This can be explained by means of the above three diagrams that show the left-hand rotor adjusted in three different ways. In diagram (a) the rotor setting is J and the ring setting is D so the letter D on the ring is aligned to be in registration with the index mark on the core of the rotor. The entire rotor has then been turned so that letter J appears in the left-hand viewing window on the Enigma machine. (Note that the positions of letters J and D in the alphabet differ by 6 places).
In diagram (b) the ring setting has been changed from D to Z by turning the inner core of the rotor ‘forwards’ so that the index mark on it comes into registration with letter Z on the ring. Note that the ring itself has not been moved and letter J still appears in the left-hand viewing window.
In diagram (c) the rotor setting has be changed from J to F by turning the entire rotor (i.e. including the core) ‘backwards’ so that the letter in the viewing window changes accordingly. Note that this has the effect of moving the index mark on the core (together with the internal wiring) to its original position. (Note that the positions of letters F and Z in the alphabet differ by 6 places.)
Similar thinking applied to the two other rotors should lead to the conclusion that the rotor positions F A T and ‘ring settings’ Z Z Z do represent the same set of rotor ‘core starting positions’ as message settings J H L and ‘ring settings’ D G R
The penalty incurred by assuming the ‘ring settings’ to be Z Z Z, is that the true locations of the left and middle-rotor turnover positions will almost certainly differ from those given by the assumed letters. During the war the correct turnover positions had to be found by a sequence of trials that were made at the last stage of the codebreaking process.
The rotors and reflector as used in the Enigma machine were designed as a single-ended unit. In the development of the bombe, an alternative double-ended form was devised which used rotating ‘drums’ instead of rotors as this was an essential requirement in the design of the machine. Each of these double-ended ‘scramblers’ had two sets of 26 input/output terminals, and the units could be linked together by 26-way cable connectors in a variety of ways. The following two diagrams show the distinction between the two forms of construction:
The drums in each scrambler unit were mechanically linked so that they moved from one position to another like the wheels in the odometer of a car. However, they could be independently pre-set to any chosen starting position.
Unlike the adjustable rings attached to the rotors in the Enigma machine, the drums simply had fixed rings of reference letters marked on their circumferences. Consequently the unknown turnover positions of the middle and right-hand rotors of the Enigma machine were unlikely to be the same as those of the corresponding drums in the bombe. This resulted in some restrictions and difficulties in the operational use of the machine.
The Turing Bombe
The fundamental ideas upon which the bombe was based are attributed to Alan Turing, and the first two of them are given here as direct quotations from his wartime paper ‘Treatise on the Enigma’.1
(i)
‘The best data for finding an Enigma key is a crib.’
(ii)
‘The method to be used for finding a key will be to take a hypothesis about part of the key and then draw from it all the conclusions that one can, hoping to obtain either a confirmation or a contradiction.’
(iii)
The perception that a closed chain of successive Enigma encipherments had a very useful property that could be exploited. (These chains were to be found in some of the cribs as will be explained.)
(iv)
His realization that a search for the correct key could be hugely reduced by rejecting all the possible keys which were found to be logically inconsistent with the information that had been derived from a crib.
A Crib
This was a conjecture (an informed guess!) for the letters of plain text represented by a given sequence of cipher letters. The big advantage of finding keys by means of cribs was that the process could not be compromised by any future changes that the Germans might make in their operational procedure. An analysis of some messages broken by earlier methods had revealed that a useful proportion of the messages contained common forms of expression (stereotypes) that could be used as cribs.
The whole basis of Turing’s approach was the idea of running a crib through all 17,576 different positions of the drums for a given wheel order, and accepting or rejecting a given position by testing to see if possible stecker pairs could or could not be found for it. This was a very remarkable idea: although in theory the steckers made the identification vastly more difficult, in practice they provided a method for spotting possible positions. Thus the steckers were used to work for a solution and their ‘difficulty’ was thus neatly compensated for by their ‘utility’.2
The following illustrative example of a crib was derived from a dummy message encrypted on an Enigma machine. The initial rotor configuration used was specially chosen to avoid the additional complications that would have arisen if a middle-rotor turnover had occurred within the span of the 25 positions of the crib (the problems caused by middle-rotor turnovers will be addressed later):
This crib can also be represented in the diagrammatic form that was known as a ‘menu’:
Each ‘link’ in the menu shows the relationship between the cipher/plain text pair of letters at a particular position on the crib. For example at the fourth position the relationship shown is that letter S is encrypted as U or alternatively, as a consequence of the reciprocal nature of Enigma, letter U is encrypted as S.
Turing found a useful way of formulating a hypothesis about part of a given message key that depended on the sequences of links forming the closed ‘loops’ that appeared in some menus. The bombe was designed to test these hypotheses in a way that provided parts of the Enigma key that had been used, so that subsequently the complete message key for the day could be found.
The given menu shown contains three such sequences of links forming loops, one for example for the positions: 4, 2, 9, 16, 22. Starting with the letter S this generates the closed letter sequence: S U H E Y (S).
The following diagram gives this sequence of links again now showing only those parts of the encrypting process due solely to the effects of the Enigma rotor system. Starting with the letter α (representing the unknown stecker partner of letter S), the diagram shows how the closed chain of (unknown) stecker letters: α, β, γ, δ, ε, (α) are related to one another.
It is very important to appreciate that the identity of the unknown stecker letters β, γ, δ, ε will depend only on the identity of letter α together with the rotor positions but not on the letters that appeared on the original menu. It was from sequences of steckered letters like this that Turing was able to formulate his working hypotheses.
Suppose that the rotor configuration is correct (i.e. both the rotor order and rotor core positions are correct), and that the working hypothesis to be used for identifying the stecker partner of letter S is: α ≡ A (i.e. the stecker hypothesis is: S/A). Then as the diagram shows, if this hypothesis is correct, then the final outcome from the closed sequence of successive encipherments, beginning with the chosen letter A must also be letter A as any other outcome would imply a logical contradiction, as the letter S must have a unique stecker partner.
A practical way of testing a working hypothesis like this can be carried out by means of the circuit shown overleaf. Assuming that the rotor configuration in use is correct, then to test the hypothesis: S/A, the switch for letter A on the panel is set to ‘on’ and the identity of the single lamp on the board that becomes lit is noted.
If the hypothesis S/A is correct then lamp A will be lit, but if it is false then instead a different lamp will be lit, indicating a logical inconsistency and establishing that hypothesis S/A is false. In this event the sequence of alternative hypotheses: S/B, S/C, S/D … etc. could then be systematically tested in turn, the final outcome being the discovery of t
he true stecker hypothesis and thus identifying the correct stecker partner of letter S.
The searching process carried out on the bombe was essentially the systematic testing of these stecker hypotheses. Turing called the basic process ‘single line scanning’, as the test involved applying a voltage to the input terminals of the scramblers one at a time. However, he realized that this would be much too slow as it would have been necessary to carry out up to 26 of these single tests, for every rotor configuration. Substantial improvements were needed if the bombe was to have any operational value.
There is some evidence that at an early stage in the design of the bombe, an electronic system was considered that would have enabled the 26 individual stecker hypothesis tests to be made at a very high speed. Turing referred to this ideal process as ‘simultaneous scanning’. This project was quickly abandoned, after it had been discovered that new ideas (to be considered later) made it unnecessary to resort to the use of complex electronics.
There was also a significant weakness in the test procedure as it has so far been described, that is best understood by means of an example. Suppose that a false stecker hypothesis is under test say S/D and that the rotor configuration being used is also wrong. The identity of the lamp on the panel that is lit now depends entirely on random chance, and so it is possible that it could be lamp D, thus wrongly indicating that the false hypothesis S/D was true. The probability of this happening is 1/26, which is an unsatisfactorily high value.
To reduce the chances of such false conclusions occurring, Turing proposed that the testing process should be carried out with menus that contained at least three closed sequences of successive encipherments. The example menu is of this type containing the sequence S1 = (4 2 9 16 22) already described and also the 2 additional sequences S2 = (21 3 12 20 9 2 4) and S3 = (21 3 5 1 15 20 9 2 4).
These three sequences have the letter S in common (Turing called this ‘the central letter’, and so in testing any of the stecker hypotheses involving letter S, say (S/D), the condition now required to establish the truth of the hypothesis is the simultaneous lighting of lamp D on all three panels shown in the next diagram.
With this circuit if the rotor configuration and the stecker hypothesis to be tested (S/I, the correct hypothesis in this case) are both correct, then lamp I will be lit on each board. If however a wrong hypothesis is tested then it is highly probable that a different lamp will light up on each of the boards.
Suppose for example that the false hypothesis S/Q is tested, and that as a consequence of setting the switch Q to ‘on’, lamp W is lit on one of the boards. Thus the hypothesis S/Q has led to the inconsistent conclusion S/W, showing that the hypothesis S/Q is false. It is important to appreciate that the conclusion S/W will itself be false. This can be verified in the following way:
If the hypothesis (S/W) were true, then when tested (i.e. by setting switch W to ‘on’), lamp W would be lit on all three boards. But it has already been established that on one of the boards lamp W was lit by means of switch Q and not by switch W, consequently the hypothesis (S/W) must be false.
Speeding up the Scanning Process
Turing thought of a highly ingenious idea that enabled the true stecker hypothesis for a chosen letter on the menu to be quickly identified by means of a procedure that eliminated all of the false ones. Provided that a suitable menu was available, this procedure enabled the correct hypothesis to be identified by means of a single electrical test that was carried out with modified versions of the electrical circuits described earlier.
The most important practical outcome of his innovative thinking was that this procedure could be carried out almost instantaneously, so that with suitable menus simultaneous scanning could be achieved.
The following is an extract from Turing’s ‘Treatise on Enigma’:
There is no reason why, when from one hypothesis about the stecker partner of the central letter we have deduced that the central letter [S in the example] must have a different stecker partner, the process should not go on to draw further conclusions from this second stecker pair. At first sight this seems quite useless, but as these deductions are reversible [i.e. may be used as new false hypotheses] it is actually very useful, for all the conclusions that can be drawn will be false, and those that remain will stand out clearly as possible correct hypotheses.
In the procedure based on this remarkable idea, each false conclusion reached in the way previously described, was to be used as a new hypothesis and so on. This gave rise to a chain of logical conclusions that were almost instantaneously deduced by means of the electrical circuits in the bombe.
A practical way of implementing this procedure is illustrated in the accompanying diagram where the output voltage signal representing the (false) conclusion resulting from the initial (false) hypothesis (S/A) is fed back as a new hypothesis, and the process is repeated until all the possible false conclusions have been reached. These are all revealed by the lamps that become lit, and these are represented in the diagram by the hollow circles.
Insight into why the circuit behaves in this way can be obtained by considering the permutation of the 26 letters represented by the switches created by the sequence of scramblers in the circuit.
The pairs of elements from such a permutation can in theory be determined one by one, by setting each switch in turn to ‘on’, and noting which lamp on the board is lit as a consequence.
For the sequence of scramblers shown in the diagram the permutation is:
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
C R K Z G F O J I N S H P V X T U E M A L W B Q D Y
Then beginning with the letter A the permutation gives the letter C and likewise from C the permutation gives the letter K, and so on. If this process is continued a sequence of letters will be created that will ultimately terminate when letter A recurs, so giving rise to the sequence (A C K S M P T). This is known as a ‘permutation cycle’ from the complete permutation.
The reader may wish to verify that the permutation also contains the following other permutation cycles:
C2 = (B R E G O X Q U L H J N V W), C3 = (D Y Z), C4 = (I), C5 = (F).
It will be seen that collectively the five cycles account for all 26 letters of the alphabet, and that there is no single letter common to any pair of cycles, (i.e. the cycles are mutually disjoint). The electrical behaviour of the circuit can now be predicted from the associated permutation cycles. The letter designated by any switch on the panel will also occur in one of the permutation cycles given above. If this switch is set to ‘on’ then all the lamps that correspond to the letters occurring in this cycle will be lit.
In one special case since the correct stecker hypothesis is S/I, the only conclusion reached will be S/I, so setting switch I to ‘on’ will result in only the lamp I on the panel being lit.
The structure of the cycles shows that tests carried out on the other 25 false stecker hypotheses will, with the exception of the hypothesis S/F, all result in more than one lamp on the panel being lit, but none would cause lamp I to be lit as the cycles are all mutually disjoint.
The application of voltage feedback to this particular circuit leads to results that considerably reduce the number of possible choices for the correct hypothesis. However the outcomes obtained on the lampboard fail to identify all of the false hypotheses and so it is still not possible to isolate the correct one. In addition there is one totally misleading outcome indicating that the false hypothesis S/F is in fact true!
The full value of voltage feed-back only becomes apparent when a longer crib is used such that the circuit derived from it contains more than one loop. This is illustrated by means of a more complex menu derived from the original crib, containing the 2 sequences S1 and S2. The following diagram shows the 2 loops for S1 and S2 from the original menu, in a circuit configuration that is similar to that used in the first version of the bombe.
The diagram does not include a lampboard as in fact lamps were not used o
n the bombe; instead a device known as the ‘indicator unit’ (or the ‘test-register’) was used, which incorporated 26 indicating relays. A test voltage was applied to the input terminal of one these relays and they provided a visual/tactile indication of the final results.
The input terminal chosen for this purpose was connected to a voltage source by means of the corresponding switch (A–Z) on the panel of switches. The indicator unit was connected to a chosen position on the scrambler circuit by means of a 26-way cable.
The terminals of the relays in the indicator unit that will also ‘receive’ the test voltage via the scrambler circuit can be identified by considering the permutation cycles for the two sequences S1 and S2.
S1 cycles: C1 = (A C K S M P T), C2 = (B R E G O X Q U L H J N V W),
C3 = (D Y Z), C4 = (I), C5 = (F).
S2 cycles: D1 = (A J U G F W Q L R S C Z M O), D2 = (B H D K Y),
D3 = (E V), D4 = (N T X P), D5 = (I).
If a test voltage is applied to terminal I on the indicator unit (i.e. testing the correct hypothesis S/I), then as the permutation cycle (I) occurs in the lists of cycles for both the sequences S1 and S2 the voltage cannot reach any of the other terminals on the test-registers. Terminal I is now the only one with this property so identifying the correct stecker hypothesis to be S/I.
If instead a false hypothesis, say (S/A) is tested, then the test voltage will be applied to relay terminal A, and because of the existence of the permutation cycle C1, the voltage will reach terminals A, C, K, S, M, P, and T via the S1 loop, and likewise because of the existence of the permutation cycle D1, the voltage will also reach the terminals A, J, U, G, F, W, Q, L, R, S, C, Z, M and O via the S2 loop.
Gordon Welchman Page 29
