by Simon Singh
Figure 45 Bletchley’s codebreakers relax with a game of rounders.
Once they had mastered the Polish techniques, the Bletchley cryptanalysts began to invent their own shortcuts for finding the Enigma keys. For example, they cottoned on to the fact that the German Enigma operators would occasionally choose obvious message keys. For each message, the operator was supposed to select a different message key, three letters chosen at random. However, in the heat of battle, rather than straining their imaginations to pick a random key, the overworked operators would sometimes pick three consecutive letters from the Enigma keyboard (Figure 46), such as QWE or BNM. These predictable message keys became known as cillies. Another type of cilly was the repeated use of the same message key, perhaps the initials of the operator’s girlfriend—indeed, one such set of initials, C.I.L., may have been the origin of the term. Before cracking Enigma the hard way, it became routine for the cryptanalysts to try out the cillies, and their hunches would sometimes pay off.
Cillies were not weaknesses of the Enigma machine, rather they were weaknesses in the way the machine was being used. Human error at more senior levels also compromised the security of the Enigma cipher. Those responsible for compiling the codebooks had to decide which scramblers would be used each day, and in which positions. They tried to ensure that the scrambler settings were unpredictable by not allowing any scrambler to remain in the same position for two days in a row. So, if we label the scramblers 1, 2, 3, 4 and 5, then on the first day it would be possible to have the arrangement 134, and on the second day it would be possible to have 215, but not 214, because scrambler number 4 is not allowed to remain in the same position for two days in a row. This might seem a sensible strategy because the scramblers are constantly changing position, but enforcing such a rule actually makes life easier for the cryptanalyst. Excluding certain arrangements to avoid a scrambler remaining in the same position meant that the codebook compilers reduced by half the number of possible scrambler arrangements. The Bletchley cryptanalysts realized what was happening and made the most of it. Once they identified the scrambler arrangement for one day, they could immediately rule out half the scrambler arrangements for the next day. Hence, their workload was reduced by half.
Figure 46 Layout of the Enigma keyboard.
Similarly, there was a rule that the plugboard settings could not include a swap between any letter and its neighbor, which meant that S could be swapped with any letter except R and T. The theory was that such obvious swappings should be deliberately avoided, but once again the implementation of a rule drastically reduced the number of possible keys.
This search for new cryptanalytic shortcuts was necessary because the Enigma machine continued to evolve during the course of the war. The cryptanalysts were continually forced to innovate, to redesign and refine the bombes, and to devise wholly new strategies. Part of the reason for their success was the bizarre combination of mathematicians, scientists, linguists, classicists, chess grandmasters and crossword addicts within each hut. An intractable problem would be passed around the hut until it reached someone who had the right mental tools to solve it, or reached someone who could at least partially solve it before passing it on again. Gordon Welchman, who was in charge of Hut 6, described his team as “a pack of hounds trying to pick up the scent.” There were many great cryptanalysts and many significant breakthroughs, and it would take several large volumes to describe the individual contributions in detail. However, if there is one figure who deserves to be singled out, it is Alan Turing, who identified Enigma’s greatest weakness and ruthlessly exploited it. Thanks to Turing, it became possible to crack the Enigma cipher under even the most difficult circumstances.
Alan Turing was conceived in the autumn of 1911 in Chatrapur, a town near Madras in southern India, where his father Julius Turing was a member of the Indian civil service. Julius and his wife Ethel were determined that their son should be born in Britain, and returned to London, where Alan was born on June 23, 1912. His father returned to India soon afterward and his mother followed just fifteen months later, leaving Alan in the care of nannies and friends until he was old enough to attend boarding school.
In 1926, at the age of fourteen, Turing became a pupil at Sherborne School, in Dorset. The start of his first term coincided with the General Strike, but Turing was determined to attend the first day, and he cycled 100 km unaccompanied from Southampton to Sherborne, a feat that was reported in the local newspaper. By the end of his first year at the school he had gained a reputation as a shy, awkward boy whose only skills were in the area of science. The aim of Sherborne was to turn boys into well-rounded men, fit to rule the Empire, but Turing did not share this ambition and had a generally unhappy schooling.
His only real friend at Sherborne was Christopher Morcom, who, like Turing, had an interest in science. Together they discussed the latest scientific news and conducted their own experiments. The relationship fired Turing’s intellectual curiosity, but, more importantly, it also had a profound emotional effect on him. Andrew Hodges, Turing’s biographer, wrote that “This was first love … It had that sense of surrender, and a heightened awareness, as of brilliant color bursting upon a black and white world.” Their friendship lasted four years, but Morcom seems to have been unaware of the depth of feeling Turing had for him. Then, during their final year at Sherborne, Turing lost forever the chance to tell him how he felt. On Thursday, February 13, 1930, Christopher Morcom suddenly died of tuberculosis.
Turing was devastated by the loss of the only person he would ever truly love. His way of coming to terms with Morcom’s death was to focus on his scientific studies in an attempt to fulfill his friend’s potential. Morcom, who appeared to be the more gifted of the two boys, had already won a scholarship to Cambridge University. Turing believed it was his duty also to win a place at Cambridge, and then to make the discoveries his friend would otherwise have made. He asked Christopher’s mother for a photograph, and when it arrived he wrote back to thank her: “He is on my table now, encouraging me to work hard.”
In 1931, Turing gained admission to King’s College, Cambridge. He arrived during a period of intense debate about the nature of mathematics and logic, and was surrounded by some of the leading voices, such as Bertrand Russell, Alfred North Whitehead and Ludwig Wittgenstein. At the center of the argument was the issue of undecidability, a controversial notion developed by the logician Kurt Gödel. It had always been assumed that, in theory at least, all mathematical questions could be answered. However, Gödel demonstrated that there could exist a minority of questions which were beyond the reach of logical proof, so-called undecidable questions. Mathematicians were traumatized by the news that mathematics was not the all-powerful discipline they had always believed it to be. They attempted to salvage their subject by trying to find a way of identifying the awkward undecidable questions, so that they could put them safely to one side. It was this objective that eventually inspired Turing to write his most influential mathematical paper, “On Computable Numbers,” published in 1937. In Breaking the Code, Hugh Whitemore’s play about the life of Turing, a character asks Turing the meaning of his paper. He replies, “It’s about right and wrong. In general terms. It’s a technical paper in mathematical logic, but it’s also about the difficulty of telling right from wrong. People think—most people think—that in mathematics we always know what is right and what is wrong. Not so. Not any more.”
Figure 47 Alan Turing. (photo credit 4.4)
In his attempt to identify undecidable questions, Turing’s paper described an imaginary machine that was designed to perform a particular mathematical operation, or algorithm. In other words, the machine would be capable of running through a fixed, prescribed series of steps which would, for example, multiply two numbers. Turing envisaged that the numbers to be multiplied could be fed into the machine via a paper tape, rather like the punched tape that is used to feed a tune into a Pianola. The answer to the multiplication would be output via another tape
. Turing imagined a whole series of these so-called Turing machines, each specially designed to tackle a particular task, such as dividing, squaring or factoring. Then Turing took a more radical step.
He imagined a machine whose internal workings could be altered so that it could perform all the functions of all conceivable Turing machines. The alterations would be made by inserting carefully selected tapes, which transformed the single flexible machine into a dividing machine, a multiplying machine, or any other type of machine. Turing called this hypothetical device a universal Turing machine because it would be capable of answering any question that could logically be answered. Unfortunately, it turned out that it is not always logically possible to answer a question about the undecidability of another question, and so even the universal Turing machine was unable to identify every undecidable question.
Mathematicians who read Turing’s paper were disappointed that Gödel’s monster had not been subdued but, as a consolation prize, Turing had given them the blueprint for the modern programmable computer. Turing knew of Babbage’s work, and the universal Turing machine can be seen as a reincarnation of Difference Engine No. 2. In fact, Turing had gone much further, and provided computing with a solid theoretical basis, imbuing the computer with a hitherto unimaginable potential. It was still the 1930s though, and the technology did not exist to turn the universal Turing machine into a reality. However, Turing was not at all dismayed that his theories were ahead of what was technically feasible. He merely wanted recognition from within the mathematical community, who indeed applauded his paper as one of the most important breakthroughs of the century. He was still only twenty-six.
This was a particularly happy and successful period for Turing. During the 1930s he rose through the ranks to become a fellow of King’s College, home of the world’s intellectual elite. He led the life of an archetypal Cambridge don, mixing pure mathematics with more trivial activities. In 1938 he made a point of seeing the film Snow White and the Seven Dwarfs, containing the memorable scene in which the Wicked Witch dunks an apple in poison. Afterward his colleagues heard Turing continually repeating the macabre chant, “Dip the apple in the brew, Let the sleeping death seep through.”
Turing cherished his years at Cambridge. In addition to his academic success, he found himself in a tolerant and supportive environment. Homosexuality was largely accepted within the university, which meant that he was free to engage in a series of relationships without having to worry about who might find out, and what others might say. Although he had no serious long-term relationships, he seemed to be content with his life. Then, in 1939, Turing’s academic career was brought to an abrupt halt. The Government Code and Cypher School invited him to become a cryptanalyst at Bletchley, and on September 4, 1939, the day after Neville Chamberlain declared war on Germany, Turing moved from the opulence of the Cambridge quadrangle to the Crown Inn at Shenley Brook End.
Each day he cycled 5 km from Shenley Brook End to Bletchley Park, where he spent part of his time in the huts contributing to the routine codebreaking effort, and part of his time in the Bletchley think tank, formerly Sir Herbert Leon’s apple, pear and plum store. The think tank was where the cryptanalysts brainstormed their way through new problems, or anticipated how to tackle problems that might arise in the future. Turing focused on what would happen if the German military changed their system of exchanging message keys. Bletchley’s early successes relied on Rejewski’s work, which exploited the fact that Enigma operators encrypted each message key twice (for example, if the message key was YGB, the operator would encipher YGBYGB). This repetition was supposed to ensure that the receiver did not make a mistake, but it created a chink in the security of Enigma. British cryptanalysts guessed it would not be long before the Germans noticed that the repeated key was compromising the Enigma cipher, at which point the Enigma operators would be told to abandon the repetition, thus confounding Bletchley’s current codebreaking techniques. It was Turing’s job to find an alternative way to attack Enigma, one that did not rely on a repeated message key.
As the weeks passed, Turing realized that Bletchley was accumulating a vast library of decrypted messages, and he noticed that many of them conformed to a rigid structure. By studying old decrypted messages, he believed he could sometimes predict part of the contents of an undeciphered message, based on when it was sent and its source. For example, experience showed that the Germans sent a regular enciphered weather report shortly after 6 A.M. each day. So, an encrypted message intercepted at 6:05 A.M. would be almost certain to contain wetter, the German word for “weather.” The rigorous protocol used by any military organization meant that such messages were highly regimented in style, so Turing could even be confident about the location of wetter within the encrypted message. For example, experience might tell him that the first six letters of a particular ciphertext corresponded to the plaintext letters wetter. When a piece of plaintext can be associated with a piece of ciphertext, this combination is known as a crib.
Turing was sure that he could exploit the cribs to crack Enigma. If he had a ciphertext and he knew that a specific section of it, say ETJWPX, represented wetter, then the challenge was to identify the settings of the Enigma machine that would transform wetter into ETJWPX. The straightforward, but impractical, way to do this would be for the cryptanalyst to take an Enigma machine, type in wetter and see if the correct ciphertext emerged. If not, then the cryptanalyst would change the settings of the machine, by swapping plugboard cables, and swapping or reorienting scramblers, and then type in wetter again. If the correct ciphertext did not emerge, the cryptanalyst would change the settings again, and again, and again, until he found the right one. The only problem with this trial and error approach was the fact that there were 159,000,000,000,000,000,000 possible settings to check, so finding the one that transformed wetter into ETJWPX was a seemingly impossible task.
To simplify the problem, Turing attempted to follow Rejewski’s strategy of disentangling the settings. He wanted to divorce the problem of finding the scrambler settings (finding which scrambler is in which slot, and what their respective orientations are) from the problem of finding the plugboard cablings. For example, if he could find something in the crib that had nothing to do with the plugboard cablings, then he could feasibly check each of the remaining 1,054,560 possible scrambler combinations (60 arrangements × 17,576 orientations). Having found the correct scrambler settings, he could then deduce the plugboard cablings.
Eventually, his mind settled on a particular type of crib which contained internal loops, similar to the chains exploited by Rejewski. Rejewski’s chains linked letters within the repeated message key. However, Turing’s loops had nothing to do with the message key, as he was working on the assumption that soon the Germans would stop sending repeated message keys. Instead, Turing’s loops connected plaintext and ciphertext letters within a crib. For example, the crib shown in Figure 48 contains a loop.
Figure 48 One of Turing’s cribs, showing a loop.
Remember, cribs are only guesses, but if we assume that this crib is correct, we can link the letters W→E, e→T, t→W as part of a loop. Although we know none of the Enigma machine settings, we can label the first setting, whatever it is, S. In this first setting we know that w is encrypted as E. After this encryption, the first scrambler clicks around one place to setting S+1, and the letter e is enciphered as T. The scrambler clicks forward another place and encrypts a letter that is not part of the loop, so we ignore this encryption. The scrambler clicks forward one more place and, once again, we reach a letter that is part of the loop. In setting S+3, we know that the letter t is enciphered as W. In summary, we know that
In setting S, Enigma encrypts w as E.
In setting S+1, Enigma encrypts e as T.
In setting S+3, Enigma encrypts t as W.
So far the loop seems like nothing more than a curious pattern, but Turing rigorously followed the implications of the relationships within the loop, and saw that the
y provided him with the drastic shortcut he needed in order to break Enigma. Instead of working with just one Enigma machine to test every setting, Turing began to imagine three separate machines, each dealing with the encipherment of one element of the loop. The first machine would try to encipher w into E, the second would try to encipher e into T, and the third t into W. The three machines would all have identical settings, except that the second would have its scrambler orientations moved forward one place with respect to the first, a setting labeled S+1, and the third would have its scrambler orientations moved forward three places with respect to the first, a setting labeled S+3. Turing then pictured a frenzied cryptanalyst, continually changing plugboard cables, swapping scrambler arrangements and changing their orientations in order to achieve the correct encryptions. Whatever cables were changed in the first machine would also be changed in the other two. Whatever scrambler arrangements were changed in the first machine would also be changed in the other two. And, crucially, whatever scrambler orientation was set in the first machine, the second would have the same orientation but stepped forward one place, and the third would have the same orientation but stepped forward three places.
Turing does not seem to have achieved much. The cryptanalyst still has to check all 159,000,000,000,000,000,000 possible settings, and, to make matters worse, he now has to do it simultaneously on all three machines instead of just one. However, the next stage of Turing’s idea transforms the challenge, and vastly simplifies it. He imagined connecting the three machines by running electrical wires between the inputs and the outputs of each machine, as shown in Figure 49. In effect, the loop in the crib is paralleled by the loop of the electrical circuit. Turing pictured the machines changing their plugboard and scrambler settings, as described above, but only when all the settings are correct for all three machines would the circuit be completed, allowing a current to flow through all three machines. If Turing incorporated a lightbulb within the circuit, then the current would illuminate it, signaling that the correct settings had been found. At this point, the three machines still have to check up to 159,000,000,000,000,000,000 possible settings in order to illuminate the bulb. However, everything done so far has merely been preparation for Turing’s final logical leap, which would make the task over a hundred million million times easier in one fell swoop.