Alan Turing: The Enigma: The Book That Inspired the Film The Imitation Game

by Andrew Hodges

  This was not the only method they devised. The perforated sheet system required the location of about ten females in the traffic. A second system required only three, but it used not only the mere existence of a female, but the particular letter that appeared as female in the cipher-text. It was essential to the principle of the method that these particular letters had to be among those left unaffected by the plugboard. Since in 1938 the plugboard was being used with only six or seven pairs connected up, this was not too stringent a requirement.

  The principle of this method was to match the observed pattern of three particular female letters, against the properties of the core positions. But it was impossible to catalogue in advance all the female letters of 6 × 17576 positions, and then perform a search, even by staggering sheets. There were far too many possible cases. Instead, they took a radical new step. They would search through the properties of the rotor positions afresh each time, doing no advance cataloguing. But this would not be a human search. It would be done by a machine. By November 1938 they had actually built such machines – six in fact, one for each possible rotor order. They produced a loud ticking sound, and were accordingly called the Bombes.

  The Bombes exploited the electrical circuitry of the Enigma machine, by using an electrical method of recognising when a ‘matching’ had been found. The very fact that the Enigma was a machine, made mechanical cryptanalysis a possibility. The essential idea was that of wiring up six copies of the basic Enigma, in such a way that a circuit closed when the three particular ‘females’ occurred. The relative core-positions of these six Enigmas would be fixed by the known relative settings of the ‘females’ – just as in the ‘staggering’ of the sheets. Keeping these relative positions constant, the Enigmas would then be driven through every possible position. The complete search could be made in two hours, meaning that several positions could be tested in each second. It was a brute force method, for all it did was naively to try out all the possibilities one after the other. It had no algebraic subtlety. Yet it brought cryptanalysis into the twentieth century.

  Unfortunately for the Polish analysts, the Germans were slightly further ahead in the twentieth century, and no sooner had this electromechanical device been brought to bear on the Enigma, than a new complication rendered it powerless again. In December 1938, the German systems all augmented their stock of three rotors, to a repertoire of five. Instead of six choices of ordering the rotors, there were now sixty. The Polish analysts did not lack for enterprise, and succeeded in working out the new wirings, thanks to cryptographic mistakes made by the self-styled German Security Service, the SD. But the arithmetic was simple. Instead of six Bombes, the method would now require sixty. Instead of six sets of perforated sheets, it would require sixty. They were lost. And this was the position when the British and French delegations went to Warsaw in July 1939. The Poles did not have the technical resources for further development.

  This was the story that Alan heard. It was a story that had ground to a halt, but even so, the Poles were years ahead of the British, who were still where they had been in 1932. The British had not been able to work out the wirings, nor had they established the fact that the keyboard was connected to the first rotor in a simple order. Like the Polish cryptanalysts, they assumed that its design would include another jumbling operation at this point, and were amazed to learn that it did not. Nor had GC and CS ever thought of ‘the possibility of high-speed machine testing against the Enigma before the July 1939 meeting’. At some level, there had been a failure of will. They had not really wanted to think, had not really wanted to know. Now that particular hurdle was passed, only to confront them with the problem the Poles had found insoluble:7

  When the various papers from the Poles – and in particular the wheel wirings – reached GC and CS it was soon possible to decrypt the old messages for which the Poles had broken the keys, but more recent messages remained unreadable.

  They would have been unreadable for the same reason as the Poles found them unreadable. They did not have enough Bombes or perforated sheets for the five-rotor Enigma. There was another difficulty, which was that since I January 1939 the German systems had used ten pairs on the plugboard, which made the Polish Bombe method unlikely to work. Behind all this lay a deeper problem, which was that the chief Polish methods depended entirely upon the specific indicator system used. Something quite new was required. And this was where Alan played his first crucial part.

  The British analysts did immediately embark upon making the sixty sets of perforated sheets that were required for the first ‘female’ method – now swollen to a colossal task of examining a million rotor settings. But they would have known that if ever the nine-letter indicator system were changed, even slightly, then the sheets would become useless. They needed something more general, something which did not depend upon specific indicator systems.

  There did exist such methods, in the case of Enigma machines used without a plugboard. Such, for instance, was the case with the Italian Enigma, and also with that used by Franco’s forces in the Spanish Civil War, whose system had been broken by GC and CS in April 1937. One particular attack was based on what Sinkov described as the ‘Intuitive’ or ‘Probable Word’ method. For this, the analyst had to guess a word appearing in the message, and its exact position. This was not impossible, given the stereotyped nature of many military communications, and would be helped by the feature of the Enigma that no letter could be enciphered into itself. Assuming the Enigma rotor wirings known, a correctly guessed word could quite easily lead the cryptanalyst to the identity of the first rotor and its starting position.

  Such analysis would be done by hand methods. But in principle, a much more mechanical approach could be made, exploiting the fact that even a million possible rotor positions did not constitute a ‘tremendously large number’. Like the Polish Bombe, a machine could simply work through the possible positions one by one until it found one that transformed the cipher-text into the known plain-text.

  In the following diagrams, we forget the internal details of the basic Enigma, and think of it just as a box which transforms an input letter into an output letter. The state of the machine is represented by three numbers, giving the positions of the rotors. (We also leave aside the problem that the middle and inner rotors may move, and assume them static; in practice this would prove an important consideration in applying the method, but not affecting the principle.)

  Now suppose it is known for certain that UILKNTN is the encipherment of the word GENERAL by an Enigma without plugboard. This means that there exists a rotor position, such that U is transformed to G, and such that the next position transforms I to E, the next one taking L to N, and so forth. There is no obstacle in principle to making a search through all the rotor positions until this particular position is found. The most efficient way would be to consider all seven letters simultaneously. This could be achieved by setting up a line of seven Enigmas, with their rotors in consecutive positions. One would feed in the letters UILKNTN, respectively, and look to see whether the letters GENERAL emerged. If not, all the Enigmas would move on by one step, and the process would be repeated. Eventually, the right rotor position would be found, the state of the machines then appearing as, say,

  None of this would require technical advances beyond that of the Polish Bombe; it would be easy to attach wires such that a current would flow if and only if all seven letters agreed with GENERAL, and stop the machine.

  Even in the early days, such an idea was not particularly far-fetched. Alan’s contemporary, the Oxford physicist R. V. Jones who had become scientific advisor to the secret service, was billeted at Bletchley in late 1939. He conversed with Edward Travis, Denniston’s deputy, about the current cryptanalytic problems. Travis posed the far more ambitious problem of the automatic recognition not of a fixed text, but of German language in general. Jones inventively proposed various solutions, one of which was8

  to mark or punch a paper or film in any one o
f 26 positions, corresponding to the letter coming out of the machine … and to run the resulting record past a battery of photocells, so that each could count the number of times of occurrence of the letter that it was looking for. After a given total count had been achieved, the frequency distribution between the letters could be compared with the one appropriate to the language, which could have been set up on some kind of template.

  Travis introduced Jones to Alan, who ‘liked the idea’. But with the Enigma, at least, the central method remained on entirely different lines. It kept to the idea of exploiting a known piece of plain-text. The difficulty, of course, was that the military Enigma did use a plugboard, which rendered such a naive searching process impossible, there being 150,738,274,937,250 possible ways* of connecting ten pairs of letters. In no way could a machine run through them all.

  Yet no serious analyst would be daunted by this frightening number. Large numbers would not in themselves guarantee immunity from attack. Anyone who had solved a puzzle-page cryptogram had succeeded in eliminating all but one of the 403, 291,461,126,605,635,584,000,000 different alphabetic substitutions.† It could be done because such facts as that E was common, AO rare, and so forth, would each serve to eliminate vast numbers of possibilities at once.

  It can be seen that the sheer number of plugboards is not in itself the problem, by considering an entirely hypothetical machine, in which a plugboard swapping is applied only before encipherment by a basic Enigma. Suppose that for such a machine, it is known for certain that the cipher-text FHOPQBZ is the encipherment of GENERAL.

  Once again, it would be possible to feed the letters FHOPQBZ into seven consecutive Enigmas, and examine the output. But this time, one could not expect the letters GENERAL to emerge, for an unknown plugboard swapping would have been applied to those letters. Nevertheless, something could still be done. Suppose that at some point in the process of running through all the rotor positions, the set-up happens to be:

  Then it may be asked whether the letters GFGCORL could, or could not, be obtained from GENERAL by the effect of a plugboard swapping. In this example, the answer is ‘no’, since no swapping could leave the first G unchanged, but swap the second G into an N; no swapping could turn the first E of GENERAL into an F and the second into a C. Furthermore, no swapping could change the R of GENERAL into an O, but then change the A into an R. Any one of these observations suffices to rule out that particular rotor position.

  One way of thinking of this question is in terms of consistency. Having fed the cipher-text into the Enigmas, is the output consistent with the known plain-text, in that it differs only by virtue of swapping? From this point of view, the correspondences (OR) and (RA), or (EF) and (EC), are contradictions. A single contradiction is enough to eliminate all the billions of possible plugboards, on this hypothetical machine. Sheer numerical size, therefore, may be insignificant, compared with the logical properties of the cipher system.

  The crucial discovery was that something like this could be done for the actual military Enigma, with its plugboard swapping taking place both before and after entry into the rotors of the basic Enigma. But the discovery was not immediate, nor was it the product of a single brain. It required a few months, and there were two figures primarily involved. For while Jeffries looked after the production of the new perforated sheets, the other two mathematical recruits, Alan and Gordon Welchman, were responsible for devising what became the British Bombe.9

  It was Alan who had begun the attack, Welchman having been assigned to traffic analysis, and so it was he who first formulated the principle of mechanising a search for logical consistency based on a ‘probable word’. The Poles had mechanised a simple form of recognition, limited to the special indicator system currently employed; a machine such as Alan envisaged would be considerably more ambitious, requiring circuitry for the simulation of ‘implications’ flowing from a plugboard hypothesis, and means for recognising not a simple matching, but the appearance of a contradiction.

  The Turing Bombe

  Suppose now that the letters LAKNQKR are known to be the encipherment of GENERAL on the full Enigma with plugboard. This time there is no point in trying out LAKNQKR on the basic Enigmas, and looking at what emerges, for some unknown plugboard swapping must be applied to LAKNQKR before it enters the Enigma rotors. Yet the quest is not hopeless. Consider just one letter, the A. There are only 26 possibilities for the effect of the plugboard on A, and so we can think about trying them out. We may start by taking the hypothesis (AA), i.e., the supposition that the plugboard leaves the letter A unaffected.

  What follows is an exploitation of the fact that there is only one plugboard, performing the same swapping operation on the letters going into the rotors as on the letters coming out. (If the Enigma had been fitted with two different plugboards, one swapping the ingoing letters and one the outcoming, then it would have been a very different story.) It also exploits the fact that this particular illustrative ‘crib’ contains a special feature – a closed loop. This is most easily seen by working out the deductions that can be made from (AA).

  Looking at the second letter of the sequence, we feed A into the Enigma rotors, and obtain an output, say O. This means that the plugboard must contain the swapping (EO).

  Now looking at the fourth letter, the assertion (EO) will have an implication for N, say (NQ); now the third letter will give an implication for K, say (KG).

  Finally we consider the sixth letter: here the loop closes and there will either be a consistency or a contradiction between (KG) and the original hypothesis (AA). If it is a contradiction, then the hypothesis must be wrong, and can be eliminated.

  This method was far from ideal. For it depended absolutely upon finding closed loops in the ‘crib’, and not all cribs would exhibit this phenomenon.* But it was a method that would actually work, for the idea of completing a closed circuit was one that could be translated naturally into an electricaI form. It showed that the sheer number of plugboards was not, in itself, an insuperable barrier.

  It was a start, and it was Alan’s first success. Like most wartime scientific work, it was not so much that it needed the most advanced knowledge of the day. It was rather that it required the same kind of skill that was used in advanced research, but applied to more elementary problems. The idea of automating processes was familiar enough to the twentieth century; it did not need the author of Computable Numbers. But his serious interest in mathematical machines, his fascination with the idea of working like a machine, was extraordinarily relevant.† Again, the ‘contradictions’ and ‘consistency’ conditions of the plugboard were concerned only with a decidedly finite problem, and not with anything like Gödel’s theorem, which concerned the infinite variety of the theory of numbers. But the analogy with the formalist conception of mathematics, in which implications were to be followed through mechanically, was still a striking one.

  Alan was able to embody this idea in the design of a new form of Bombe at the beginning of 1940. Practical construction began, and was pursued with a speed inconceivable in peacetime, under the direction of Harold ‘Doc’ Keen at the British Tabulating Machinery factory at Letchworth. Here they were used to building office calculators and sorters in which relays performed simple logical functions such as adding and recognising. It was now their task to make relays perform the switching job required for the Bombe to ‘recognise’ the positions in which consistency appeared, and stop. Here again, Alan was the right person to see what was needed, for his unusual experience with the relay multiplier had given him insight into the problems of embodying logical manipulations in this kind of machinery. Perhaps no one, in 1940, was better placed to oversee such work than him.

  Yet Alan had not seen that a dramatic improvement could be made to his design. Here it was Gordon Welchman who played the vital part. He had moved into the Enigma cryptanalytic group with a remarkable achievement to his credit: he had re-invented the perforated sheets method by himself, entirely ignorant of the fact th
at the Poles had worked it out and that Jeffries already had the production in hand. Then, on studying the Turing Bombe design, he saw that it had failed to exploit Enigma weakness to the full.

  Returning to the illustration of the Turing Bombe, we notice that there are other implications which were not followed up, as indicated by the heavier lines:

  These differ in being implications that could not be foreseen in advance. They arise because (KG) also means (GK), and so at position 1 has an implication for L. Similarly (NQ) also means (QN) and hence at position 5 has an implication for R. This will give rise to a further implication for L at position 7. Clearly there is the possibility of a contradiction arising between these further implications, over and above the question of the loop closing at position 6. Indeed it is not now necessary for the texts to exhibit a loop for a contradiction to arise in this more general way. But this greater power of deduction does depend upon having some automatic means of going from (K G) to (G K), and similarly for every other implication reached, without knowing in advance when or where this may be required.