by Kahn, David
This remarkable paper had two results. It demonstrated that a fundamental problem in mathematics, the so-called Entscheidungsproblem—ascertaining whether certain problems could be solved—was not soluble. And, as became evident only later, the imagined device, eventually called a “universal Turing machine,” was the idealization of general-purpose computers. Turing became, in other words, the intellectual father of the computer.
An American mathematician at Princeton had also been working on the Entscheidungsproblem, and Turing spent the academic years 1936–37 and 1937–38 at that university earning a doctorate. While there he frequently discussed ciphers, to which he had been attracted since he was a boy. He claimed to have found an answer to the question “What is the most general kind of code or cipher possible?” If he talked about cryptology at the King’s College high table, he may have been recognized as a natural recruit by those Room 40 veterans who either were still fellows of or retained close ties with King’s. This recognition perhaps led to an invitation to join the course in cryptology, which ran for a week or two at Broadway Buildings. Though many of the other students were mathematicians, a few linguists, including German scholars, also attended. The course may have been more than instructional. When the charming Oliver Strachey took the young men out and gave them a very good lunch at the Travellers Club, it struck one of them that the course sought as much to let the G.C.&C.S. hierarchs look over the recruits as to teach them cryptology.
Even though the war scare preceding the Munich pact in September had been followed by Chamberlain’s promise of “peace for our time,” G.C.&C.S. had Turing and others come down to London for a second course around Christmas of 1938. Afterward, he visited G.C.&C.S. every few weeks to help Knox, presumably in his attack on the Enigma.
In February 1939 G.C.&C.S. advertised for a “signals computer.” A lean young Oxford graduate in mathematics applied. Peter Twinn hadn’t the foggiest notion what the work entailed—and his interviewer talked all around it—but jobs were then hard to come by. Twinn was hired, together with another mathematician, J. C. T. Dryden, and in mid-February 1939 they reported to Broadway Buildings. When G.C.&C.S. moved to Bletchley Park in August, Twinn found himself working as a cryptanalyst side by side with Knox in the Cottage.
On September 3, Turing, in his room at Cambridge, heard Chamberlain intone on the wireless that the expiration of Britain’s ultimatum to Hitler to withdraw his forces from Poland meant that Britain was at war with Germany. The next day, he reported to Bletchley, where he joined Knox, Twinn, and a Cambridge mathematician, John R. F. Jeffreys, in working on the Enigma. He found, as Twinn and Jeffreys had before him, that the continuing recovery of the Enigma keys was being achieved mainly by bright ideas, not by mathematics. It was, however, mathematicians who were having the ideas, thus at least partially vindicating Denniston’s faith.
The most important breakthrough, an idea of Turing’s, came late in 1939. It dealt with the Polish mechanism for testing for possible Enigma keys, the bombe, which the Poles had displayed to Knox at the July meeting in Warsaw but whose technical description had not arrived in England until August 16, just three weeks before Turing came to Bletchley. Turing was especially well equipped to work on this electromechanical device, for, though most of his work was theoretical, he was mechanically apt. He had once made an electric multiplier (for use in a cipher system he invented), machining and winding some of the relays himself, and had later designed a mechanism to answer a problem dealing with prime numbers, cutting some of the gears himself.
Turing had reached some of his most important conclusions by eliminating results that led to self-contradictions. If the Entscheidungsproblem can be solved, he had written, “then there is a general (mechanical) process for determining whether Un (M) is provable. By Lemmas 1 and 2, this implies that there is a process for determining whether M ever prints 0 and this is impossible, by §8. Hence the Entscheidungsproblem cannot be solved.” He now applied the same sort of thinking to the Enigma.
He recognized that the Polish machine helped to identify keys by asking, in mathematical terms, whether the enciphered message keys of the cryptogram were consistent with the unknown basic setting that was wanted. The bombe actually did this by rejecting the thousands of inconsistencies and leaving the few noncontradictory situations to be tested to see whether their settings yielded German when applied to the intercepts. Turing advanced this testing method by a giant step.
A basic technique in cryptanalysis is that of the probable word. The cryptanalyst guesses that a particular word or phrase exists in the plaintext of a cryptogram—perhaps “enemy” or “attack” in a message transmitted after a military unit has been under assault—and employs it as a wedge to recover the full text and possibly the key of the cryptogram. The Poles had used this method in a limited area before they had bombes: to reduce the number of trials in finding the positions of the alphabet rings on the rotors, they assumed that the German military message they were attacking began with An, or “To,” followed by the letter X, which separated words. Turing shifted the focus of this technique and endowed it with vast new power. He matched a probable word or phrase (longer than AnX) to a portion of an intercept and tested whether any rotor position allowed such an encipherment. He moved, in other words, from speeding the recovery of keys by finding noncontradictory links between the known and the assumed keys to speeding the recovery of keys by finding noncontradictory links between assumed plaintext and assumed keys.
His bombe did this by adding to the multiplicity of Enigma replicas a test register, a set of twenty-six relays. At each of the successive rotor positions the bombe was running through, this test register looked at the voltage at each of the twenty-six points equivalent to the output lights of the Enigma’s illuminable panel. Two conditions—voltage appearing at all twenty-six points or at all but one—represented a noncontradiction between the assumed plaintext and the then position of the rotors. This position thus constituted a possible key, and clerks would see if it produced German plaintext. If it did not, the bombe would be restarted.
The work began with cryptanalysts imagining the possible plaintext of a message, which they called a crib. They made these guesses on the basis of their knowledge of German communications, gained through direction-finding, radiomen’s chatter, service messages, plaintext intercepts, solutions of simpler systems, captured documents, prisoner interrogations, and previous Enigma solutions that used other principles. Suppose they learned that a Luftwaffe headquarters sent a report every day at 4 P.M. to the general of reconnaissance; they could guess that its messages started Dem General der Aufklaerungsflieger. A navy communications outpost was ordered to report every day to a central radio post the strength at which the signal was being received. An army unit repeatedly transmitted Nichts zu melden (“Nothing to report”).
The crib would be set letter for letter above the ciphertext. The cryptanalyst then sought a loop: letters in the assumed plaintext and in the ciphertext that could be chained together, eventually linking the first letter to the last. For example,
links the m in the upper line to the E below, one of the e’s above to an L below, and an l above to an M below, thus forming the loop M E L M. The bombe was set up in the basic position, with rotors I, II, and III, in that order, set at A A A. (The ring positions were ignored, and the cryptanalyst hoped that the middle rotor would not step within the crib.) The plugboard positions were as unknown as the rotor order and position.
Voltage was then applied to the bombe position representing one of the twenty-six possible plugboard substitutions for the first letter of the crib. It went through the bombe’s rotor array, into and back out through the reflecting rotor, back through the rotor array, then into the rotor array that was testing the second plain-cipher pair of the loop and was advanced by the number of places by which the first and second pairs differed in the text: the E-L pair in the crib is two places further on than M-E, so the rightmost, or fast, rotor of the second arra
y has to be two clicks beyond the fast rotor of the first array. The voltage emerged from this array to pass through a third and then loop back into the first.
As it did so, the voltage passed through the test register. Suppose that the arrangement of rotors was correct and the choice of plugboard substitutions was correct. The voltage would make a single circuit through the rotors and show up at only one test point—one of the two conditions for a correct match. The relay would electromechanically interrupt the power to the bombe and stop it, enabling the cryptanalysts to ascertain this rotor position and use it to decipher the cryptogram to see if German plaintext appeared. Because of the plugboard, the test decipherment would include many cipher substitutes for plaintext letters, but it should retain enough of a German appearance to test its validity. The cryptanalyst would have to recover the plaintext by solution.
Suppose, however, that the arrangement of rotors was wrong. The voltage would pass through the first rotor array, come out at a letter that would not complete a loop, enter the second rotor at a non-loop point, pass through it, and emerge again at a nonloop letter that would send it into a third rotor array. The voltage would continue its errant course through the bombe’s several rotor arrays—as many as letters in the crib—nearly always emerging at all twenty-six letters and putting voltage on all twenty-six relays of the test register. But this is not one of the patterns that would stop the machine. So the bombe would continue to run, searching for a position at which to stop. Suppose, finally, that the arrangement of rotors was correct but the choice of plugboard substitution was not. In this case, the voltage would spread out among the test pins, as in the case of an incorrect rotor arrangement, but would not be able to enter the one correct test pin. This would produce the second, more likely, correct condition, with voltage to all test relays except one, and the bombe would stop.
Turing’s method had two advantages over the Poles’. It liberated the cryptanalysts from the need to find special conditions among the message keys, namely, the repeated letters in certain positions that the Polish cryptanalysts had called females. And it could look for help in the vast ranges of human endeavor distilled by messages, thus improving the chances that a message would be solved and increasing the volume of solutions.
But the method had not reached its full potential. A way of doing that was discovered totally unexpectedly by another Cambridge mathematician, Gordon Welchman. A chess player, but not a very good one, and a tennis player, even worse, he was a sturdily built man of thirty-four, of medium height with very pink cheeks, wavy hair, and dashing good looks. But he was austere and reserved and was regarded even by his friends as “a solemn old stick, without a great sense of humor.” Welchman had attended Trinity College, Cambridge, on a mathematics scholarship and after his 1928 graduation had taught mathematics at another Cambridge college, Sidney Sussex. He specialized in algebraic geometry.
Like Turing, Welchman had attended the introductory course in cryptology and had reported to Bletchley Park upon the outbreak of war. Denniston sent him to the Cottage, where he joined the group working on the Enigma under Knox. Welchman soon got the impression that Knox didn’t like him—indeed, he soon concluded that Knox didn’t like most people—and within a couple of weeks he had been exiled to another building, Elmers School, with another assignment. He was to study the externals of the intercepted German army messages—the radio frequencies on which they were sent, their call signs, message indicators, signatures, and addresses—to deduce what information he could from any patterns he found. To help with this, he was given a sheaf of solved Enigma intercepts.
Welchman quickly perceived that the traffic patterns reflected the organization of the German army. “The call signs came alive,” he said, “as representing elements of those forces whose commanders at various echelons would have to send messages to each other. The use of different keys … suggested different command structures.” He was independently inventing a form of intelligence called traffic analysis. He rapidly perceived the stereotyped nature of many of the addresses, text beginnings, and even whole messages, and wondered whether they could not be used as cribs. He was reinventing Turing’s method of ascertaining a valid key. And, quickly spotting many of the same patterns and characteristics in the message indicators that Rejewski and his colleagues had found, he proposed using perforated sheets to narrow down the possible rotor orders and ring settings. He was reinventing the Zygalski sheets, which had, unknown to him, been adopted by G.C.&C.S. and named Jeffreys sheets after John Jeffreys, who was in charge of preparing them.
But Welchman, who had independently duplicated two of the most important ideas of Enigma cryptanalysis and one of the fundamentals of radio intelligence, was not doomed always to walk in the shadow of others. Before the war was three months old, his brilliance augmented the power of Turing’s bombe and greatly accelerated the pace of Enigma solutions.
His method was based on the fact that Enigma substitutions were reciprocal. If plaintext r became ciphertext P at a particular rotor order and position and with particular plugboard connections, then plaintext p would become ciphertext R at the same setting. Welchman employed this principle to exploit the letters of a crib that did not form part of a loop. He set out, on a wooden board, a square array of 676 contacts lettered A to Z across the top and A to Z down the side. Then he connected by wires the contact in, say, row D and column F to the contact in row F and column D. All 676 contacts were thus wired. As a consequence, when the crib gave plaintext p and ciphertext R, the diagonal board automatically sent the voltage for ciphertext P and plaintext r through the rotor arrays. This reduced the number of erroneous stops.
Once Turing had sketched out the plan for his bombe, Commander Edward Travis, the bulldoglike deputy head of G.C.&C.S., began discussions with the British Tabulating Machine Company. The company named as its representative Harold (Doc) Keen, a friendly, talkative engineer who had often visited the International Business Machines Corporation in the United States. At one meeting, at the White Hart Pub in Buckingham, Peter Twinn summarized the concept to Keen by saying that what was needed was a machine like forty Enigmas in a row. Keen also rapidly grasped Welchman’s idea and incorporated the diagonal board into the British bombes. The main frame was about 4 feet wide and as tall as a man; it was supported on short legs that rolled on casters. Each bombe consisted of the equivalent of twelve Enigma machines (the two prototypes had only ten) plus a diagonal board. The face of each bombe was divided into six stacks of two horizontal rectangles; in each rectangle were mounted three wired wheels, each about 5 inches across. They emulated Enigma rotors but differed from them in that the current flowed not through them but across them: from an outer ring of contacts to an inner ring, both on the face plate of the bombe. Each vertical set of three rotors represented an Enigma with a different rotor choice and order. Five bombes would thus represent all sixty rotor possibilities. The wheels stepped as did the rotors, except that the lack of knowledge of the ring position introduced discrepancies that caused some accurate crib superimpositions to be rejected as not possible.
Behind the face of the bombe was the machinery that drove it, turning all the upper wheels together, all the middle wheels together and all the lower wheels together. The back of the bombe, which opened to give access to the mass of circuitry within, served as a frame for the diagonal board. Keen’s two prototypes, built in part out of punched-card machinery, proved extremely flexible, largely because Keen’s long experience with punched-card equipment had taught him that it was often used to perform tasks not envisioned when it was designed.
The first Turing bombe was installed in Bletchley Park’s Hut 11 on the 8th of August, 1940. Named AGNES, it became a prototype for machines superior to the sorters used by Germany for codebreaking.
The Government Code & Cypher School expanded rapidly, a phantom agency exercising apparently spectral powers. Its organization reflected that of the enemy whose cryptosystems were being read, because those cryptosys
tems varied according to the needs and usages of the services that employed them. Thus G.C.&C.S. Naval Section dealt with foreign naval intercepts, and other sections worked on foreign army, air force, and diplomatic intercepts. The military and naval sections each evolved into two parts: cryptanalysis, which cracked the cryptograms, and intelligence, which extracted information from the solved intercepts. These teams were soon known better by the number of their hut than by their formal organizational name.
The naval cryptanalysts, headed by Turing, worked in Hut 8. Seated at cheap wooden desks, they spent their time guessing at possible cribs, looking for loops, and testing them on the bombes; they did sums, drew diagrams, printed letters. They seldom spoke, though occasionally one might express some emotion in a reserved British way. Next to them in Hut 4 were the naval intelligence analysts, who translated and appended comments to the solved intercepts. Hut 3 housed the cryptanalysts solving the German army and air force intercepts; Hut 6, the analysts for these solutions.
The advances made by Turing and Welchman had left Knox far behind; he remained in the Cottage working on the Enigmas without plugboards used by the Italian navy and by Abwehr, the German high command’s espionage service. The solutions that his little group produced were designated ISK, for Intelligence Service Knox.
Some of the higher positions of this growing organization were filled by Room 40 veterans summoned from their civilian occupations. Nigel de Grey, a solver of the Zimmermann telegram that helped bring the United States into World War I, a man barely five feet tall and given to wearing fawn-colored trousers, returned from the publishing world as a deputy director. Frank Adcock, a round-faced, secretive classics scholar at King’s College with a way of telling a joke and then cocking his head while waiting for the laugh, returned in 1939. The pantomimist Frank Birch, forty-nine, also a fellow of King’s, came back to head Naval Section. He had taught history at Cambridge from 1921 to 1928, where his histrionic gifts made his lectures extraordinarily vivid. He quit academe to act in and produce plays in London. Of medium height, with close-set eyes in a mobile face, he was a very good comic actor and very good company, very amusing—when he wasn’t working.
