The Enigma machine was used by the German military during WWII to encode communications. This chapter consists of a short history of the machine, followed by an explanation of the system’s functionality and components. We then look at the methods that were used by the Polish cryptanalysts to initially crack the system and subsequently by British and American scientists to completely neutralize the system.
THE ENIGMA MACHINE: A BRIEF HISTORY
The theory behind the Enigma enciphering machine first struck Albert Scherbius in 1918, when he considered the idea of building a cipher machine that used rotating rotors to continually change the encoding context. Scherbius immediately took his insights to the German military, but was told that the Germans didn't require further code security, as their codebook system had been sufficient during WWI. Scherbius then opened his technology to the private market, where its patents were ultimately acquired by Gewerkschaft Securitas. By the late 1920's, the Enigma machine was available commercially for individuals or companies who, for one reason or another, required secure communication.
The German Navy's interest in the Enigma machine was spurred by Great Britain's announcement that they had cracked the German codebook system. The Navy began purchasing machines in 1925 and went to work modifying them to provide more security. The German Army quickly followed suit and within a year or two, the Enigma machine was the crux of German military communication security. The modifications that were made include the addition of a plug board and (in the case of the Navy) an additional rotor. With this new technology, the German military was confident that they had an unbreakable means of encoding communications.
Polish cryptanalysts first began their work on cracking the Enigma machine in 1927 and despite Germany's various attempts to thwart their security attack by changing code regulations and tweaking the machine, they were able to decode nearly all German messages by early 1939. Later that year German forces began attacking and ultimately invaded Poland.
The Polish cryptanalyst team fled to Britain to pass their research on to the Allied super-powers and the German military went to work revamping their Enigma machines. Using the work provided by Poland, Britain and the U.S. began their work on decoding the messages of the (once-again revamped) Enigma machine. Ultimately the Allied powers were able to completely neutralize Germany's supposedly undecipherable security device by mid 1940.
HOW THE ENIGMA WORKS
The Enigma is able to map characters through sophisticated wiring and the use of rotors. Figure 1 illustrates the wiring of a rotor to map one character to another. Each rotor was unique and thus placing the rotors into the machine in the correct order was part of the encryption scheme.
A single translation is called a mono-alphabetic substitution and is quite simple to solve. If we add another rotor and attach it to the first we get figure 2.
If this setup was static it would be just be two substitutions, Q to M, M to R, which is just Q to R and again mono-alphabetic substitution. The appeal of the enigma was the odomeric nature of the rotors to rotate and advance after each key-press. Figure 3 shows the results of the above rotors after two key-presses.
Here you can see how hitting the Q key no longer generates R, but will now generate the letter L. The rotating rotors form the foundation to the encoding scheme of the Enigma.
To allow for added complexity at little cost the reflector was added to the Enigma. This allows the current to pass through all the rotors once, then get reflected and head right back through the rotors and get encoded again. The reflector itself even encodes, but unlike the rotors it was one-to-one such that if Q goes to R, R goes to Q. Figure 4 shows the entire view of the Enigma and the possible encoding of the letter Q.
To encode a message a user selects the correct three rotors from a given set and lines them up in prescribed starting positions and begins to type his message on the keyboard. At each key-press the corresponding encoding is lit up on the Lamp Board and needs to be recorded as the encoding message. To decode a message there is no need to change any wiring; just ensure that the same rotors at the same starting position are used, and the message decodes into the original text.
A Steckerboard was introduced by the Germans to allow for one more level of complexity and customizability. The Steckerboard allowed user to apply zero to 13 re-mapping of characters from the keyboard before going through the rotors. For example, plugs could be added to connect A to E. This would cause an E to be sent on to the rotors any time an A was pressed and vice-versa. The Steckerboard would have to be setup correctly for proper use of the Enigma.
With the arrival of the Polish-developed Bombe and Polish intelligence information on the Enigma machine, the British government faced the challenge of developing this technology further to allow them to decipher the German Enigma.
How the British Cracked the Enigma Cipher:
Turing’s insight into patterns reduced complexity and helped generate new algorithms for Bombe.
Plug board elimination reduced computation complexity.
Herival insight into human behavior related to Enigma usage.
The method to cracking the Enigma cipher arose from Turing’s observation that certain cribs had logical circularities that could only be generated from a limited number of Enigma settings.
He formed a theorem based on the loop that exists between the crib and the equivalent cipher text. Turing employed a mathematical technique called a reduction ad absurdum to figure out the starting patterns for the rotors. This method involves exhaustively disproving every possible rotor starting position set until a correct one is found and is akin to a brute force search. This method of determining rotor-starting positions, combined with patterns found in certain cribs established the British strategy for breaking the Enigma code.
Plug board could be ignored in a plaintext attack
As illustrated in the theoretical background of the Enigma machine, proper use of the plug board adds 500 trillion possibilities to the possible initial rotor setting. A clever mathematical trick was devised to in essence guess the plug board’s initial setting, and eliminate its added complexity from the number of permutations that had to be tested.
Nik Shaylor has written a clear textual explanation of how the complexity of the plug board is overcome:
“If for instance the crib was "TOGENERALBLOGGO" and the ciphered text was "IEDYVTGFYDOJOPT" the letters from these two texts can be matched together thus:
The second pairing is O with E the forth is E with Y the ninth is Y with L and the eleventh L with O. This is called a loop because the sequence begins and ends with the same letter, O in this case. Turing realized that there were only so many possible rotor orders and scrambler sequences that could allow this sort of loop to be produced, and that it was possible to build a machine that could search out these possible rotor sequences.
Because the Steckerboard is never changed after it is initially set up we also know that the E that was enciphered in the forth position of the crib must have had the same stecker value as the output of the second position. It is not possible to know what this was but it is enough to know only that it must be the same Stecker(E) value. Moving on in just the same way this must have been translated by the scrambler (in the forth position) to the character Stecker(Y) . This is taken to the ninth position in our crib-cipher pairing. Here the sequence is the other way around, L was enciphered to Y that is the opposite way around to the way we want for the sequence in the loop. This, however, does not matter at all, because we know that with the Enigma machine in any one setting the input and output are reciprocal. If we typed an L we would get a Y, and had we typed a Y an L would have appeared (in this example). So by the same process as before we can think of the output (rather than the input) of the ninth position being the character Stecker(L) which is the input to the eleventh position. Now we come full circle as the output of the scrambler in this position will be Stecker(O) which, if our initial hypothesis, is correct will be O.
Here we are testing our crib theorem using one known character O and three virtual characters Stecker(E), Stecker(Y), and Stecker(L) . The beauty of this is that our theorem can be tested without reference to the actual Steckerboard settings, because no steckerboard transformations (other then O) are used for the test, and hence the trillions of possible encipherings from this device are of no consequence and only the 26 x 26 x 26 x 60 possible rotor settings need to be tested. This is a number too large for manual testing, but not for a machine.”(Shaylor, 1)
This technique of eliminating the plug board can be illustrated mathematically as follows:
Given the known plaintext
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Plaintext O B E R K O M M A N D O D E R W E H R M A C H T
Ciphertext Z M G E R F E W M L K M T A W X T S W V U I N Z
Let S(X) be the effect of the plug board on x at let P(x) be the effect of the permutation at step I on x.
Consider the “cycle”
9 7 14
A M E A
P9S(A) = S(M),
P7S(M) = S(E),
P14S(E) = S(A),
S(E) = P9P7P14S(E).
Guess, say S(E) = G. If correct,
P9P7P14G = G (1)
Problem: There are 26 guesses for S(E) and, at random, 1/26 chance that (1) holds.
Solution: There is another cycle
4 15 8 7
E R W M E
P4P15P8P7S(E) = S(E)
Now guess say S(E) = G. If correct, (1) and
P4P15P8P7G = G (2)
There are still only 26 guesses for S(E) but, at random, only 1/262 = 1/676 chance that (1) and (2) hold.
Herival’s insight into human factors
A young mathematician named John Herival had the insight that human factors might also be involved in figuring out a way to break the encryption scheme. He reasoned that Enigma operators might be too lazy to change the ring settings with every sent message, and if it could be determined when the rings were set, the chances of success with a cribbing attack would increase greatly. The first message sent out after the rings were set would indicate the initial setting range of the rings which reduced complexity from a random set of 17,576 possibilities to 20 or 30 settings.
The Enigma machine was developed as a revolutionary new tool in cryptography. Its story, however provides more evidence that the technology of information security is one fraught with difficulty. This difficulty comes as a result of the system’s vulnerability to human fallacies. This is a prime example that no theory is fault-proof with regards to implementation. In short, there is no silver bullet when it comes to information security.
Mark Stamp, MediaSnap, Lecture 5/17/01
Alan Turing: The Enigma by Alan Hodges
Crpytography: A Primer by Alan G. KonHeim
Chapter 5: Rotor based encryption schemes
Nik Shaylor’s Paper on the Bombe: