Alan Turing: The Enigma The Centenary Edition

by Andrew Hodges

  to mark or punch a paper or film in any one of 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 electrical 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 he.

  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 perfora
ted sheets method by himself, entirely ignorant of the fact that 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 by 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 (KG) to (GK), and similarly for every other implication reached, without knowing in advance when or where this may be required.

  Welchman not only saw the possibility of improvement, but quickly solved the problem of how to incorporate the further implications into a mechanical process. It required only a simple piece of electrical circuitry – soon to be called the ‘diagonal board’. The name referred to its array of 676 electrical terminals in a 26 × 26 square, each corresponding to an assertion such as (KG), and with wires attached diagonally in such a way that (KG) was permanently connected to (GK). The diagonal board could be attached to the Bombe in such a way that it had precisely the required effect. No switching operations were required for this; the following of implications could still be achieved by the virtually instantaneous flow of electricity into a connected circuit.

  Welchman could hardly believe that he had solved the problem, but drew a rough wiring diagram and convinced himself that it would work. Hurrying to the Cottage, he showed it to Alan, who was also incredulous at first, but rapidly became equally excited about the possibilities it opened up. It was a spectacular improvement; they no longer needed to look for loops, and so could make do with fewer and shorter ‘cribs’.

  With the addition of a diagonal board, the Bombe would enjoy an almost uncanny elegance and power. Any assertion reached, say (BL), would feed back into every B and every L appearing in either plain-text or cipher-text. With this four-fold proliferation of implications at every stage it became possible to use the Bombe on any ‘crib’ of three or four words. The analyst could select a ‘menu’ of some ten or so letters from the ‘crib’ sequence – not necessarily including a ‘loop’, but still as rich as possible in letters bound to lead to implications for other letters. And this would provide a very severe consistency condition, sweeping away billions of false hypotheses with the speed of light.

  The principle was startlingly like that of mathematical logic, in which one might seek to draw as many conclusions as possible from a set of interesting axioms. There was also a particularly logical subtlety about the process of deduction. As so far described, the operation would require the trying out of one plugboard hypothesis at a time. If (AA) were brought down by its own contradictions, then (AB) would be tried, and so on, until all 26 possibilities had been exhausted. Only then would the rotors move on by one step and the next position be examined in the same way. But Alan had seen that this was unnecessary.

  If (AA) were inconsistent then it would generally lead to (AB), (AC), and so forth, in the process of following all the implications. This would mean that all these were also self-contradictory, and there was no need to try them out. An exception would occur when the rotor position was actually correct. In this case either the plugboard hypothesis would also be correct, and would lead to no contradictions; or would be incorrect and lead to every plugboard statement except the correct one. This meant that the Bombe was to stop when the electric current had reached either only one, or just twenty-five, of twenty-six terminals. It was this rather complicated condition that the relay switches had to test. This was not at all an obvious point, but seeing it made the process twenty-six times faster. Alan would comment on the likeness to mathematical logic, in which a single contradiction would imply any proposition. Wittgenstein, discussing this point, had said that contradictions never got anyone into trouble. But these contradictions would make something go very wrong for Germany, and lead to bridges falling down.

  Thus the logical principle of the Bombe was the wonderfully simple one of following the proliferation of implications to the bitter end. But there was nothing simple about the construction of such a machine. To be of practical use, a Bombe would have to work through an average of half a million rotor positions in hours rather than days, which meant that the logical process would have to be applied to at least twenty positions every second. This was within the range of automatic telephone exchange equipment, which could perform switching operations in a thousandth of a second. But unlike the relays of telephone exchanges, the Bombe components would have to work continuously and in concert, for hours at a stretch, with the rotors moving in perfect synchrony. Without the solution of these engineering problems, in a time that would normally see no more than a rough blueprint prepared, all the logical ideas would have been idle dreams.

  Even with Bombes designed and in the pipeline, the problem of the Enigma was far from solved. A Bombe would not take all the work out of the probable word method. One very important point was that when the consistency conditions were met, and a Bombe came to a halt, this did not necessarily mean that the correct rotor position had been arrived at. Such a ‘stop’, as it would be called, could arise by chance. (The calculation of how often such chance ‘stops’ were to be expected was a nice application of probability theory.) Each ‘stop’ would have to be tested out on an Enigma to see whether it turned the rest of the cipher-text into German, until the correct rotor position was discovered.

  Nor was it a trivial matter to guess the probable word, nor to match it against the cipher-text. A good cipher clerk, indeed, could make these operations impossible. The right way to use the Enigma, like any ciphering machine, was to guard against the probable word attack by such obvious devices as prefacing the message with a variable amount of random nonsense, inserting X’s in long words, using a ‘burying procedure’ for stereotyped or repetitious parts of the transmission, and generally making the system as unpredictable, as un-mechanical, as was possible without loss of comprehensibility to the legitimate receiver. If this were done thoroughly the accurate ‘cribs’ required for the Bombe could never be found. But perhaps it was too easy for the Enigma user to imagine that the clever machine would take care of itself, and there were often regularities for the British cryptanalysts to exploit.

  Even when they had overcome subtleties of this kind, and learnt how to guess words with perfect accuracy, the story was far from over. Deciphering one message would not help to fight the war. The problem was to solve every message, of which there would be thousands every day in each network. The solution of this problem would depend upon the cipher system as a whole. In a system as simple as the pre-war use of repeated triplets of indicator letters, a single solved message could be used to undo the whole process, find the ‘ground-setting’, and thus reveal the entire traffic. But the enemy would not always be so obliging. Moreover, there was a sort of double bind, since the process of guessing a word with virtual certainty would only become possible when there was a good acquaintance with the traffic as a whole. The Bombe would be of little use unless a break into that traffic were first made in some other way.

  With the Luftwaffe signals they did have another way – the method with perforated sheets which worked for the nine-letter indicator system. During the autumn of 1939, the construction of the sixty sets of sheets was completed, and a copy taken to the French cryptanalysts at Vignolles. This was an act of hope. No Enigma messages had been solved since December 1938, so they had no ass
urance that by the time the sheets were completed they would be of any use. But the hope was justified, for10

  ‘At the end of the year’, GC and CS records, ‘our emissary returned with the great news that a key had been broken (October 28, Green)* on the … sheets he had taken with him. Immediately we got to work on a key (October 25, Green)…; this, the first wartime Enigma key to come out in this country, was broken at the beginning of January 1940’. The GC and CS account continues: ‘Had the Germans made a change in the machine at the New Year? While we waited … several other 1939 keys were broken. At last a favourable day arrived… The sheets were laid … and [the] Red of 6 January was out. Other keys soon followed….’

  Their luck had held, and the perforated sheets gave the first entry into the system. It was like the Princeton treasure hunt, in that each success would give the clue to the next goal, that of speedier and more comprehensive decryption. Special methods like those of the sheets – and there were many other algebraic, linguistic, and psychological tricks – could open up the way for something better. But it was never simple, for the rules were changing all the time, and they had to run as fast as they could to keep up. They were only just in time and, had they fallen behind by a few months, might never have caught up. In the spring of 1940 it was particularly precarious, as they held on with a mixture of ingenuity and intuition – or as the military were likely to call it, sheer bloody guesswork.

  Guessing and hoping were entirely characteristic of current British operations. The government had little more idea of how a war could be won, or even of what was happening, than did the public. It seemed that the British and German armed forces had, after all, agreed to have a battle again, but the British Tweedledee was decidedly reluctant to be the one to start, and the German Tweedledum expected it all to be over by six o’clock. Tweedledee’s weaponry was still concealed behind Chamberlain’s umbrella. The Red King was snoring on the square to the east, and no one (not even at Bletchley) knew what he was dreaming of. The blockade was supposed to bring an already ‘stretched’ Germany to crack from within, if only Britain could ‘hold out’. Half desired, half dreaded by the British rulers, was the reappearance of the Monstrous Crow, currently flapping ambiguously on the other side of the Atlantic.