Cracking Enigma

Michael Howe

March 7, 2006

In the midst of the First World War an inventor named Arthur Scherbius developed a simple machine designed for businesses to protect sensitive information. Despite being built for business customers, the machine would eventually be altered and used by the Germany military, creating an important battleground between nations fighting in the world’s next Great War. Cracking the secrets of this machine proved a daunting challenge, but provided the Allies an important advantage in defeating the Axis powers when its mysteries were overcome.

Scherbius invented Enigma in 1918. It looked similar to a typewriter and allowed an operator to type in a message and receive an encoded string as output. The message to be encrypted was typed in as a cleartext string of characters and exited as a converted string of characters with no apparent connection to the input. Soon after its development the German army realized the importance of Scherbuis’ invention. They believed that with modifications, the machine could be utilized to send text undecipherable to those without access to that message’s particular settings; so perfectly encrypted that even if someone were to steal one of the machines, they would still have miniscule odds of ever deciphering any intercepted messages. On the heels of the German defeat in World War I and subsequent disarmament, a means of secret communication was needed to effectively remilitarize without drawing too much attention. With this in mind, the German army took on the task of creating an updated version of Enigma.

Enigma acted as a stream cipher. Each letter of input was converted to another letter based on a series of conversions. An operator input a character, which was converted to another letter and output to another step in the conversion based on an offset. Figure 1 shows an example of two steps in the conversion. Take as an example that ‘H’ is accepted as the next character of input. First, it is input into the first step and converted to ‘C’. Then, ‘C’ is output to the second step. The second step accepts this character at a two character offset, so takes ‘A’ as its input. Subsequently, this step does a conversion and outputs ‘C’. This process continues through the series of conversion steps.

Figure 1: Letter conversions

Enigma accomplished these conversion steps through rotors. Rotors contained 26 notches around the outside for each letter of the alphabet, indicating the rotor’s input offset. Each rotor contained hardwired connections that converted the input to another letter. These rotor connections were the same across all instances of Enigma, allowing operators of one machine to decipher messages from another instance. The rotors sat in a series with three rotors connected together (until late in the war when Germany began adding rotors). An operator typed in a character, which was sent to the entry rotor where it was converted and passed to the next rotor at a user configurable offset. This continued until reaching the last rotor. As time progressed, the Germans further increased the difficulty of cracking the code by including five rotors from which the operators would choose three and situate them in a particular order for the encryption. Figure 2 shows a picture of the rotor machinery.

Figure 2: Enigma rotors

As each letter was enciphered, an electric current was sent through the machine. This current shifted the offset of the first rotor by one place. If the rotor currently held no offset and was in place ‘A’, it would shift to place ‘B’ after doing the first conversion. The second and third rotors would also shift, although with less frequency. This process continued with every conversion creating a situation where the encryption process was continually changing. The mechanism for the shifts was a “carry” notch on each of the rotors. Its purpose was to trigger the next rotor to shift whenever the notch hit. This acted in the same logical way that numbers are carried over in addition when they pass a certain threshold (like passing nine in the ones column in base ten, which is then carried to the tens column). The “carry” notch was at a different place for each of the rotors.

Military Enigma added extra complexity to the commercial model with the use of a reflector. Instead of a letter being converted through three rotors and then outputting an enciphered character, the last rotor now fed into a reflector plate. This plate returned a converted letter to the last rotor and the letter was converted back through to the second and then first rotor. The reflector plate differed from the rotors in that it contained fixed connections between two letters. For instance, if the third rotor output ‘F’ and received back ‘D’ from the plate, it would receive back ‘F’ when inputting ‘D’. This “reflection” allowed the individual operators of Enigma to utilize the same settings to both encrypt and decrypt. Decryption simply occurred by sending the cipher text through the machinery in the same way as when encrypting a message. While a nice convenience, the reflector plate eventually proved a great aid to those trying to crack the code since a letter could never encrypt to itself.

Military Enigma added yet another form of complexity to the commercial version by allowing its operators to insert plugs to make a connection between pairs of letters before and after the rotor conversions. Figure 3 contains a picture of an Enigma plugboard, showing where the operator would insert plugs between pairs of letters to make the connection. This would serve as a conversion both before the entry rotor received the input and also before the output was displayed. For example, the operator might choose to connect ‘Q’ and ‘M’. If the operator pressed ‘Q’ on the keyboard, it would be converted to ‘M’ before entering into the series of rotors.

Figure 3: Enigma plugboard

Essential to Enigma being able to effectively pass along messages was every operator utilizing the same settings for encrypting and decrypting a single message. Otherwise, the receiver of a message would have no easy to way to understand any message. To accomplish this task the Germans distributed to each operator station a sheet containing configuration information for each day in a month. The sheet included the following information: the rotors to be used and their order, the letter setting for each rotor and the plug settings. The operator would then choose a three letter key for each individual message. He would encrypt this key twice beginning from the base settings. The six characters resulting from these two encryptions would then be passed along at the beginning of the communication. The doubly encrypted key ensured that the key arrived correctly. However, this system was fairly easily solved by the code breakers and provided them extra information that was useful in determining the overall operation of Enigma.

With the alterations made by the Germans, the military Enigma boasted a staggering number of states, particularly after making their later changes to increase complexity. Since there were five rotors that could be placed in the three positions, there were 5 x 4 x 3 = 60 possible ways of ordering the rotors. Once put in place each of the rotors could rotate into any of 26 positions. With three rotors there were 26 x 26 x 26 = 17576 possible ways of positioning the rotors in the machine. The plugboard contributed massively to the possibilities, especially in the later years when the operators used up to ten plugs. With all ten plugs there were over 1.507382749373 x 1014 possibilities of connecting the board. All together there were 60 x 17576 x 676 x 1.507382749373 x 1014 = 1.074586873273 x 1023 possible states facing the code breakers. Even after determining the internal operations of Enigma, the code breakers still needed to find the machine’s configurations for each individual sent message.

By the late 1920s other countries realized that a buildup of German military might was again probable. In order to track this buildup, countries like Poland needed a way to monitor secret German communications. To accomplish this task Poland recruited the best mathematical minds the country offered, including Marian Rejewski, Henryk Zygalski and Jerzy Rozycki. These mathematicians worked out of a secret location constantly trying to break the German system of encipherment. At first this effort was fairly straightforward as the cryptographic methods were well understood. However, in the beginning of the 1930s messages began appearing that appeared uncrackable. The Germans had begun using Enigma and the Polish mathematicians needed to alter their tactics to catch up.

The Polish cryptographers initially did not have access to the military version of Enigma, only possessing a commercial version of the machine. Thanks to French intelligence, though, they were given operating instructions to military Enigma, keying instructions, old monthly configuration sheets and cipher/plaintext pairs. They combined this information with their mathematical background to begin cracking the code. Their first task was to recreate a version of Enigma.

The first means of attacking the code was to analyze the twice encrypted key. Since they had possession of a large number of encrypted messages for any given day, the cryptographers began by finding cycles of encrypted letters. They knew that the first three letters encrypted to the second three letters. Thus, the first letter encrypted to the fourth letter, the second to the fifth and the third to the sixth. They wrote down all the first six characters of messages they had intercepted. Then, they looked for fourth letters corresponding to first letters in other messages, since that would provide a connection to what this letter encrypted to. For instance, say the letters “dmq vbn, von puy, puc fmq” constituted the beginning of three intercepted messages. The first message tells us that ‘d’ converts to ‘v’. The second indicates that ‘v’ converts to ‘p’ and the third that ‘p’ converts to ‘f’. In this way a cycle containing “dvpf” is determined. Continuing to work this out with enough messages would provide the full cycles for the first, second and third characters. Through this process the code breakers discovered characteristics, such as the feature that cycles of the same length occurred in every line in even numbers. Combining this information with human engineering (for example, early in their efforts they knew that the operators chose message keys consisting of the same three letters, like “aaa”), the cryptographers were able to determine rules for key cracking and gained valuable insight into the inner working of the machine.. As the operators’ methods for key creation became more complicated, the code breakers continually utilized human engineering skills and followed along with the increased sophistication.

Since the understanding of the Enigma keys provided six successive permutations, the Polish mathematicians were next able to move onto discovering the connections in the rotors. Because of the fact that the rotor connections needed to be the same in the sender and receiver operators’ machines, the code breakers only needed to determine the connections of the existing rotors. The code breakers developed equations to determine the internal wiring of the rotors once the input characters reached the entry rotor. However, a huge challenge confronted the Poles. How was the keyboard connected to the entry rotor? On the commercial version of Enigma, the wiring circled around the rotor according to the placement of the keys on the keyboard (QWER…). After trying this combination it became apparent that this ordering was not accurate on the military version. Without any other recourse, the Polish mathematician Rejeswki fell back upon human engineering yet again. He utilized his knowledge of German order and precision and guessed that the wiring was in alphabetic order (ABCD…). This guess proved correct. With this information combined with his set of formulas, knowledge of the aforementioned keys, ciphertext/plaintext pairs and trial and error the team was able to work out the rotor connections. This was a huge step. Knowing the fundamentals of Enigma, the Polish team then went about creating their own physical duplicates of the machine. At this point they possessed the ability to determine the daily and message keys and had a machine to then decipher the intercepted messages. Deciphering the messages still required tremendous amounts of daily manual labor, particularly as the Germans further changed and complicated their methods. For the next years, the Polish team continually updated their methods so that they were more efficient and automated.

A problem they continually faced was the order of the rotors at any given time (as the Germans refined their methods, this order changed more frequently). The team knew that this configuration could be determined by analyzing the encrypted message key passed in the first six characters of each message. They sought to catalog these configurations, which would make determining the current configuration a quick process (ten to twenty minutes). To speed up the tedious cataloging process, they created a device called a cyclometer. It consisted of two sets of rotor set at an offset to each other. Though the cyclometer allowed them to complete their catalog in under a year, the Germans changed their methods. This required other automated decryption methods.

At about the same time as the Germans changed their methods, the Polish team developed two new tools, Zygalski sheets and the Bomba. Zygalski sheets were a series of perforated paper sheets with columns and rows of up to 51 holes up and across. Each series consisted of 26 sheets. The user worked through each of the possible first rotor letters, up to 156. A sheet existed for each first wheel letter with each possible wheel order. The correct first sheet would then overlay the next possible sheets. When holes coincided throughout these sheets, the original ring settings could be deduced. The Bomba was a hybrid of the Enigma machine that automatically revolved the rotors trying all combinations. It worked off of the double enciphered message key and iterated until finding the exact rotor positions that corresponded to the encipherment. As long as the Germans only had three rotors interchangeable in Enigma, six Bomba machines were needed. However, when the configuration was changed so that the operators selected the rotors out of a possible five, 60 of these devices were required to do the work.

At its height of its efforts the Polish team was boasting a dechiperment rate of around 75% of all messages intercepted. Unfortunately, in 1939 the political state worsened and Poland drew closer to a military attack by the Germans. In anticipation of this event the Polish team invited the British and French cryptographers to a meeting where they shared their findings. In this meeting the Polish cryptographers told of the working of Enigma and demonstrated their tools and methods for discovering configurations and keys. They even offered to send their Enigma replicas to the foreign teams. As the British and French had found little success cracking Enigma, this aid proved invaluable. When Poland was finally attacked and conquered by the Germans, the code breaking efforts transferred to France and Britain.

For the remainder of the war the task facing the code breaking teams was to enhance the finding of the Polish cryptographers, to develop tools to ease the finding of configuration and keys and to keep their mastery of Enigma a secret to the Germans. As time went along the Germans altered their methods several times, requiring an agile and ever-updating attack. The British, led by Dillwyn Knox and Alan Turing, had the most success in solving Enigma from their secret location at Bletchley Park once they learned of the Polish advances. The British focused much of their efforts on constructing a machine that could determine the current machine configuration and key based on known combinations of ciphertext/plaintext pairs, in a way similar to the Polish tools. This method required at least one known pair every day, which they solved by exploiting common German communications and their knowledge that a letter could never encrypt to itself.

The device developed at Bletchley Park to accomplish this task was called Turing’s Bomb. It was inspired by the earlier work of the Polish cryptographers and relied on the possession of known plaintext, known as a “crib”. The rotors would automatically rotate through all possible combinations. With every combination an electric current test would be done to determine whether this configuration was a possibility based on the known ciphertext/plaintext pair. The machine would stop when it found a possibility, requiring further analysis to determine if this were indeed the correct combination. The biggest complication came from Enigma’s use of plugboards since it was difficult to know what crib and ciphertext were transformed to between the input/output and rotors. The original version of the Bomb worked in theory but required cribs that were too long to be practical, especially considering the German practice of limiting message length. After the development of the initial Bomb design, another member of the Bletchey group, Gordon Welchman, realized the reciprocal nature of the plugboard. If ‘A’ were plugged to ‘B’, then ‘B’ had to be plugged into ‘A’. He developed an enhancement called the Diagonal Board. It consisted of a matrix of the letters in the alphabet connected with diagonal wires across the board. When Turing’s Bomb was reconstructed with this attachment, the machine became an effective decryption tool. More Bombs were produced and put to use. Turing’s Bomb was hugely successful. By the end of the war it has been estimated that Bletchley Park was deciphering 18,000 messages a day, thanks in large part to Turing’s Bomb. Figure 4 shows a picture of the machine.