Previous section: Running keys, 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 letter was pressed, a lamp lit up on the machine and displayed the encoded version of that letter. The encoded message was then sent by Morse code. If the receiver had an Enigma machine that he had set up identically to the sender’s, he could type the encoded message into his machine and read the original message off its lamps.
This was before electronics had come into general use. Enigma machines worked with a combination of mechanics and simple electrics. Electric current flowed through a number of linked components. Each component substituted whatever letter it received for another letter that it then passed on to the next component in the chain. The most important components were rotor wheels. Each rotor wheel had twenty-six equally spaced notches and was placed into a perpendicular slot in the machine where it 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.
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 have replaced A with D, B with M and C with T, while another rotor might have replaced 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 have replaced A with D, then the middle rotor D with Q, and then the leftmost rotor Q with F.
Each time a key was pressed and a letter had been encoded, the 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 rightmost 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 advancement of the rotors had the effect that each letter position within a message was encrypted using a completely different set of correspondences between the original alphabet and the encoded alphabet.
To make the system yet 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, ten pairs of letters were connected in this way, while the other six 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, although there were different types of reflector that paired up the alphabet in different ways. 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 both linked pairs of letters, the symmetrical nature of this setup – plugboard, then rotors, then reflector, then rotors again, then plugboard again – was what allowed two people to communicate using Enigma without any difference in the way the encrypting and the decrypting machines were configured or used. It 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.
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 message (or as the unfortunate reality had it, 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 configurations for a whole month could be captured on a single sheet 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 same initial positions had been used for a large number of messages sent on a single day, the resulting cipher could have been decoded using the frequency analysis techniques discussed earlier in this chapter. For example, 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 into 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. The three letters that were displayed on the sending machine before a message was typed into it showed how the rotors on the receiving machine would have to be set up to decode that message. It is important to understand that the alphabet wheel 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. However, the most common one was based on the concept that one set of three initial rotor positions, which was transmitted in unencrypted form, was used to configure the machine to encrypt a second triad of letters that then formed the initial rotor positions for the actual message. The idea was that somebody who eavesdropped on the first set of positions would remain unable to decrypt the second set because he would not know the other settings that were valid for that day.
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 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 to these positions 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 the rotor 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 advanced 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 Q. 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 be able to glean anything from the encrypted information 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 that played a decisive role in their eventual victory. The Bletchley Park project to decipher the Enigma messages has since attained the status of national legend in several countries that were involved: the United Kingdom; Poland; France; and the United States.
The mathematicians and linguists working at Bletchley Park used a variety of analysis techniques to crack the Enigma code, many of which 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 that were developed at Bletchley Park specifically for the task. Whether or not it is apposite to regard the bombes as the first computers depends largely on how a computer is defined.
The overall design of the Enigma system had already been in the public domain before the war. On occasion, military operations led to the physical capture of Enigma machines that could then be examined to gain 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 could even allow a couple of days’ 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 so often allowed 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 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 anywhere and had a hunch as to what had happened. And in everyday decoding work, the same shortcoming could be exploited to discover which position within an encrypted text encoded a specific stretch of original text. How did this work?
The Bletchley Park team 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 standardised language. Identifying which individual was sending a message could further increase the predictability of its contents. This was sometimes possible if the sender transmitted Morse code with a distinctive rhythm, as well as by virtue of the fact that the preamble to each message contained an unencrypted call sign that identified which station was sending the message and which station was intended to receive it.
Recurring stretches of text like Nothing to report were called cribs. An analyst who thought 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 out its position 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.
Postulated correspondences between cribs and encoded letters were used to set up the bombe machines. Although there are a huge 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 the vast majority 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 nine to zero, this causes the tens column to advance as well; and when the tens column itself moves from nine to zero, 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 into which slots by observing statistical patterns in encoded texts that betrayed when the middle and leftmost rotors had 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 to vary how the machines were configured, it was 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 in the alphabet 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 elimination on any given day.
At the same time, the fear was absolutely founded that personnel under pressure would cut corners and fail to use the full range of possible setups effectively. Just like the Russians with their one-time pads, the office responsible for generating codebooks would sometimes reuse settings from previous months, which was a godsend to the analysts at Bletchley Park once they realised what was happening.
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. And because they had no way of knowing that their sloppiness was allowing others to eavesdrop, bad practice became ingrained as an unchecked habit.
The security of the system relied on the initial rotor positions for each message being chosen randomly. In reality, though, certain message transmitters – who we have seen 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. And as the other settings were valid for all messages sent by a particular group within the armed forces on a particular day, a small number of messages that had been encoded sloppily could end up allowing the Bletchley Park teams to decode 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: the physical act of setting a rotor’s wiring component tended to 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.
In fact, because the indicators were sent unencrypted, clusters of indicator values that were observed in the messages sent first thing in the morning immediately after the wiring components had been set to their new positions for the day greatly aided the Bletchley Park teams in the task of finding out those wiring component 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.
It took until 1974 for the Bletchley Park story to enter the public domain. The techniques that had been developed and applied to decipher messages had shown that the mere complexity of an encryption system was no guarantee it could not be cracked until a sufficient number of codebreakers had tried and failed. They had also demonstrated that even a theoretically secure method could only be relied upon if people were forced to use it as designed. These insights played a crucial role in informing the first modern encryption methods, which were developed and standardised shortly afterwards.
To read on about how modern encryption methods work, buy Cybertwists now!