by Simon Singh
Hans-Thilo Schmidt was born in 1888 in Berlin, the second son of a distinguished professor and his aristocratic wife. Schmidt embarked on a career in the German Army and fought in the First World War, but he was not considered worthy enough to remain in the army after the drastic cuts implemented as part of the Treaty of Versailles. He then tried to make his name as a businessman, but his soap factory was forced to close because of the postwar depression and hyperinflation, leaving him and his family destitute.
The humiliation of Schmidt’s failures was compounded by the success of his elder brother, Rudolph, who had also fought in the war, and who was retained in the army afterward. During the 1920s Rudolph rose through the ranks and was eventually promoted to chief of staff of the Signal Corps. He was responsible for ensuring secure communications, and in fact it was Rudolph who officially sanctioned the army’s use of the Enigma cipher.
After his business collapsed, Hans-Thilo was forced to ask his brother for help, and Rudolph arranged a job for him in Berlin at the Chiffrierstelle, the office responsible for administrating Germany’s encrypted communications. This was Enigma’s command center, a top-secret establishment dealing with highly sensitive information. When Hans-Thilo moved to his new job, he left his family behind in Bavaria, where the cost of living was affordable. He was living alone in expensive Berlin, impoverished and isolated, envious of his perfect brother and resentful toward a nation which had rejected him. The result was inevitable. By selling secret Enigma information to foreign powers, Hans-Thilo Schmidt could earn money and gain revenge, damaging his country’s security and undermining his brother’s organization.
On November 8, 1931, Schmidt arrived at the Grand Hotel in Verviers, Belgium, for a liaison with a French secret agent codenamed Rex. In exchange for 10,000 marks (equivalent to $30,000 in today’s money), Schmidt allowed Rex to photograph two documents: “Gebrauchsanweisung für die Chiffriermaschine Enigma” and “Schlüsselanleitung für die Chiffriermaschine Enigma.” These documents were essentially instructions for using the Enigma machine, and although there was no explicit description of the wirings inside each scrambler, they contained the information needed to deduce those wirings.
Figure 41 Hans-Thilo Schmidt. (photo credit 4.1)
Thanks to Schmidt’s treachery, it was now possible for the Allies to create an accurate replica of the German military Enigma machine. However, this was not enough to enable them to decipher messages encrypted by Enigma. The strength of the cipher depends not on keeping the machine secret, but on keeping the initial setting of the machine (the key) secret. If a cryptanalyst wants to decipher an intercepted message, then, in addition to having a replica of the Enigma machine, he still has to find which of the millions of billions of possible keys was used to encipher it. A German memorandum put it thus: “It is assumed in judging the security of the cryptosystem that the enemy has at his disposition the machine.”
The French Secret Service was clearly up to scratch, having found an informant in Schmidt, and having obtained the documents that suggested the wirings of the military Enigma machine. In comparison, French cryptanalysts were inadequate, and seemed unwilling and unable to exploit this newly acquired information. In the wake of the First World War they suffered from overconfidence and lack of motivation. The Bureau du Chiffre did not even bother trying to build a replica of the military Enigma machine, because they were convinced that achieving the next stage, finding the key required to decipher a particular Enigma message, was impossible.
As it happened, ten years earlier the French had signed an agreement of military cooperation with the Poles. The Poles had expressed an interest in anything connected with Enigma, so in accordance with their decade-old agreement the French simply handed the photographs of Schmidt’s documents to their allies, and left the hopeless task of cracking Enigma to the Biuro Szyfrów. The Biuro realized that the documents were only a starting point, but unlike the French they had the fear of invasion to spur them on. The Poles convinced themselves that there must be a shortcut to finding the key to an Enigma-encrypted message, and that if they applied sufficient effort, ingenuity and wit, they could find that shortcut.
As well as revealing the internal wirings of the scramblers, Schmidt’s documents also explained in detail the layout of the codebooks used by the Germans. Each month, Enigma operators received a new codebook which specified which key should be used for each day. For example, on the first day of the month, the codebook might specify the following day key:
(1) Plugboard settings: A/L-P/R-T/D-B/W-K/F-O/Y.
(2) Scrambler: arrangement: 2-3-1.
(3)Scrambler orientations: Q-C-W.
Together, the scrambler arrangement and orientations are known as the scrambler settings. To implement this particular day key, the Enigma operator would set up his Enigma machine as follows:
(1) Plugboard settings: Swap the letters A and L by connecting them via a lead on the plugboard, and similarly swap P and R, then T and D, then B and W, then K and F, and then O and Y.
(2) Scrambler arrangement: Place the 2nd scrambler in the 1st slot of the machine, the 3rd scrambler in the 2nd slot, and the 1st scrambler in the 3rd slot.
(3) Scrambler orientations: Each scrambler has an alphabet engraved on its outer rim, which allows the operator to set it in a particular orientation. In this case, the operator would rotate the scrambler in slot 1 so that Q is facing upward, rotate the scrambler in slot 2 so that C is facing upward, and rotate the scrambler in slot 3 so that W is facing upward.
One way of encrypting messages would be for the sender to encrypt all the day’s traffic according to the day key. This would mean that for a whole day at the start of each message all Enigma operators would set their machines according to the same day key. Then, each time a message needed to be sent, it would be first typed into the machine; the enciphered output would then be recorded, and handed to the radio operator for transmission. At the other end, the receiving radio operator would record the incoming message, hand it to the Enigma operator, who would type it into his machine, which would already be set to the same day key. The output would be the original message.
This process is reasonably secure, but it is weakened by the repeated use of a single day key to encrypt the hundreds of messages that might be sent each day. In general, it is true to say that if a single key is used to encipher an enormous quantity of material, then it is easier for a cryptanalyst to deduce it. A large amount of identically encrypted material provides a cryptanalyst with a correspondingly larger chance of identifying the key. For example, harking back to simpler ciphers, it is much easier to break a monoalphabetic cipher with frequency analysis if there are several pages of encrypted material, as opposed to just a couple of sentences.
As an extra precaution, the Germans therefore took the clever step of using the day key settings to transmit a new message key for each message. The message keys would have the same plugboard settings and scrambler arrangement as the day key, but different scrambler orientations. Because the new scrambler orientation would not be in the codebook, the sender had to transmit it securely to the receiver according to the following process. First, the sender sets his machine according to the agreed day key, which includes a scrambler orientation, say QCW. Next, he randomly picks a new scrambler orientation for the message key, say PGH. He then enciphers PGH according to the day key. The message key is typed into the Enigma twice, just to provide a double-check for the receiver. For example, the sender might encipher the message key PGHPGH as KIVBJE. Note that the two PGH’s are enciphered differently (the first as KIV, the second as BJE) because the Enigma scramblers are rotating after each letter, and changing the overall mode of encryption. The sender then changes his machine to the PGH setting and encrypts the main message according to this message key. At the receiver’s end, the machine is initially set according to the day key, QCW. The first six letters of the incoming message, KIVBJE, are typed in and reveal PGHPGH. The receiver then knows to reset his scrambler
s to PGH, the message key, and can then decipher the main body of the message.
This is equivalent to the sender and receiver agreeing on a main cipher key. Then, instead of using this single main cipher key to encrypt every message, they use it merely to encrypt a new cipher key for each message, and then encrypt the actual message according to the new cipher key. Had the Germans not employed message keys, then everything—perhaps thousands of messages containing millions of letters—would have been sent using the same day key. However, if the day key is only used to transmit the message keys, then it encrypts only a limited amount of text. If there are 1,000 message keys sent in a day, then the day key encrypts only 6,000 letters. And because each message key is picked at random and is used to encipher only one message, then it encrypts a limited amount of text, perhaps just a few hundred characters.
At first sight the system seemed to be impregnable, but the Polish cryptanalysts were undaunted. They were prepared to explore every avenue in order to find a weakness in the Enigma machine and its use of day and message keys. Foremost in the battle against Enigma was a new breed of cryptanalyst. For centuries, it had been assumed that the best cryptanalysts were experts in the structure of language, but the arrival of Enigma prompted the Poles to alter their recruiting policy. Enigma was a mechanical cipher, and the Biuro Szyfrów reasoned that a more scientific mind might stand a better chance of breaking it. The Biuro organized a course on cryptography and invited twenty mathematicians, each of them sworn to an oath of secrecy. The mathematicians were all from the university at Poznán. Although not the most respected academic institution in Poland, it had the advantage of being located in the west of the country, in territory that had been part of Germany until 1918. These mathematicians were therefore fluent in German.
Three of the twenty demonstrated an aptitude for solving ciphers, and were recruited into the Biuro. The most gifted of them was Marian Rejewski, a timid, spectacled twenty-three-year-old who had previously studied statistics in order to pursue a career in insurance. Although a competent student at the university, it was within the Biuro Szyfrów that he was to find his true calling. He served his apprenticeship by breaking a series of traditional ciphers before moving on to the more forbidding challenge of Enigma. Working entirely alone, he concentrated all of his energies on the intricacies of Scherbius’s machine. As a mathematician, he would try to analyze every aspect of the machine’s operation, probing the effect of the scramblers and the plugboard cablings. However, as with all mathematics, his work required inspiration as well as logic. As another wartime mathematical cryptanalyst put it, the creative codebreaker must “perforce commune daily with dark spirits to accomplish his feats of mental ju-jitsu.”
Rejewski’s strategy for attacking Enigma focused on the fact that repetition is the enemy of security: repetition leads to patterns, and cryptanalysts thrive on patterns. The most obvious repetition in the Enigma encryption was the message key, which was enciphered twice at the beginning of every message. If the operator chose the message key ULJ, then he would encrypt it twice so that ULJULJ might be enciphered as PEFNWZ, which he would then send at the start before the actual message. The Germans had demanded this repetition in order to avoid mistakes caused by radio interference or operator error. But they did not foresee that this would jeopardize the security of the machine.
Each day, Rejewski would find himself with a new batch of intercepted messages. They all began with the six letters of the repeated three-letter message key, all encrypted according to the same agreed day key. For example, he might receive four messages that began with the following encrypted message keys:
In each case, the 1st and 4th letters are encryptions of the same letter, namely the first letter of the message key. Also, the 2nd and 5th letters are encryptions of the same letter, namely the second letter of the message key, and the 3rd and 6th letters are encryptions of the same letter, namely the third letter of the message key. For example, in the first message L and R are encryptions of the same letter, the first letter of the message key. The reason why this same letter is encrypted differently, first as L and then as R, is that between the two encryptions the first Enigma scrambler has moved on three steps, changing the overall mode of scrambling.
The fact that L and R are encryptions of the same letter allowed Rejewski to deduce some slight constraint on the initial setup of the machine. The initial scrambler setting, which is unknown, encrypted the first letter of the day key, which is also unknown, into L, and then another scrambler setting, three steps on from the initial setting, which is still unknown, encrypted the same letter of the day key, which is also still unknown, into R.
This constraint might seem vague, as it is full of unknowns, but at least it demonstrates that the letters L and R are intimately related by the initial setting of the Enigma machine, the day key. As each new message is intercepted, it is possible to identify other relationships between the 1st and 4th letters of the repeated message key. All these relationships are reflections of the initial setting of the Enigma machine. For example, the second message above tells us that M and X are related, the third tells us that J and M are related, and the fourth that D and P are related. Rejewski began to summarize these relationships by tabulating them. For the four messages we have so far, the table would reflect the relationships between (L, R), (M, X), (J, M) and (D, P):
If Rejewski had access to enough messages in a single day, then he would be able to complete the alphabet of relationships. The following table shows such a completed set of relationships:
Figure 42 Marian Rejewski.
Rejewski had no idea of the day key, and he had no idea which message keys were being chosen, but he did know that they resulted in this table of relationships. Had the day key been different, then the table of relationships would have been completely different. The next question was whether there existed any way of determining the day key by looking at the table of relationships. Rejewski began to look for patterns within the table, structures that might indicate the day key. Eventually, he began to study one particular type of pattern, which featured chains of letters. For example, in the table, A on the top row is linked to F on the bottom row, so next he would look up F on the top row. It turns out that F is linked to W, and so he would look up W on the top row. And it turns out that W is linked to A, which is where we started. The chain has been completed.
With the remaining letters in the alphabet, Rejewski would generate more chains. He listed all the chains, and noted the number of links in each one:
So far, we have only considered the links between the 1st and 4th letters of the six-letter repeated key. In fact, Rejewski would repeat this whole exercise for the relationships between the 2nd and 5th letters, and the 3rd and 6th letters, identifying the chains in each case and the number of links in each chain.
Rejewski noticed that the chains changed each day. Sometimes there were lots of short chains, sometimes just a few long chains. And, of course, the letters within the chains changed. The characteristics of the chains were clearly a result of the day key setting-a complex consequence of the plugboard settings, the scrambler arrangement and the scrambler orientations. However, there remained the question of how Rejewski could determine the day key from these chains. Which of 10,000,000,000,000,000 possible day keys was related to a particular pattern of chains? The number of possibilities was simply too great.
It was at this point that Rejewski had a profound insight. Although the plugboard and scrambler settings both affect the details of the chains, their contributions can to some extent be disentangled. In particular, there is one aspect of the chains which is wholly dependent on the scrambler settings, and which has nothing to do with the plugboard settings: the numbers of links in the chains is purely a consequence of the scrambler settings. For instance, let us take the example above and pretend that the day key required the letters S and G to be swapped as part of the plugboard settings. If we change this element of the day key, by removing the cable tha
t swaps S and G, and use it to swap, say, T and K instead, then the chains would change to the following:
Some of the letters in the chains have changed, but, crucially, the number of links in each chain remains constant. Rejewski had identified a facet of the chains that was solely a reflection of the scrambler settings.
The total number of scrambler settings is the number of scrambler arrangements (6) multiplied by the number of scrambler orientations (17,576) which comes to 105,456. So, instead of having to worry about which of the 10,000,000,000,000,000 day keys was associated with a particular set of chains, Rejewski could busy himself with a drastically simpler problem: which of the 105,456 scrambler settings was associated with the numbers of links within a set of chains? This number is still large, but it is roughly one hundred billion times smaller than the total number of possible day keys. In short, the task has become one hundred billion times easier, certainly within the realm of human endeavor.
Rejewski proceeded as follows. Thanks to Hans-Thilo Schmidt’s espionage, he had access to replica Enigma machines. His team began the laborious chore of checking each of 105,456 scrambler settings, and cataloguing the chain lengths that were generated by each one. It took an entire year to complete the catalogue, but once the Biuro had accumulated the data, Rejewski could finally begin to unravel the Enigma cipher.