Bombe

The Bombe replicated the action of several Enigma machines wired together. Each of the rapidly rotating drums, pictured above in a Bletchley Park museum mockup, simulated the action of an Enigma rotor.

Template:EnigmaSeries In the history of cryptography, a bombe was an electromechanical machine used by British and American codebreakers to help break German Enigma machine signals during World War II. The bombe was invented by Alan Turing with an important refinement suggested by Gordon Welchman. Using the Turing-Welchman bombe, the Allies were able to read a high proportion of the German Enigma traffic, and it was the primary tool used for this purpose.

The bombe was named after, and possibly inspired by, an earlier Enigma codebreaking device designed by Polish cryptanalyst Marian Rejewski, known as the Bomba.

The standard services Enigma contained a set of three rotors, each of which could be set in any of 26 positions. The bombe worked by trying each possible rotor position and applying a certain test. The test would eliminate most of the 26×26×26=17576 positions of all three rotors, and the few remaining settings could be examined by hand. However, in order to use a bombe, a cryptanalyst first had to produce a so-called crib — a section of the ciphertext where he knew (or could guess) the corresponding plaintext.

The Enigma machine

Main article: Enigma machine

The German Army and Air Force Enigma machines used a stack of three rotors with 26 electrical contacts on each end. The wiring between the input and output contacts within each rotor was scrambled. The three rotors were connected to a reflecting rotor, which redirected current back through the rotors by a different path. The set of rotors and the reflector is termed the scrambler, denoted by S in this article. Each rotor could be set into one of 26 positions, resulting in 26 × 26 × 26 = 17,576 possible ways the rotor stack could rearrange the letters of the alphabet. The initial positions of the rotors formed part of the secret key of the Enigma, and purpose of the bombe was to recover these positions of the rotors. At each step of the encryption, at least one of the rotors (the "fast rotor") advanced a position. At certain points the other rotors were also advanced, but when using the bombe, it was, for a small stretch of letters, assumed that only the fast rotor moved, and that the others remained stationary. We denote this by writing S₁ for some given position of the scrambler, and S₂ for the same position but with the fast rotor advanced one position, and similarly S₃, S₄ and so forth.

An additional complication in the German military Enigma machines was a plugboard (Steckerbrett in German, shortened to "Stecker") that further scrambled the letters. The large number of possible stecker wirings made cryptanalysis much more difficult. Letters were swapped in pairs: if A was transformed into R then R was transformed into A. This regularity was exploited by Welchman's "diagonal board" enhancement to the bombe. Here, we denote the plugboard by P. Because the plugboard simply swapped pairs, applying P twice restored the original, so that <math>P(P(x)) = x<math>.

The encryption can be viewed as first applying P, then S, then P again. Mathematically, the Enigma encryption E can be written: <math>E(x)=P(S(P(x)))<math>. The Enigma also has a "self-reciprocal" property: decryption is the same as encryption, so that <math>E(E(x))=x<math>.

The principle of the bombe

In the bombe, a set of rotors with the same internal wiring as the German Enigma rotors was used — but designed to be spun by a motor, stepping through all possible rotor settings. The bombe rotors had a double set of contacts and wiring to emulate the Enigma reflection. A bombe would consist of a number of these sets of rotors wired up according to a menu prepared by codebreakers. At each position of the rotors, an electrical test would be applied. For a large number of the settings, the test would lead to a logical contradiction, ruling out that setting. If the test did not lead to a logical contradiction, the machine would stop, and the candidate solution would be examined further, typically on a replica of the German Enigma machine. There might be incorrect guesses and many false matches before the correct match was found.

Cribs

The test worked by making deductions from a short piece of known (or guessed) plaintext, known as a crib. For example, a codebreaker might suspect that the phrase ATTACKATDAWN was the message corresponding to a certain stretch of ciphertext, say, WSNPNLKLSTCS:

Finding cribs was not always straightforward; it required considerable familiarity with German military jargon and the communication habits of the operators. However, the codebreakers were aided by the fact that the Enigma would never encrypt a letter to itself. This helped in locating the position of a crib in a plaintext, as it could rule out a number of positions where a letter from the crib "clashed" with the same letter in the ciphertext.

The plugboard

The German military Enigma included a plugboard (P) which provided a secret wiring which swapped letters before and after the main scrambler (S). If there had been no plugboard, it would have been relatively straightforward to test a rotor setting; a replica Enigma could be set up and the crib letter A encrypted on it, and compared with the ciphertext, W. If they matched, the next letter would be tried, checking that T encrypted to S and so on for the entire of the crib. If at any point the letters failed to match, the initial rotor setting would be rejected; most incorrect settings would be ruled out after testing just two letters. This test could be readily mechanised and applied to all 17,576 settings of the rotors.

However, with the plugboard, it was much harder to perform trial encryptions because it was unknown what the crib and ciphertext letters were transformed to. For example, in the first position, P(A) and P(W) were unknown because the plugboard settings were unknown.

Reasoning about steckered values

Turing's solution was to note that, even though the values for, say, P(A) or P(W), were unknown, the crib still provided known relationships amongst these values; that is, the values after the plugboard transformation. Using these relationships, a cryptanalyst could reason from one to another and, potentially, derive a logical contradiction, in which case the rotor setting under consideration could be ruled out

A worked example of such reasoning might go as follows: a cryptanalyst might guess that P(A)=Y. Looking at position 10, we notice that A encrypts to T, or, expressed as a formula:

<math>\texttt{T} = P(S_{10}(P(\texttt{A})))<math>

Because P is its own inverse, we can apply the function to both sides to obtain the following equation:

<math>P(\texttt{T}) = S_{10}(P(\texttt{A})))<math>

This gives us a relationship between P(A) and P(T); if P(A)=G, and for the rotor setting under consideration, S₁₀(Y)=Q (say), we can deduce that

<math>P(\texttt{T}) = S_{10}(P(\texttt{A}))) = S_{10}(\texttt{Y})=\texttt{Q}.<math>

While the crib does not allow us to determine what the values after the plugboard are, it does provide a constraint between them. In this case, it shows how P(T) is completely determined if P(A) is known.

Likewise, we can also observe that T encrypts to W at position 2. Using S₂, we can deduce the steckered value for W as well using a similar argument, to get, say,

<math>P(\texttt{W}) = S_{2}(P(\texttt{T}))) = S_{2}(\texttt{Q})=\texttt{Y}.<math>

Furthermore, we notice that in position 1, A encrypts to W. As the Enigma machine is self-reciprocal, this means that at this position W would also encrypt to A. Knowing this, we can apply the argument once more to deduce a value for P(A), say,

<math>P(\texttt{A}) = S_{1}(P(\texttt{W}))) = S_{1}(\texttt{Y})=\texttt{F}.<math>

However, in this case, we have derived a contradiction, since, by hypothesis, we assumed that P(A)=Y at the outset. This means that the initial assumption must have been incorrect, and so that (for this rotor setting) P(A)≠Y (this type of argument is termed "reductio ad absurdum" or "proof by contradiction").

For a single setting of the rotors, a cryptanalyst could try each possibility for P(A); if all of the possibilities lead to a contradiction, then the rotor setting can be eliminated from consideration. The bombe mechanises this process, performing the logical deductions near-instantaneously using electrical connections, and repeating the test for all 17,576 possible settings of the rotors.

Automating deduction using an electrical circuit

To automate these logical deductions, the bombe took the form of an electrical circuit. Current flowed around the circuit near-instantaneously, and represented all the possible logical deductions which could be made at that position. To form this circuit, the bombe used several sets of Enigma rotor stacks wired up together according to the instructions given on a menu, derived from a crib. Because each Enigma machine had 26 inputs and outputs, the replica Enigma stacks are connected to each other using 26-way cables. In addition, each Enigma stack rotor setting is offset a number of places as determined by its position in the crib; for example, an Enigma stack corresponding to the fifth letter in the crib would be four places further on than that corresponding to the first letter.

In practice

Practical bombes used several stacks of rotors spinning together to test multiple hypothesis about possible setups of the Enigma machine, such as the order of the rotors in the stack.

While Turing's bombe worked in theory, it required impractically long cribs to rule out sufficiently large numbers of settings. Gordon Welchman came up with a way of using the symmetry of the Enigma stecker to increase the power of the bombe. His suggestion was an attachment, called the diagonal board, that further improved the bombe's effectiveness.

The British bombe

The bombes were built by the British Tabulating Machine company at Letchworth. The machine was built under the direction of Harold 'Doc' Keen and was codenamed CANTAB. Each British bombe was about 7 feet wide, 6 feet 6 inches tall and 2 feet deep and weighed about a ton. On the front of each bombe were 108 places where rotors could be mounted. The rotors were in three groups of 12 triplets. Each triplet, arranged vertically, corresponded to the three Enigma rotors. The bombe rotors had a double set of contacts and wiring to emulate the Enigma reflection. The input and output of each triplet of rotors went to cable connectors, allowing the bombe to be rewired according to the Turing and Wlechman methodologies as applied to individual ciphertexts.

History and usage

Using Polish codebreaking techniques, British cryptanalysts at Bletchley Park were, at the beginning of World War II, able to read Enigma messages by exploiting weaknesses in the German operating procedure. There was the concern that the Germans might at any point change their procedure rendering the current methods obsolete.

To preempt this, British mathematician Alan Turing designed the bombe on a more general principle — the assumption of the presence of text that analysts could guess somewhere in the message, a cryptanalytical technique known as cribbing, also termed a known plaintext attack.

The first bombe, which was based on Turing's original design and so lacked a diagonal board, arrived at Bletchley Park in March 1940 and was named "Victory". The second bombe — "Agnus" — was equipped with Welchman's diagonal board, and was installed on 8 August 1940; bombes of this type were called "Spider" bombes.

By the end of March 1941, a more advanced version of the Bombe had been developed, the "Jumbo" machine.

During 1940, 178 messages were broken on the two machines, nearly all successfully. By the end of 1941, there were 16 bombes in use. By the end of 1942, this had increased to 49 bombes; at the end of 1943, this figure had more than doubled to 99 bombes in operation. By May 1945, there were 211 operational machines, and required nearly 2,000 staff to operate.

The Germans generally changed settings each day at midnight, the British goal was to find the new settings before the day was out, preferably by noon. With a motor spinning at 120 RPM, all combinations would be tested in under 6 hours. On average it would take half that time to find the correct match.

After World War II, Winston Churchill ordered all the bombes destroyed, so no original material remains, although such an order appears to contradict the often-repeated story that use of Enigmas after the War was still encouraged, so the Allies could continue to read traffic from other countries.

United States Navy bombes

US bombe

By late 1941 the change in German Navy fortunes combined with his intelligence reports led Admiral Karl Dönitz to become convinced that the Allies could read Navy communications and a fourth thin rotor with unknown wiring was added to German Navy systems to produce the Triton system, with a lock-out which would allow them to remain compatible with three rotor machines when necessary. As before, the unknown wiring would prevent the reading of the messages. Fortunately for the Allies, in December 1941, before the machine went into official service, a submarine accidentally sent a message with four rotors, then sent the same message using only three, disclosing the wiring of the extra rotor. In February 1942 the change became official and the ability to read the critical messages for the submarines largely ceased until new equipment became available which could use the information about the fourth rotor wiring to decrypt messages.

That spring was known as the "Happy Time" for the submarines, with renewed success in their attacks on shipping due in part to the security of their communications and the German ability to read the convoy messages sent in Allied Naval Cipher No. 3 and find out where the convoys were. Between January and March 1942 submarines sank 216 ships off the US East Coast. In May 1942 the US switched for the first time to using a convoy system and to requiring blackouts of coastal cities so ships wouldn't be silhouetted against their lights but the improvement was small.

An urgent work plan to design bombes which could decrypt the four rotor system, with delivery scheduled for August or September of 1942, was begun at Bletchley Park. The urgent need, doubts about the British design and slow progress with it prompted the US to start investigating designs for a parallel effort, based in part wiring diagrams provided to US Navy officers during a visit to Bletchley park in July 1942. Funding for a full US development effort was requested on 3 September 1942 and approved the following day.

The U.S. bombes became available starting in late May 1943. They were 10 feet wide, 7 feet high, 2 feet deep and weighed about 2 1/2 tons. About 120 were made before production was stopped in September, 1944 due to rapid progress in the war. The last manufactured United States bombe is on display at the National Cryptologic Museum. Jack Ingram, Curator of the museum, describes being told of the existence of a second and searching for it but not finding it whole. Whether it remains in storage in pieces, waiting to be discovered, or no longer exists, is unknown.

References

• Donald Davies, The Bombe — a Remarkable Logic Machine, Cryptologia, 23(2), April 1999, pp108–138.
• Donald Davies, Effectiveness of the Diagonal Board, Cryptologia, 23(3), July 1999, pp229–239.
• John Keen, "Harold 'Doc' Keen and the Bletchley Park bombe", 2003.
• Gordon Welchman, "The Hut Six Story: Breaking the Enigma Codes", M&M Baldwin, 1997, 1998. ISBN 0-947712-34-8

External links

• The Turing Bombe — what it was and how it worked (http://www.ellsbury.com/bombe1.htm) by Graham Ellsbury
• Bombe rebuild project (http://www.jharper.demon.co.uk/bombe1.htm)
• Tony Sale's description of the British bombe (http://www.codesandciphers.org.uk/virtualbp/tbombe/tbombe.htm)
• A bombe simulator (in Javascript) (http://www.codesandciphers.org.uk/virtualbp/tbombe/bombesc.htm)
• Enigma and the Turing Bombe (http://frode.home.cern.ch/frode/crypto/Shaylor/bombe.html) by N. Shaylor, April 17, 1997. Includes a simulator (a Java applet and C)
• Solving the Enigma — History of the Cryptanalytic Bombe (http://ed-thelen.org/comp-hist/NSA-Enigma.html) — NSA pamphlet
• The US Navy's Bombe exhibit (http://www.nsa.gov/museum/museu00025.cfm)de:bomba