Previous section: One-time pads and the Venona project
On the opposing side in the Second World War, the Germans encrypted and decrypted messages using Enigma machines. These created keys as they went along, which avoided the practical problems that resulted from using one-time pads. The machines were invented during the First World War and were available for commercial use in the 1920s before being commandeered by the German military. The sender typed his message letter by letter into a keyboard. Each time a key was pressed, a lamp lit up on the machine that displayed the encoded version of the letter. The encoded message was then sent by Morse code. If the receiver had an Enigma machine that she had set up identically to the sender’s, she could type the encoded message into her machine and read the original message off the lamps.
This was before electronics had come into general use. Enigma machines worked with a combination of simple electric current and mechanics. The electric current flowed through a number of linked components, each of which substituted a letter for another letter. The central components were rotor wheels, each of which had twenty-six notches. A rotor wheel was placed into a slot in the machine and made contact with twenty-six connections arranged in a circle to its right and another twenty-six connections arranged in a circle to its left. The slot and the circles of connections on either side of it were all perpendicular to the machine, so that only one side of the edge of a rotor wheel was visible when it had been placed in a slot. Each of the circles of connections corresponded to the letters of the alphabet arranged in alphabetical order from A to Z.
There were several types of rotor wheel that were distinguished from one another by their internal wiring. The wires in each type linked the connections on their right to the connections on their left in a different, randomly chosen way that determined which letter was substituted for which when current was passed through the rotor. One rotor might replace A with D, B with M and C with T, while another rotor might replace A with U, B with N and C with P. An Enigma machine had three or more slots into which different rotors were placed. The rightmost rotor might replace A with D, then the middle rotor D with Q, and then the leftmost rotor Q with F.
Crucially, each time a key was pressed and a letter had been encoded, the three rotors were incremented much like the units, tens and hundreds columns of the mechanical counters that were used in the pre-digital age to track how far a vehicle had been driven. The rightmost rotor would move by one position after each key press. Each time the rightmost rotor had turned through a whole circle, the middle rotor would move by one position, and each time the middle rotor had turned through a whole circle, the leftmost rotor would move by one position. Choosing three letters out of the twenty-six at random as examples, a rotor that had replaced K with C, P with X and T with H before being moved by one position would now replace J with B, O with W and S with G. The movement of the rotors had the effect that each letter in a message was encrypted using a completely different set of correspondences between the original alphabet and the encoded alphabet.
To make the system still more complicated and difficult to crack, the rotors were used in conjunction with a plugboard. The plugboard had a socket for each letter of the alphabet and leads could be plugged into it to link letters in a pairwise fashion. For example, D and M might be linked by a lead. This would cause D to be replaced by M and M to be replaced by D when current passed through the plugboard. Normally, six pairs of letters were connected in this way, while the other fourteen letters were left unconnected.
When a user typed a letter into the keyboard, the current flowed from the key he had pressed to the plugboard. If the letter was connected on the plugboard, it was replaced by its pair, otherwise it remained unchanged. The current then flowed through the rotors one after the other, a new substitution occurring each time. It then passed through a reflector. Like the plugboard, a reflector connected letters in a pairwise fashion. However, important differences were that a reflector did not leave any letters unchanged and that its wiring was fixed rather than being set up by the person using the machine. There were different types of reflector that wired different pairs of letters together. The letter the reflector returned was then passed backwards through the three rotors in reverse order before finally the plugboard was traversed a second time. The encoded version of the letter then lit up on the lampboard.
Coupled with the fact that the plugboard and the reflector themselves linked pairs of letters, the symmetrical nature of this setup – plugboard, then rotors, then reflector, then rotors again, then plugboard again – meant that the Enigma machine as a whole itself encoded letters in a pairwise fashion. If pressing the letter K with the machine set up in a certain way and its rotors in a certain position caused the W lamp to light up, pressing the letter W with the same setup and rotor positions would cause the K lamp to light up. The electric current would take the same path in both cases, just in opposite directions. This feature was what allowed two people to communicate using Enigma without any difference in the way the encrypting and the decrypting machines were set up or used.
Information about how to set up groups of Enigma machines so they could encode and decode one another’s messages was distributed to military personnel in advance using paper codebooks. It included which rotor and reflector types to use, which rotors to place into which slots and which pairs of letters to link on the plugboard. Unlike a Russian one-time pad, which had to be the same length as the messages it was encoding, an Enigma setup took up a mere line in a table. Each setup was normally valid for a day, so that a whole month’s configurations could be captured on a single piece of paper.
In order to make use of the full range of substitution alphabets the Enigma machine could generate, the rotors had to be set to different starting positions each time a new message was sent. If the rotors had been set to the same initial positions for a large number of messages sent on a single day, they could have been decoded using the statistical frequency analysis technique discussed earlier in this chapter. All original messages that began with the letter E would then have resulted in encrypted messages that themselves began with the same letter, and it could then have been determined that, for the first position within each message, this letter must encode E based on how often it was observed to occur relative to the other encoded letters.
The twenty-six positions in which each rotor could be placed were marked using an alphabet wheel that circled the rotor. This showed the twenty-six letters of the alphabet in alphabetical order. When a rotor had been slotted into the machine, one of these letters was visible in a window at the front. It is important to understand that this was merely a convenient way of labelling the different positions a rotor could be in. Which letter showed at the front of a rotor had nothing to do with the substitutions it would perform when current was passed through it.
Because the sender of a message set the initial rotor positions randomly for each new message, they had to be somehow transmitted to the recipient. Different procedures were used to achieve this at different points during the war and by different armed forces, but the most common one was based on the idea that one set of three initial rotor positions, which was transmitted in unencrypted form, was used to set up the machine to encrypt three letters that made up a second set of initial rotor positions. This second set was then used to set up the machines to encode and decode the actual message.
The sender would choose three letters at random and set his rotors accordingly. These three letters, say TDH, formed what were known as the indicator. He would then choose the initial rotor positions for the actual message, say WOF, and type them into the machine – which he had set up with the other settings that were valid for that day – to obtain the encrypted version, say LSG. Before sending the actual message, he would transmit the indicator TDH and the encrypted initial rotor positions LSG.
The recipient would set the rotors on his machine to the indicator TDH and type in the encrypted initial rotor positions LSG. The lampboard would display the chosen initial rotor positions WOF. The recipient could then set his rotors accordingly and begin decrypting the message that followed.
To make things more complex and to reduce the amount of information the indicator and the encrypted initial rotor positions would give to an eavesdropper, the wiring component within each rotor was built so that it could itself be turned through a circle with twenty-six positions. The position of the wiring component was shown by a single dot on it that aligned with one of the letters on the alphabet wheel. Moving the wiring component changed which letter on the alphabet wheel referred to which of the twenty-six groups of letter substitutions of which the rotor was capable.
In the example above, a rotor that had replaced K with C, P with X and T with H was moved by one position so that it replaced J with B, O with W and S with G. Perhaps the wiring component had been set with its dot aligned to R and the rotor was moved from the L position to the M position. The same effect could have been achieved by leaving the rotor in the L position but moving its wiring component one notch in the opposite direction from R to P.
Together with the types of rotor to use, the slots to place them in and the plugboard settings, the positions of the wiring components within each rotor made up part of the pre-distributed setup information that was valid for a day at a time.
It was inconceivable for most Germans using the Enigma system that anyone would manage to read the encrypted messages without access to the codebooks. That so many of the messages were in fact successfully decoded by the western Allies was a tremendous intellectual achievement and played a pivotal role in their eventual victory. Although its story remained classified for several decades following the war, the Bletchley Park project to decipher the Enigma messages has since entered the collective legend of several nations that were involved: Great Britain, Poland, France and the United States.
The mathematicians and linguists working at Bletchley Park cracked Enigma messages using a variety of analysis techniques. Many of them are well beyond the scope of this book. Different situations called for different combinations of methods. For example, while most Enigma machines had three rotor slots, some machines used later in the war had more; and the German navy used a more complex means of transmitting initial rotor positions than the one described above. Much of the decoding work relied on mechanical analysis machines called bombes. These were developed at Bletchley Park specifically for the task and were perhaps some of the earliest computers, depending on how the word is defined.
The overall design of the Enigma system had already been in the public domain before the war. On occasions, military operations led to the physical capture of Enigma machines which could then be examined to glean crucial information like the internal wirings of previously unseen rotor types. The seizure of a codebook would reveal helpful facts about operating procedures, and if nobody noticed it had been lost it might even allow a few weeks’ messages to be read without any work on the part of the Bletchley Park teams. In general, however, details that seeped in from outside played much less of an important role than patterns that were discerned within the messages themselves. That these were so often sufficient to allow the original content to be retrieved resulted from a combination of flaws both in the basic design of the machines and in how the Germans used them.
The most important weakness of the system was that no letter could ever be encrypted to itself because the machine could only be configured to substitute the letters of the alphabet in a pairwise fashion. On one famous occasion, this feature was used to successfully derive the wiring for a previously unknown rotor type when somebody sent a test message that consisted exclusively of the letter L repeated over and over again. The person at Bletchley Park examining the encoded version of the message noticed that it did not contain the letter L and had a hunch as to what had happened.
In everyday decoding work, the same shortcoming could be exploited to discover which part of an encrypted text encoded a specific stretch of original text. The Bletchley Park workers frequently knew or strongly suspected that an encoded message would include certain phrases, because military communication is highly formulaic. The German for “Nothing to report” was often transmitted day in, day out, and even when there was something to report it was frequently couched in standard language. Identifying which individual was sending a message could further increase the predictability of its contents. This was sometimes possible if he transmitted Morse code with a distinctive rhythm.
Recurring stretches of text like “Nothing to report” were called cribs. An analyst who knew that a given crib formed part of a message but did not know exactly where in the encoded message it lay hidden could often work the position out using the fact that no letter could be encrypted to itself. All candidate positions within the encoded message could be excluded where at least one encoded letter had the same value as its unencoded counterpart from the crib. For example, the word ENIGMA could not possibly be positioned at any point in an encrypted message where the first encoded letter was an E, the second encoded letter an N, the third encoded letter an I, the fourth encoded letter a G, the fifth encoded letter an M or the sixth encoded letter an A. By process of elimination, this technique would ideally identify a single position in a given encrypted message at which a string of letters began that was expected to encode the crib.
Presumed correspondences between cribs and the letters that were thought to encode them were used to set up the bombe machines. Although there are a vast number of possible permutations in which the various components of an Enigma machine can be configured, a bombe was capable of proving that most of them could not have possibly led to all the correspondences between cribs and codes that had been observed on a given day. Once most of the candidate setups for a day’s messages had been discounted as impossible, the remaining configurations could be tried out one by one by hand until the analysts hit on the one that was seen to work in that it yielded a sensible German message.
The repetitive nature of the messages meant that they typically contained cribs in sufficient quantity to allow each day’s codebook settings to be determined. However, the Allies were not always prepared to leave this to chance. When they were planning a particularly important military operation and needed to be sure of their ability to read enemy communication on the day it began, they would sometimes lay mines purely so that the positions of the mines would appear in messages transmitted shortly afterwards and could then serve as cribs.
The rotors interacted with one another in a way that was supposed to make the system more secure but that actually had the opposite effect. When a numerical counter with units, tens and hundreds columns is incremented, only the units column advances most of the time. When the units column .moves from 9 to 0, this causes the tens column to advance as well; and when the tens column itself moves from 9 to 0, the hundreds column advances. The rotors that were slotted into an Enigma machine were interconnected according to a similar principle. A middle or leftmost rotor advanced when the rotor to its right was moved to a specific letter on its alphabet wheel. However, for each rotor type it was a different letter that caused the rotor to its left to advance. This was designed to make the machine more complicated and harder to crack, but it actually helped analysts to determine which rotors had been placed in which slots in sender machines by observing statistical patterns in encoded texts that betrayed when the middle and leftmost rotors moved.
The German military was concerned that Enigma might be used with a small selection of simple, easily memorable setups that the enemy would quickly be able to recover. To force codebook authors and operators to vary how the machines were configured, they stipulated that a rotor should never be allowed to remain in the same slot on the machine on two subsequent days, nor should a letter ever be wired to its immediate neighbour on the plugboard. These decisions actually handed unintended advantages to the Allies by reducing the number of permutations the bombes had to consider in their process of exclusion on any given day.
At the same time, the fear that personnel under pressure would cut corners and fail to use the full range of possible setups effectively was absolutely founded. From 1942, just like the Russians with their one-time pads, the office responsible for generating codebooks started to reuse settings from previous months, which was a godsend to the analysts at Bletchley Park once they realised what had happened.
More generally, the military personnel responsible for transmitting messages often had little or no understanding of the rationale behind the operating principles that they were supposed to be following to keep the system secure. They had precise instructions detailing how to use the Enigma machines, and if they had followed them exactly the Allies would not have been able to listen in quite as often. As it was, they started to cut corners because doing so made life easier. Because they had no way of knowing that their sloppiness was allowing others to eavesdrop, bad practice became a habit.
The security of the system relied on the initial rotor positions for each message being completely randomly chosen. In reality, certain message transmitters – who were sometimes identifiable based on the rhythm of their Morse code – tended to use trivial settings like AAA or BBB or settings based on names or obscenities. Knowing the probable initial rotor positions for a message made the task of determining the other machine settings easier. As the other settings were valid for all messages sent on a particular day, a small number of messages that had been encoded sloppily could end up allowing the Bletchley Park teams to eavesdrop on a much larger number of messages whose transmitters had observed the rules down to the last detail.
Before the first message of each day could be transmitted, the wiring component within each rotor had to be set to the value specified in the codebook. One of the most useful insights at Bletchley Park was that the easiest way of moving the dot on the wiring component to align with a given letter on the alphabet wheel was to move both the letter and the dot to the front of the machine so that the letter would be visible through the rotor window. This meant that the physical act of setting a rotor’s wiring component, depending on how it was performed, could entail moving the rotor itself to a corresponding and predictable position.
The operating instructions stated that the rotors should then be moved to random positions to use for the indicator of the first message. However, this step was often skipped or performed perfunctorily, perhaps advancing one or two rotors by one or two notches. It may have been that message transmitters reasoned that the indicator was not really that important because it was not used to encrypt the actual message, but merely to communicate how to set up the machine for it.
In fact, because the indicators were sent unencrypted, the task of finding out in which positions the wiring components had been placed on a given day was greatly aided by clusters of indicator values that were observed in the messages sent first thing in the morning immediately after the wiring components had been put in their new positions. If twenty initial messages were sent on a given day and the indicator value for the rightmost rotor was D for two of them, E for three of them and F for two of them, with the remaining values distributed randomly throughout the alphabet, it was likely that the wiring component for that rotor had been set to a position around the letter E.
|Tweet about Enigma and Bletchley Park|
Next section: Block-based encryption methods