(ii)
Probability theory has already shown that the voltage on 5 out of the 12 ‘live’ contacts on each of the above lines of continuity will be returned via the diagonal board and will result in another ‘live’ contact on another scrambler. Since there are five such lines the total number of contacts that will be made ‘live’ = 5 × 5. Then taking into account that some are very likely to be ‘repeats’, the expected number of new contacts to be made ‘live’ in this way = 25 × (312 – 74)/312 ( = 19). Hence the cumulative total number of activated contacts at the end of the second stage = 74 + 19 = 93. This analysis can be continued for the third stage, fourth stage and so on until no additional new contacts are made ‘live’.
The set of results obtained for six stages is shown in the table overleaf.
The ‘live’ contacts on the diagonal board represent the steckers that can be deduced from the initial false stecker hypothesis that was chosen to start the process. The final number of 305 ‘live’ terminals obtained is only an approximation (about 2% too big) for the total number of (25 × 12) false steckers that would be expected to be obtained when using an open menu with 12 letters.
The final outcome obtained is that all but one of the contacts in each of the connected rows on the diagonal board become ‘live’. The remaining ‘non-live’ contacts will all be on one particular ‘line of electrical continuity’ that is electrically isolated from the others and these contacts represent in electrical terms the true stecker partners of the twelve letters on the menu. If the initial stecker hypothesis used happens to be true then only the contacts on the isolated line of continuity will become ‘live’.
The first machine to be fitted with a diagonal board became operational in late August 1940; it was a considerable improvement on the early prototype and operationally it proved to be very effective. Subsequently a large number of bombes of this type were manufactured, and for a time these was known as spider bombes. The probable reason for this name was that Welchman often referred to bombe menus as ‘webs’.
All of the ‘stops’ given by the bombe are detected by means of a test procedure that is carried out at each of the possible rotor settings, where at each setting the 26 alternative stecker hypotheses for a chosen input letter on the menu are tested simultaneously. In electrical terms the true stecker hypothesis is identified by a particular contact on one line of continuity through the scramblers that is found to be electrically isolated from all the others. Each of the contacts on this isolated line of continuity represents a possible stecker partner for the corresponding letter on the menu. When such a single line of continuity is detected by the logic circuits incorporated in the bombe it will automatically execute a ‘stop’. The information provided by a ‘stop’ consists of the rotor settings together with a corresponding possible stecker partner of the chosen input letter.
A serious problem that had to be dealt with was that in addition to the stop that provided the correct information, additional random stops could also occur. The number of random stops obtained depended on the structure of the menu and clearly it was necessary to be able to predict the number likely to be obtained from a given menu.
Consider a menu consisting of a single open network, (i.e. one without any loops). At each of the possible 26 × 26 × 26 rotor settings for a given rotor order, any initial stecker hypothesis, say g, for the chosen input letter A will lead to one stecker partner for each of the other letters on the menu, and so will satisfy the necessary condition for a ‘stop’ to occur. Hence the expected number of stops resulting from any initial stecker hypothesis = 26 × 26 × 26. In all there are 26 possible initial stecker hypotheses, so it follows that there are 26 × 26 × 26 × 26 (= 264) possible combinations that will all satisfy the condition required for a stop to take place (i.e. 26 ‘stops’ for each of the possible rotor settings)!
Each ‘stop’ will lead to stecker partners for all the letters on the menu. For example the two letters E and F on the menu will have 26 × 26 possible different pairs of stecker partners (including ‘self-steckers’). The diagram shows the pair (E/c and F/k).
The Effect of the Presence of a Loop in the Menu
Suppose that the letters E and F are in positions on the menu such that the introduction of a new link between them will create a closed loop. This link has the important effect of reducing the number of possible stops by a factor of 26 which can be explained in the following way:
When the link between the letters E and F is added to the original menu, a restriction is imposed on the number of possible pairs of stecker partners for the letters E and F.
The diagram showing one possible pair of (x n) when letter x is encrypted through the new scrambler to give n, so that E/x ↔ F/n. consequently the corresponding pair of stecker partners for letters E and F is (x n). Since every scrambler permutation consists of thirteen pairs of reciprocal letter transpositions, the total number of possible pairs of stecker partners for letters E and F is reduced from (26 × 26) to (2 × 13) = 26.
Thus the introduction of the additional link has the effect of reducing the number of possible pairs of stecker partners by a factor of 26, and consequently there will be the same reduction factor for the number of stops obtained when the new link is added to the menu. Hence the expected number of random stops obtained with a simple menu with one loop = 264/26 = 263 (i.e. one for each of the possible rotor settings.)
In general if the links in a menu result in the formation of c loops then the number of random stops S obtained is given by the expression:
S = (264)/26c = 264−c
Turing carried out a mathematical investigation to estimate how effective the diagonal board was in reducing the number of random ‘stops’, and produced a very useful table that enabled an accurate estimate to be found for the number of random stops to be expected from a given menu (he described this work as ‘very tedious and uninteresting’). This table was based on an expression for the expected number of random stops in terms of the number of loops c on the menu and a factor F that depended on the number of letters it had:
Estimated number of random stops = 264−c × F
He derived numerical values of the factor F for different numbers of letters on the menu showing that the number decreased very rapidly as the number of letters increased. (It is worth noting that without the diagonal board the number of random stops entirely depended on the number of loops.)
One particular entry from Turing’s table shows that for a menu of 12 letters, F = 0.0018. This result can be used to illustrate the beneficial effect of the diagonal board.
Let the number of random stops obtained from a menu with 12 letters and c loops when using the diagonal board = N.
Then
N = 264−c× 0.0018
Suppose that another ‘stronger’ menu with 12 letters and k loops (where k is greater than c) would be required to produce the same number of random stops when the diagonal board is not connected:
Then
N = 264−k
Hence
264−c× 0.0018 = 264−k
After some simplification this reduces to: 26k−c = 500
Hence
(k−c) = log (500) ÷ log (26) (≈ 1.90)
Hence
k ≈ c + 2
This result shows that for a menu of 12 letters the effect of the diagonal board is approximately equivalent to the addition of 2 additional loops.
In order to identify the correct ‘stop’ from all the other ‘random’ ones, each had to be subjected to a process of hand testing. The first step in this task was to use the information provided by the ‘stop’ to determine the stecker partners for all of the letters appearing on the menu that were implied by it. These implied stecker partners were tested for their logical consistency by checking to see that for every letter on the menu the implied stecker partner was unique. All of the ‘stops’ that failed to satisfy this requirement were regarded as being due to chance and would be rejected.
The task of f
inding the implied stecker pairs was carried out with the aid of a small ancillary piece of equipment known as a ‘checking machine’, but sometimes there were additional difficulties. If a menu happened to be made up of two or more unconnected parts (known as ‘webs’) then often some of the implied stecker pairs could not be found directly in this way and in such cases some additional deductive work would be necessary to find them.
To come to an understanding of the function of the checking machine, consider again a menu previously given but now re-arranged into the equivalent form shown in the diagram below.
Suppose that a particular bombe stop found from this menu gave the rotor settings: H B L together with the stecker pair S/I. The validity of this stop would have been checked in the following way:
From the ‘stop’ it is known that letter S has letter I as its stecker partner, and so logically letter I should have letter S as its stecker partner. However the partners of the other letters Q, F, E, H and U are currently unknown. Let these unknown letters be represented by the Greek letters: α, β, γ, δ, and ε, so that Q/α, F/β, E/γ, H/δ and U/ε are the unknown stecker pairs.
From the stecker pair S/I given by the ‘stop’ it follows from the information in the diagram that if the letter I is used as the input to the scrambler system adjusted to ‘position 21’ that the output letter from this scrambler will be the implied stecker partner of letter Q on the menu. It is in fact found that α ≡ Q, indicating that letter Q must be ‘self-steckered’ i.e. Q/Q. (The standard German practice was to use six self-steckers in each Enigma key.)
In the same way by using this implied letter Q as the input to the next scrambler adjusted to ‘position 3’ the output letter obtained will be the implied stecker partner of letter I on the menu. For logical consistency this must be the letter S, otherwise there would be a contradiction with the stecker pair S/I given by the bombe ‘stop’. So if a different letter were to be obtained then this would show that the ‘stop’ was a random one.
Supposing, however, that the letter S was obtained, then the testing procedure would be continued with letter S now being used as the input to the scrambler adjusted to ‘position 12’, so that the output β will be the implied stecker partner for letter F. This process could be continued for all the letters on the menu. If any logical inconsistency were to be discovered between the results then the ‘stop’ would be regarded as ‘random’ and would be rejected. This would happen if, for example, the two inconsistent implied stecker pairs T/F and U/T were to be obtained.
If no inconsistencies were found between any of the implied stecker partners for all of the letters on the menu then the stop was said to have provided a ‘partial key’. If the partial key were set up on an Enigma machine then it would decrypt all the letters from the crib that had been used for the menu, but not usually the complete message because it was unlikely that the restricted number of letters on the menu would have enabled deductions to be made for all the ten stecker pairs that ultimately had to be found.
The checking machine used special drums that were similar in their design to the German Enigma rotors as they also had adjustable rings, unlike the drums used on the bombe. The machine had a fourth drum that functioned as an adjustable pre-set reflector. The machine also had 26 keys for the input letters and the same number of lamps to indicate the output letters. The selection of the drums and their ring settings was made to correspond to the information given by the ‘stop’ on the bombe. The set of drums on the checking machine would then be moved in turn to correspond to the positions given on the menu. As one stecker pair had already been given by the ‘stop’, the implied stecker partners for all of the other letters on the menu could then be found in turn.
Summary
After a menu had been set up on the bombe and a chosen set of drums had been installed, the machine would be systematically run through all of the possible starting positions, and at each of them tested for the condition that had to be satisfied to ensure that a unique stecker partner existed for a preselected letter on the menu. If at the end of a ‘run’ with a chosen rotor order all of the ‘stops’ that had been obtained were found to be false then another rotor order would have to be tried. The small number of partial keys obtained from the ‘stops’ that passed all the tests made by the checking machine were subjected to further examination. A brief account of how this was done will be given later.
If the unfortunate circumstances arose when none of the partial keys provided the complete key, then the validity of the menu had to be questioned, both with respect to its position relative to the letters in the original cipher text and also its literal accuracy.
Further Development of the Bombe
By the end of 1941 a more advanced version of the bombe (known as ‘Jumbo’) had been developed. This was fitted with additional circuitry that enabled a second test to be automatically carried out when the basic conditions for a ‘stop’ had occurred. The second test was designed to eliminate all those ‘stops’ that led to a ‘legal contradiction’, which the earlier versions of the machine were unable to detect. This second test checked the logical consistency of all the stecker pairs that could be directly deduced from the menu and if an inconsistency was detected then the new machine ignored the basic ‘stop’ condition that had occurred and continued with the ‘run’. If, however, no inconsistencies were found then the machine did stop and automatically printed out all of the stecker pairs that could be directly deduced from the menu.
The introduction of Jumbo eliminated a major part of the hand-based work that had previously been necessary but, as only a few of these machines were actually made, the bulk of the work throughout the war was carried out on the spider bombes, of which over 200 were in service by the end of the war in Europe. This new version of the machine provided no more information about the stecker pairs than was intrinsically available on the original bombes, but by automatically eliminating all the inconsistent random ‘stops’ and printing out details of the remaining ones, Jumbo made it possible to run much weaker menus successfully. The few Jumbo machines that were made were reserved for work on important messages that had only provided very weak menus and were expected to generate large numbers of random stops when used with a spider bombe.
The following extract from an internal memorandum from Welchman to Travis (September 1941) is of interest:
Dear Commander Travis,
The problems which we have to deal with in HUT 6 fall into two main classes – those in which we have to try 17,576 positions per wheel order, and those in which we need only try a limited number of positions. Problems of the first class can only be dealt with by means of a bombe, and the possibility of dealing with a particular problem depends chiefly on the strength of the menus that can be prepared. For running on a standard bombe a menu must be strong enough to produce a small number of stops because the testing of a large number of stops would take too much time. Weaker menus can be run on Jumbo because the machine tests its own stops, but the menus that can be run are limited by two factors. When a menu is so weak that Jumbo has to stop hundreds of times in each run, the running time is too long. Also when Jumbo produces a large number of stories, which have to be examined, the time and labour required for this part of the work becomes excessive …
At present we have eight bombes of which only one is a Jumbo.3
Difficulties Caused by Middle-Rotor Turnovers
A matter of vital importance that arose during the construction of the menus was the possibility that at some position within the span of the crib a middle-rotor turnover had occurred on the Enigma machine when the message had been encrypted. There was no prior way of knowing if this had happened, and if one had taken place and was not allowed for in the menu, then the ‘stops’ found in the subsequent bombe runs would all be wrong. Since a turnover on the middle rotor of an Enigma machine always occurred at some position during the encrypting of a sequence of 26 consecutive letters, it follows that for an menu to have more than an
even chance of success its span could not exceed 12 consecutive positions of the cipher text.
During the war several procedures were devised to overcome this difficulty, for example from a crib spanning consecutive positions it was possible to derive two menus each spanning 13 of these positions so that if the middle-rotor turnover occurred in one of them then it could not have occurred in the other. However, this approach often resulted in two relatively ‘weak’ menus (i.e. containing less than 2 loops) which could result in an undesirable large number of random stops.
Other methods involved making a sequence of trial runs using different assumed positions for the middle-rotor turnover. As these runs had to be repeated for each of the rotor orders that were to be tested, these procedures were often very time-consuming.
The bombes were designed with three banks of 12 ‘scramblers’, each scrambler consisting of three vertically aligned drums to emulate the three rotors in the Enigma machine. Then, provided that the menu used did not contain more than 12 letter pairs from the crib, this arrangement made it possible to try out three different menus or rotor orders simultaneously.
One remarkably innovative procedure was proposed by John Herivel, the originator of the ‘Herivel Tip’. It appears in a BP research paper he wrote in the autumn of 1940 and required only one bombe run for each of the rotor orders to be tested.4 However, during this single run on the bombe the machine had to be manually halted by the operator several times to enable changes to be made to the offsets of some of the middle drums.
In his paper Herivel expressed his understanding that there were plans to modify the electrical design of the first bombes and ‘to interchange the slow and fast wheel’. This change made it possible for the bombe operators to use this new procedure he proposed. (In more recent times this perhaps unexpected design feature of the standard British bombes has often been a source of confusion.)
Gordon Welchman Page 31