The basic principle of using an Enigma machine was that its rotors and rings and plugboard would be set up in some particular way, and then the message would be encrypted, the rotors automatically stepping round as this was done. But for this to be of any use in a practical communication system, the receiver of the message also had to know the initial state of the machine. It was the fundamental problem of any cipher system. The machine was not enough; there had to be also an agreed, fixed, ‘definite method’ of using it. According to the actual method employed by the Germans, the initial state of the machine was partly decided at the time of use by the cipher clerk. Inevitably, therefore, it made use of indicators, and it was through the indicator system that the Poles enjoyed their success.
To be explicit, the order of the three rotors was laid down in written instructions, and so was the plugboard and ring-setting. The task of the cipher clerk was to choose the remaining element, the initial settings for the three rotors. This amounted to choosing some triplet of letters, say ‘WHJ’. The most naive indicator system would have been simply to transmit ‘WHJ’, and follow it with the enciphered message. However, it was made more complicated than that. The ‘WHJ’ was itself enciphered on the machine. For this purpose a so-called ground-setting was also laid down in the instructions for the day. This, like the rotor order, plugboard and ring-setting would be common to every operator in the network. Suppose the ground-setting were ‘RTY’. Then the cipher clerk would set up his Enigma with the specified rotor order, plugboard and ring-setting. He would turn the rotors to read ‘RTY’. Then his job was to encipher, twice over, his own choice of rotor setting. That is, he would encipher ‘WHJ WHJ’, producing say ‘ERIONM’. He would transmit ‘ERIONM’, then turn the rotors to ‘WHJ’, encipher the message, and transmit it. The strength was that every message, after the first six letters, was enciphered on a different setting. The weakness was that for one day, all the operators in the network would be using exactly the same state of the machine for the first six letters of their messages. Worse, those six letters always represented the encipherment of a repeated triplet. It was this element of repetition that the Polish cryptanalysts were able to exploit.
Their method was to collect each day, from their radio intercepts, a list of these initial six-letter sequences. They knew that in this list, there would be a pattern. For if in one message the first letter were A, and the fourth letter was R, then in any other message where the first letter was A, the fourth letter would again be R. With enough messages, they could build up a complete table, say:
First letter: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Fourth letter: R G Z L Y Q M J D X A O W V H N F B P C K I T S E U
There would be two further tables, connecting the second and fifth letters, and the third and sixth. There were a number of ways of using this information to derive the state of the Enigma machine from which all those six-letter sequences had emanated. But particularly significant was a method which responded to the mechanical work of the cipher clerk, with a mechanised form of analysis.
They wrote these tables of letter connections in the form of cycles. The cycle notation was common currency in elementary group theory. To bring the specific letter connection above into ‘cycle’ form, one would start with the letter A, and note that A was connected with R. Then R was connected with B, B with G, G with M, M with W, W with Z, Z with C, C with Z, Z with U, U with K, and K with A – making a complete ‘cycle’: (A R B G M W T C Z U K). The complete connection could be written out as the product of four cycles:
(ARBGMWTCZUK) (DLOHJXSPNVI) (EY) (FQ)
The reason for doing this was that the analysts had noticed that the lengths of these cycles (in this example, 11, 11, 2, 2) were independent of the plugboard. They would depend only upon the position of the rotors, the plugboard affecting which letters appeared in the cycles, but not how many. This observation showed that in a rather beautiful way the rotor positions left their fingerprints upon the cipher-text, when the traffic was considered as a whole. In fact they left just three fingerprints, the cycle-lengths of each of the three letter-connection tables.
It followed that if they possessed a complete file of the cycle-length fingerprints, three for each rotor position, then to determine which rotor position was being used for the first six letters all they would have to do was to search through the file. The snag was that there were 6 × 17576 possible rotor positions to catalogue. But they did it. To help in the work, the Polish mathematicians devised a small electrical machine which incorporated Enigma rotors, and which automatically produced the required sets of numbers. It took them a year to do the work, the results of which were entered on file cards. But then the detective work was effectively mechanised. It only took twenty minutes to look through the file to identify the combination of cycle-lengths which matched the cipher traffic of the day. This would reveal the positions of the rotors as they stood during the encipherment of the six indicator letters, and from that information, the rest could be worked out and the day’s traffic read.
It was an elegant method, but the disadvantage was that it depended entirely on the specific indicator system. It did not last. The naval Enigma was the first to be lost, and6
… after the end of April 1937, when the Germans changed the naval indicators, they had been able to read the naval traffic only for the period from 30 April to8 May 1937, and that only retrospectively. Moreover, this small success left them in no doubt that the new indicator system had given the Enigma machine a much higher degree of security…
And then on 15 September 1938, as Chamberlain flew to Munich, a greater disaster struck. All the other German systems were changed. It was only a minor modification, but it meant that overnight, all the catalogued cycle-lengths became completely worthless.
In the new system, the ground-setting was no longer fixed in advance. Instead, it would be chosen by the cipher clerk, who therefore had to communicate it to the receiver. This was done in the simplest possible way, by transmitting it as it stood. Thus the clerk might choose AGH, then set the rotors to read AGH. He would then choose another setting, say TUI. He would encipher TUITUI, to give say RYNFYP. He would then transmit AGHRYNFYP as indicator letters, followed by the actual message as enciphered with the rotors starting on the setting TUI.
This method depended for its security upon the fact that the ring-setting would be varying from day to day, for otherwise the first three letters (AGH, in the example) would give the whole thing away. The task of the analyst, correspondingly, was to determine this ring-setting which was common to all the traffic of the network. And amazingly, the Polish analysts were able to bounce back with a new kind of fingerprint, which had the effect of finding this ring-setting, or equivalently, of finding the core-position which corresponded to the openly announced rotor setting such as AGH in the example.
As with the older method, the fingerprint depended upon looking at the entire traffic, and in exploiting the element of repetition in the last six of the nine indicator letters. Without a common ground-setting, there was no fixed correspondence between first and fourth, second and fifth, third and sixth letters, to analyse. But one remnant of this idea, like the grin on the Cheshire cat, survived. Sometimes it would happen that first and fourth letters would actually be the same - or the second and the fifth, or the third and the sixth. This phenomenon was, for no apparent reason, called ‘a female’. Thus, supposing that TUITUI were indeed enciphered as RYNFYP, that repeated Y would be ‘a female’. This fact would then give a small piece of information about the state of the rotors as they were when the letters TUITUI were being enciphered. The method depended upon putting enough of these clues together to deduce that state.
More precisely a core-position would be said to have a ‘female’ letter, if that letter’s encipherment happened to be the same three steps later. This was not a rare phenomenon, but would occur on average one time in twenty-five. Some core-positions (about forty per cent) would have the
property of possessing at least one ‘female’ letter, and the rest would not. The property of having a female, or not, would be plugboard-independent, although the identity of the female letter would depend upon the plugboard.
The analysts could easily locate all the observed females in the traffic of the day. They would not know the core-positions which had given rise to them, but from the openly announced rotor settings like AGH in the example, they would know the relative core-positions. This information yielded a pattern of females. Because only about forty per cent of the core positions had females, there might only be one way in which this pattern could be matched with their known distribution. Here therefore was the new fingerprint – a pattern of ‘females’.
But it was not possible to catalogue in advance all possible patterns, as they had been able to do with the cycle lengths. There had to be some other, more sophisticated means of making the match. The method they employed made use of perforated sheets. These were simply tables of all the core-positions, in which instead of printing ‘has a female’ or ‘has no female’, there would either be a hole punched, or not. In principle they could first have constructed one such huge table, and then each day could have made a template with the pattern of females observed in the traffic of that day. Passing the template over the table, they would eventually have found a position where the holes matched. But that would have been far too inefficient a method. Instead, they had a method of piling pieces of the table of core positions on top of each other, staggered in a manner corresponding to the observed relative positions of the females. A ‘matching’ of the pattern would then show up as a place where light passed through all the sheets. The advantage of this staggering system was that 676 possibilities could be examined simultaneously. It was still a long job, requiring 6 × 26 operations for a complete search. It also required the construction of perforated sheets listing the 6 × 17576 core-positions. Yet they achieved this within a few months.
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 1 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.)
The Relay Race
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
Alan Turing: The Enigma The Centenary Edition Page 29