Codebreaking was instrumental to computing history. Richard Harris presents a simplified Enigma code for you to crack.
I was fortunate enough to be invited to assist in the ACCU's charitable efforts for Bletchley Park at this year's conference by creating a cryptographic puzzle that would form part of the fundraising effort. It was intended to be simpler to solve by hand than by computer, and to encourage the former included a question that could not be answered if one simply wrote a program to examine every potential solution. In fact, it was designed so that it should be possible to solve the challenge by hand with pen and paper in about 15 to 30 minutes, albeit only if one had spotted the properties of the puzzle that made such a speedy solution possible.
So that you too might enjoy the challenge it is presented below, followed by an historical justification and then its solution.
The challenge
Encoding
The enemy are using a 36 character alphabet encoded with 2 digit base 6 numbers such that the numerical value of the character is equal to 6 times the first digit plus the second digit. The # character is a control code indicating that the following two digits should be interpreted as a two digit base 6 integer in the range 0 to 35, rather than as a letter or punctuation. The full table of character mappings is given below:
000000111111222222333333444444555555
012345012345012345012345012345012345
#abcdefghijklmnopqrstuvwxyz ?!.+-*/=
Encryption
The encryption scheme used by the enemy is an Enigma variant with two 6 digit rotors of the form shown in Figure 1.
|
| Figure 1 |
When a plaintext digit is entered it is mapped to an intermediate value by the first rotor (which may be either A or B) and then to the cyphertext by the second rotor along the connecting lines. For example, given the setting above, where rotor A is the first and rotor B the second, the digit 1 would be mapped by rotor A to an intermediate value of 5 and then by rotor B to the cyphertext digit 4.
After each digit (i.e. half a character) is entered the connections on the second rotor rotate 1 digit clockwise. After every 6 digits, the connections on the first rotor also rotate 1 digit clockwise.
The order and orientation of the initial setting of the rotors is unknown.
Plaintext
We know that the enemy prefix their plaintext messages with a single base 6 digit (i.e. half a character) representing the message's priority. We also know that they foolishly sign the plaintext so that the last characters are always of the form:
NN...NNDDMMM
where N stands for the surname of the agent, D for the day and M for the month. For example:
harris04feb
Cyphertext
Decrypting the following cyphertext will reveal which drop to deposit your ticket in:
514524110354101255444144222503405
Bonus question
Defining use to mean 'consider the implications for more than any two digits (i.e. one character's worth of data) in the cyphertext', how many initial rotor settings must we use in the worst case to guarantee that we correctly decrypt this message?
The historical justification
Given that Bletchley Park was the intended beneficiary of our charitable efforts it was a natural choice to base the puzzle on the Enigma machine, an example of which is illustrated in Figure 1. The difficult part was ensuring that the weaknesses I introduced into the puzzle reflected historic weaknesses in the design and use of the Enigma machine.
Originally marketed to businesses as a secure means of corporate communication, the Enigma machine was adopted by the German armed forces between the years of 1926 and 1935; the Navy were the first to adopt it and the Air Force the last [ Copeland04 ] .
The original machine had three rotors around the edge of which were printed the 26 letters of the alphabet. They could be placed in any order in the machine and were internally wired to create electrical paths connecting pairs of letters. Figure 2 shows an Enigma machine (photo by K. Sperling).
|
| Figure 2 |
Adjacent to the left-most rotor was a reflector board connecting pairs of letters on the left-most rotor, resulting for each letter in a path leading through the assembly from the right-most rotor to the left-most, through the reflector board and back again from the left-most to the right-most, conceptually illustrated in Figure 3.
|
| Figure 3 |
After each key press the right-most rotor would rotate by one step. After it had rotated through all 26 steps the middle rotor would rotate by one step and after it, in turn, had rotated through all 26 steps the left-most rotor would rotate by one (the rotation of the rotors was, in fact, slightly more complicated than this, but this description captures the basic idea).
Finally, the keys used to input the message and the lamps lighting up the encrypted letters were wired to the right-most rotor such that the encryption was symmetric; if the key Q resulted in the letter A lighting up for a given set-up, the key A would result in the letter Q lighting up, as illustrated in Figure 4.
|
| Figure 4 |
Hence to decrypt a message, one needed simply to type it into an Enigma machine configured in exactly the same way as the one that was used to encrypt it.
The encryption scheme resulting from this mechanism is a known as a substitution cipher, in which each letter in the message is encrypted by substituting it with another. When the substitution rule is fixed for the whole message, this scheme is fairly easy to crack. The mechanism of the Enigma machine ensured that the substitution rule changed after every letter in the message and only cycled through all of the rules a given set-up could represent after key presses. Furthermore, since the 3 rotors could be arranged in 6 different ways, there were 6 times as many initial settings and hence sequences of substitution rules.
The military version of the Enigma machine added further complexities to increase first the number of initial settings and then the length of the cycles of substitution rules.
The encryption scheme described in the Enigma challenge is clearly a much simplified version of the Enigma machine. Whilst it follows the same basic principle of implementing a substitution cipher using connections between letters on rotors, and of changing the substitution rule after each letter in the message by rotating them, it only has a 6 letter alphabet, 2 rotors and it entirely does away with the reflector board.
Now that I have described the mechanism of the Enigma machine and how the challenge is just a simplified version of the encryption scheme it implemented, it's time to describe a couple of its weaknesses which inspired the specific details of the challenge that make it relatively simple to solve.
One weakness of the Enigma machine was the order in which the rotors were rotated after each key press; if the middle rotor had been the first to rotate rather than the right-most it would have been considerably more difficult to crack [ Leavitt06 ] .
To reflect this weakness, the Enigma challenge uses deliberately badly designed rotors; the specific details are given in the solution, below.
The next weakness of the Enigma machine, at least in the early days of its use by the German military, was that rather than use a daily pre-distributed setting for encoding messages, they would use such a daily setting to encode a 3 character message defining the rotor setting for the remainder of the message. Whilst on the face of it this seems to be a pretty sensible scheme, they further decided to repeat the message setting twice to allow checking for errors in the settings or the message transmission. By enforcing that the first 6 characters of the message were in fact a pair of identical 3 character messages, the German military had provided their enemies with a hint, or crib, as to what the daily rotor settings were.
This is reflected in the Enigma challenge by the message signature. By consistently signing their messages in a specific format, our hypothetical enemies have introduced a fatal weakness into the encryption scheme, as detailed in the solution, below.
The solution
To decrypt this message, the first thing to note is the rotational symmetries of the rotors, meaning that there are only 6 unique settings for each ordering. The second thing to note is that reversing the order of the rotors reverses the mapping of the digits, meaning that we can deduce the mapping for both orderings by examining only one.
Naming the rotor positions as in their initial description and rotated clockwise through their distinct states as A 0 , A 1 , A 2 , B 0 and B 1 respectively and using permutation notation (in which each number in the top rows are encrypted to the numbers below them) we have:
Next we note that the day in the signature will be an integer between 0 and 31, so will be encoded in the number format; namely two 0 digits followed by the value in base 36. This means that the 9th and 10th digits from the end of the encoded plaintext must both be 0. Hence, at that point in the encryption we have:
0 → 4 then 0 → 2
This could only occur with the sequential rotor positions A 0 B 1 , A 0 B 0 or B 0 A 1 , B 1 A 2 .
Finally we note that the 10th digit from the end is the 24th from the start and, since this is a multiple of 6, both rotors must turn after it is encrypted. Hence the rotor positions at this point must be B 0 A 1 . Furthermore, since 24 is an even multiple of 6 and rotor B only has 2 unique states, the next state must be equivalent to the starting position of the rotors, namely B 1 A 2 and so the rotors must cycle through the sequence:
B 1 A 2 , B 1 A 0 , B 1 A 1 , B 1 A 2 , B 1 A 0 , B 1 A 1 , B 0 A 2 , B 0 A 0 , B 0 A 1 , B 0 A 2 , B 0 A 0 , B 0 A 1
Applying this to the cyphertext gives us:
102132243000443024130230035140122
Hence the plaintext is:
1bin #04 byro#35jan
or:
(priority 1) bin 4 byro23jan
and we only need use 1 initial rotor setting to successfully decrypt the message.
In closing
Well, I hope you enjoyed the Enigma challenge and that it gave you a taste of the technical process of code breaking, or cryptanalysis. If this has piqued your interest in the subject and you would like to read more about it, Simon Singh's The Code Book [ Singh99 ] provides an enjoyable layman's treatment. For the more mathematically minded, there are many textbooks on the subject: Handbook of Applied Cryptography [ Menezes97 ] is the one currently sitting on my desk.
I would also recommend a visit to Bletchley Park itself with its many exhibits on the code breaking work undertaken there during the Second World War and its fledgling Computer Museum [ Bletchley ] . Whilst we're about it, why not give them a donation? As a fundamental part of our collective history as computer programmers and users, we owe it to ourselves to see that this site is maintained for future generations.
This article has been something of a departure from our usual subject matter, but given the importance of the beneficiary, I believe it to be a justifiable one.
Next time, dear reader, normal service will be resumed.
And finally...
Congratulations to Jim Hague, Alan Brooks, Phil Bitis, Andrew Bainbridge, Sam Saariste, Roger Orr, Per Liboriussen, Dave Hargreaves, Jan Willem, Jonathan Wakely, Charles Tolman, Judy Booth, Seb Rose, Jakob Gaardsted, George Vernon, Gary Duke, who all broke the code, and especially to Duncan Grant, Matthias Hertel and Andrew Kemp who successfully cryptanalysed the Enigma Challenge.
To everyone who took part, and to everyone who donated to Bletchley, we should like to extend our deepest gratitude.
Acknowledgements
With thanks to Astrid Byro, John Paul Barjaktarevi? and Lee Jackson for proof reading this article.
References and further reading
[Bletchley] www.bletchleypark.org.uk
[Copeland04] Copeland, B. (ed), The Essential Turing, Oxford University Press, 2004
[Leavitt06] Leavitt, D., The Man Who Knew Too Much, Weidenfeld & Nicolson, 2006
[Menezes97] Menezes, A. et al, Handbook of Applied Cryptography, CRC Press, 1997
