In the history of cryptography, the Bombe was an electromechanical device used by British cryptologists to help break German Enigma machine signals during World War II. The bombe was designed by Alan Turing, with an important refinement suggested by Gordon Welchman.
The Bombe was named after, and inspired by, a cryptologic device designed in 1938 by Polish Cipher Bureau cryptologist Marian Rejewski, and known as the "cryptologic bomb" (Polish: "bomba kryptologiczna"). They were also referred to by Group Captain Winterbotham as "Bronze Goddesses" because their cases were made of bronze, but they were more prosaically described by operators as being "like great big metal bookcases".
A standard services Enigma employed, at any one time, a set of three rotors, each of which could be set in any of 26 positions. The bombe tried each possible rotor position and applied a certain test. The test eliminated thousands of positions of the three rotors; the few potential solutions were then examined by hand. In order to use a bombe, however, a cryptanalyst first had to produce a "crib" – a section of ciphertext for which he could guess the corresponding plaintext.
The German Army and Air Force Enigma machines, and initially those used by the German Navy, 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 non-rotating reflecting drum, or reflector, which redirected electrical current back in reverse order through the rotors. 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 × 25 × 26 = 16,900 (not 26 X 26 X 26 because of the double stepping of the second rotor, see ). 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 the 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 S1 for some given position of the scrambler, and S2 for the same position but with the fast rotor advanced one position, and similarly S3, S4 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 .
The encryption can be viewed as first applying P, then S, then P again. Mathematically, the Enigma encryption E can be written: . The Enigma also has a "self-reciprocal" property: decryption is the same as encryption, so that .
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 ring a bell, and the candidate solution would be examined further, typically on a replica of the German Enigma machine, to see if that decryption produced German. There might be incorrect guesses and many false matches before the correct match was found.
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.
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:
Because P is its own inverse, we can apply the function to both sides to obtain the following equation:
This gives us a relationship between P(A) and P(T); if P(A)=Y, and for the rotor setting under consideration, S10(Y)=Q (say), we can deduce that
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 L at position 8. Using S8, we can deduce the steckered value for L as well using a similar argument, to get, say,
Similarly, in position 6, K encrypts to L. As the Enigma machine is self-reciprocal, this means that at the same position L would also encrypt to K. Knowing this, we can apply the argument once more to deduce a value for P(K), which might be:
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.
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.
Using Polish cryptological techniques, British cryptanalysts at Bletchley Park were, at the beginning of World War II, able to read German army and air force Enigma messages by exploiting weaknesses in operating procedures. The British cryptologists were concerned that the Germans might at any moment change their procedures, rendering those cryptological 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." (Actually, the Poles had likewise exploited "cribs," e.g. the Germans' use of "ANX" — German for "To," followed by "X" as a spacer.) 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 – "Agnes" – 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; at the end of 1943, that figure had more than doubled to 99 bombes in operation. By May 1945, there were 211 operational machines, requiring nearly 2,000 staff to run.
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 permutations could be tested in under 6 hours. On average, it took half that time to find the correct match.
Once the British had given the Americans the details about the bombe and its use, the US had the National Cash Register Company manufacture a great many additional bombes, which they (the US) then used to assist in the code-breaking. These ran much faster than the British version, so fast that unlike the British model, which would freeze immediately (and ring a bell) when a possible solution was detected, the NCR model, upon detecting a possible solution, had to "remember" that setting and then reverse its rotors to back up to it (meanwhile the bell rang).
After World War II, some fifty bombes were retained at Eastcote, while the rest were destroyed. The surviving bombes were put to work, possibly on Eastern bloc ciphers (Smith, 1998). The official history of the bombe states that "some of these machines were to be stored away but others were required to run new jobs and sixteen machines were kept comparatively busy on menus. It is interesting to note that most of the jobs came up and the operating, checking and other times maintained were faster than the best times during the war periods."
By late 1941 the change in German Navy fortunes, combined with intelligence reports, convinced Admiral Karl Dönitz that the Allies could read German Navy communications, and a thin fourth rotor with unknown wiring was added to German Navy Enigmas to produce the Triton system. The Triton had a lock-out that allowed it to remain compatible with three-rotor machines when necessary. As before, the unknown wiring would prevent unauthorized reading of messages. Fortunately for the Allies, in December 1941, before the machine went into official service, a submarine accidentally sent a message using four rotors, then the same message again using only three, thus disclosing the wiring of the extra rotor. In February 1942 the change in number of rotors used became official, and British ability to read German submarines' messages largely ceased until new equipment became available that could use the information about the fourth-rotor wiring.
That spring was the "second happy time" for the submarines, with renewed German success in attacking Allied shipping due to the security of their own communications and their ability to read convoy messages sent in Allied Naval Cipher No. 3. Between January and March 1942, German submarines sank 216 ships off the US East Coast. In May 1942 the US began using the convoy system and requiring blackouts of coastal cities so that ships would not be silhouetted against their lights, but this yielded only slightly improved security for Allied shipping.
A crash program was begun at Bletchley Park to design bombes that could decrypt the four-rotor system, with delivery scheduled for August or September 1942. 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 on 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. Development was led by Joseph Desch of the National Cash Register Company at the United States Naval Computing Machine Laboratory in Dayton, Ohio.
The U.S. bombes became available starting in late May 1943. They were wide, high, deep and weighed 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 bombe 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.