Gordon Welchman

by Joel Greenberg

  The following is a real example, taken from the ‘Official History of Hut 6’. Each day German airfields would receive instructions for their targets from Luftwaffe HQ and the signals always began with the phrase

  BESONDERE ANORDNUNGEN FUER DIE …

  (‘SPECIAL ORDERS FOR THE …’)

  Using the fact that the Enigma machine could not encrypt a letter as itself, a cryptanalyst hoped to find a position in which the first 20 characters of the German phrase in plain text, were different from a run of 20 encrypted characters from the intercepted message. These could be aligned as in the table below and the letters of the phrase which could be matched sequentially to a different letter of encrypted text was referred to as a crib. x was used to represent a space.

  On the Enigma machine the right-hand wheel turned every time a key was pressed but the turnover position of the middle and left wheels was determined by the ring settings. As each ring could be set to one of 26 positions, the middle and left wheels could turn at any point between the 1st and the 26th key stroke. This would create problems for the method of solution that Turing had in mind. Therefore, cribs were usually restricted to not more than 12 characters to give a better than 50:50 chance of avoiding a middle-wheel turnover. In this example, the first 12 letters were used for the crib.

  The Crib

  The relationship between the plain text and the encrypted text could be described graphically and the resulting diagrams were referred to as menus. While the bombe was not a computer, it had some computer-like characteristics. Therefore, this was arguably the first use of the word menu in association with a computer-like device.

  The Menu

  Each line in the diagram represented a 26-way cable and showed the relationship between the plain text/encrypted text pairs of letters at a particular position. The menu was in effect an instruction sheet for the technicians (usually members of the Women’s Royal Naval Service or WRNS) who operated the bombes. The letters were connected at the back of the bombe with red 26-way cables. 108 round drums were mounted on the front and each was wired internally to replicate an Enigma wheel. They were laid out in three banks of 36 in columns of 3. Each column replicated one Enigma machine and was called a scrambler.

  It was obvious to Turing that a head-on attack was doomed to failure if all of the elements of the daily key were taken on simultaneously. The bombe managed to isolate the plug connections and concentrate on finding the wheel choice and their order in the machine, one possible plug pair (one of which Turing called the central letter) and information relating to the message setting. Turing’s idea was that once you found these, you could then work out the plug connections and the rest of the key as a separate process. Turing described his brilliant idea of testing for the plug (or stecker) connections separately as follows:

  There is no reason why, when from one hypothesis about the stecker partner of the central letter we have deduced that it must have a different stecker partner, the process should not go on to draw further conclusions about this second stecker partner.

  At first sight this seems quite useless, but as these deductions are reversible [i.e. can be used as new hypotheses] it is actually very useful for all of the conclusions that can be drawn will be false, and those that remain will stand out clearly as possible correct hypotheses.

  So a letter would be chosen from the crib and a guess made about its plug pair (the hypotheses referred to by Turing). The extraordinary thing about this approach was that it did not matter whether the guess was right or wrong. The machine would come to the right conclusion in either case. A wrong answer would simply be used as a new starting point to find more wrong conclusions, thus eliminating them as possible right solutions and leaving the right answer. In other words, each letter could have one of 26 plug partners and the machine would eliminate the 25 wrong ones.

  The early prototype was called Victory and had a serious limitation which was brilliantly resolved by Welchman. Only certain cribs worked effectively and Turing’s original design would have struggled to find a solution to the example above. It was also restricted to what he called single-line scanning which meant that for each wheel choice and order, 26 electrical tests had to be carried out, one at a time. The physical realization of Welchman’s idea was called the diagonal board and resulted in a huge increase in the power of the bombe. It also delivered the simultaneous scanning feature that Turing wanted, i.e. that at each wheel choice, order and position, 26 electrical tests were carried out simultaneously. A detailed description is given in Appendix 2 but in essence, the device consisted of an array of 26 × 26 (676) electrical terminals that were connected to each other and to the scramblers in the bombe in such a way as to exploit the symmetrical properties of the electrical connections in the Enigma plugboard. It significantly increased the number of false conclusions arrived at from any false initial hypothesis.

  For each of the possible wheel starting positions, the machine automatically carried out an electrical test to determine if the current starting positions were logically consistent with the menu. If the current starting positions satisfied the requirements of the test, then the machine would automatically stop; otherwise it would proceed to test the next set of starting positions. In effect, the Bombe found wrong answers and reduced the impossibly large number of possible starting positions of the Enigma machine when the message was encrypted, to a manageable number. Information provided by the Bombe at the ‘correct stop’ allowed the cryptanalysts to find the complete key as well as the message setting using a range of manual methods.

  Appendix 2

  Enigma and the Bombe in Depth

  By Frank Carter

  The ‘military’ Enigma machine generates a sequence of cipher text letters from the corresponding sequence of plain text letters that are typed on its keyboard. When a letter key is depressed the movement closes a switch under the key and this completes an electrical circuit that lights a lamp (one on a panel of 26 lamps) that indicates the corresponding cipher text letter. The convoluted wiring of this circuit passes through the interior of three moveable wheels or rotors, and also through a plugboard.

  Every rotor (referred to as a wheel in the body of this book) has a set of 26 electrical contacts on each of its opposite sides, with a different internal arrangement of 26 wires connecting the contacts on one side to those on the other, so that when located in the machine every possible combination of the rotational positions of the three rotors will result in a different electrical circuit between the keys and the indicating lamps. The three rotors turn in a way that is somewhat like the motion of the wheels in an odometer fitted in a car, the right-hand rotor turning on by one position for each letter key pressed, and at a particular position, this turning motion causes the middle rotor to turn on by one place. In the same way at a certain position the movement of the middle rotor causes the left-hand rotor to turn on by one place. The design of the machine is such that when a key is pressed the rotors move before the switch under the key closes to complete the electrical circuit and to light one of the lamps.

  The rotor orientations where the ‘turnovers’ take place are determined by the positions of a notch cut into the side of the ring that is fitted round the rim of each rotor, rather like a tyre on a wheel. These rings either have the 26 letters (A–Z) or alternatively the 26 numbers (1–26) inscribed on them (the following exposition will assume them to be letters).

  In the initial setting-up of the machine each ring is made to rotate around the inner core of its rotor to a position where a chosen letter on the ring is aligned with a fixed index mark embossed on the rotor, and it is then locked at this position by a spring clip. These chosen positions are referred to collectively as the ‘ring settings’ of the rotors and as the plain text is ‘typed’ on the keyboard of the machine the ‘turnover’ positions of the middle and left-hand rotors are determined by these settings.

  The rotor ‘turnovers’ have the following unexpected characteristic: every time a key is pressed
on the Enigma machine the right-hand rotor moves on regularly by one position; once in every 26 of these moves (at the turnover position set on the right-hand rotor) the middle rotor will also move on by one position. If this movement of the middle rotor happens to bring it to its own ‘turnover’ position then it will move on again by one position when the next letter key is pressed, and also cause the left-hand rotor to advance by one position. This behaviour is known as the ‘double stepping’ of the middle rotor and it has the effect of reducing the cyclic period of the rotors from the expected value of 26 × 26 × 26 ( = 17,576) to 26 × 25 × 26 ( = 16,900).

  The three chosen rotors are placed side by side in one of the six possible arrangements. When in position, three small viewing windows allow one letter on each of the rotor rings to be visible to the operator. The rotors can then be turned by hand until the three letters chosen for the initial rotor starting positions appear in the three windows. Then each letter of plain text entered on the keyboard will result in the illumination of one of the lamps on the lamp panel indicating the corresponding letter of cipher, the electric current passing first though the plugboard to the rotors, and then again through the plugboard and finally to the lamp panel.

  The function of the plugboard is to enable additional special changes to be made to the electrical circuits connecting the keys to the lamps. For pre-selected pairs of letters this device enables exchanges to be made automatically between the letters in each pair in the electrical circuits between the keyboard and the rotors and again between the rotors and the indicating lamps.

  After passing through the three rotors the electric circuits are connected to another device known as the ‘reflector’; the internal wiring in this has the effect of returning the circuit back through the rotors for a second time but in the reverse direction and following a different path, returning again to the plugboard where further exchanges between the pre-selected pairs of letters are made.

  The Steckers

  The pairs of pre-selected letters that were subjected to these exchanges were known at BP as the ‘stecker pairs’ (Stecker is the German word for ‘plug’). The remaining letters not paired for this purpose were said to be ‘self-steckered’ or ‘unsteckered’. During the war the standard German practice was to select 10 pairs of letters each day, and one of the tasks at BP was to identify these 10 stecker pairs (by default the remaining six letters would be self-steckered).

  The Reciprocal Characteristics of the Machine

  The Enigma machine was designed to have reciprocal characteristics so that the two processes of encrypting and decrypting a message are essentially the same. In order to understand how this can be achieved it is necessary to consider the electrical circuits inside the machine connecting the keys on the keyboard to the indicating lamps on the lamp panel. At each set of rotor positions the effect of the design of the machine is to partition the 26 letters from the alphabet into 13 conjugate pairs so that for every pair one letter will be encrypted as the other and consequently no letter will ever be encrypted as itself. It is important to remember that as the rotor positions change the identity of these conjugate pairs will also change but there will always be 13 of them.

  Two highly simplified versions of the circuit diagram of the machine are given opposite showing only 4 of the keys and 4 of the indicator lamps. A machine based upon this simple circuit would be of no practical use but the electrical principles of the real machine can be readily understood by considering the characteristics of the electric circuits shown in these diagrams.

  The first diagram shows a configuration of the machine for which letter Q is encrypted to letter E. The second diagram of the same Enigma configuration shows the reciprocal process where letter E is encrypted to letter Q.

  The diagrams also show the basic electrical design of the double sockets on the plugboard, where the insertion of a two-pin plug moves the spring-loaded shorting bar across the sockets causing a break in the electrical contact between them and thus enabling the required external ‘crossed’ pair of connections to be made. The diagrams show how the insertion of plugs in sockets ‘Q’ and ‘W’ enables the electrical cross connections to be made to form the stecker pair Q/W.

  The addition of the plugboard to an earlier version of Enigma transformed it into such a formidable cipher machine that throughout WWII the German authorities never seriously thought that it had been broken. The function of the board was to add to the effects of the rotors the further complication of the transposition of selected pairs of letters. The number of pairs subjected to this process changed over time; initially 6 different pairs were selected each day, but by 1939 this had been increased to 10 pairs. So then each day 10 pairs of sockets from the 26 on the plugboard were chosen and these pairs were electrically connected by means of external cables that had special plugs at each end.

  As might be expected the number of possible ways of selecting a set of steckers is a function of the number that are to be selected. Let n represent the number of steckered pairs of letters that are to be selected, so that the number of sockets on the plugboard that will be involved = 2n. The first pair of sockets can be selected in 26C2 ways. After the selection of the first pair has been made from 26 sockets there will be 24 sockets remaining from which the second pair of sockets can be selected. Hence the second pair of sockets can be selected in 24C2 ways. After the selection of the second pair has been made there will be 22 sockets remaining from which the third pair of sockets can be selected and so on. In general, the number of remaining sockets from which the nth pair of sockets can be selected is given by the expression (28 – 2n).

  Hence from this chain of values, the total number (Tn) of possible selections of n pairs of sockets is given by the following expression:

  Hence

  After considerable simplification (by cancellation)

  In this analysis, the order of occurrence of the selected pairs of sockets is not taken into account and hence the total number Tn of possible selections found includes all of the possible orders of arrangement of the n selected pairs of sockets. The total number of arrangements of n pairs of sockets = n!.

  Hence if Sn represents the number of possible selections of n pairs of sockets (when no distinction is made between different orders of arrangement) then it follows that:

  Two numerical examples:

  If n = 1 then S1 = 26!/(2 × 24! × 1) = (26 × 25)/2 ( = 325)

  If n = 2 then S2 = 26!/(4 × 22! × 2) = (26 × 25 × 24 × 23)/8 ( = 44,850)

  It is evident that at this stage the number of possible sets of steckers increases very rapidly!

  The expression for Sn given above is inconvenient to use when calculating the results for larger values of n. An alternative method is to use the ratio

  (As an algebraic exercise the reader may wish to confirm this result.)

  By using this ratio the results for larger values of n can be more readily determined:

  if n = 1: S2/S1 = (24 × 23/4)

  then since S1 = 325, S2 = (24 × 23/4) × 325 ( = 44,850)

  if n = 2: S3 / S2 = (22 × 21)/6

  then since S2 = 44,850, S3 = (22 × 21)/6 × 44,850 ( = 3,453,450)

  This process can be continued for values of n = 3, 4, 5 …. 13.

  Overleaf is a graph of the results obtained in this way.

  It is perhaps surprising that the maximum possible number of stecker pairs is produced when 11 pairs are selected. From the perspective of German security, the greater the number of stecker letter pairs the better, and so 11 pairs would have been the optimal number to use. However the number for 10 pairs is close and slightly reduced the daily task for the Enigma operators when setting up their machines. The value of S10 is approximately equal to 1.5 × 1014 (i.e. about 150 million, million). (About 95% of the letters of cipher were affected by the 10 stecker pairs.)

  The addition of the plugboard to the Enigma machine gave a huge increase in the number of possible keys that could have been used on a given day, and so greatly increased
the security of the system.

  Breaking Enigma ciphers

  In order to be able to read an Enigma message, it was necessary to find the ‘key’ that had been used to encrypt the message. This consisted of four component parts.

  (i)

  The choice and location in the machine of the three rotors used, referred to as the ‘rotor order’;

  (ii)

  The rotor turnover positions for the rotors, given by the ‘ring settings’ that had been selected for the three rotor rings;

  (iii)

  The identity of the set of the 10 ‘steckered pairs’ of letters that had been set up on the plugboard;

  (iv)

  The starting positions of the three rotors that had been used to encrypt the message, known as the ‘message settings’.

  The function of the bombe was to carry out a systematic search to find the following parts of an unknown Enigma key: (a) the rotor order, (b) the rotor ‘core starting positions’ (c) the ‘stecker partner’ of one of the letters on the plugboard.

  The expression ‘core starting positions’ used above is not easy to come to terms with and requires a careful explanation. The ‘core starting positions’ of the rotors are defined by the respective differences (i.e. the number of places in the alphabet) between the letters of the message settings and the corresponding ring settings. For example the ‘message settings’ JHL and ring settings DGR taken together define the rotor ‘core starting positions’; initially of course both of these parameters would be unknown.

  However the ‘core starting positions’ can be represented by many different combinations of rotor settings and ring settings, and by provisionally assuming the ring settings to be Z Z Z, a bombe could be used to find the rotor settings that represented the same unknown rotor ‘core starting positions’. For example with the provisional ring settings Z Z Z, the rotor settings that will give the same ‘core starting positions’ are F A T.