Bombe
From Wikipedia, the free encyclopedia
| The Enigma cipher machine |
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, based on a previous Polish device, was designed by Alan Turing, with an important refinement subsequently contributed by Gordon Welchman.
The Bombe was named after, and inspired by, a cryptologic device designed about October 1938 by Polish Cipher Bureau cryptologist Marian Rejewski, and known as the "cryptologic bomb" (Polish: "bomba kryptologiczna").
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 nearly all the 26 × 26 × 26 = 17,576 possible 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.
Contents |
[edit] The 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 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 × 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 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 P(P(x)) = x.
The encryption can be viewed as first applying P, then S, then P again. Mathematically, the Enigma encryption E can be written: E(x) = P(S(P(x))). The Enigma also has a "self-reciprocal" property: decryption is the same as encryption, so that E(E(x)) = x.
[edit] 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 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.
[edit] 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:
| Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Crib | A | T | T | A | C | K | A | T | D | A | W | N |
| Ciphertext | W | S | N | P | N | L | K | L | S | T | C | S |
Finding cribs was not always straightforward; it required considerable familiarity with German military jargon and the communication habits of the operators (see crib). 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.
[edit] 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.
[edit] 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:
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:
And again, the same sort of reasoning applies at position 7 to get:
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.
[edit] 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.
[edit] In practice
Practical bombes used several stacks of rotors spinning together to test multiple hypotheses 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.
[edit] 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 Welchman methodologies as applied to individual ciphertexts.
[edit] History and use
Using Polish cryptological techniques, British cryptanalysts at Bletchley Park were, at the beginning of World War II, able to read Enigma messages by exploiting weaknesses in German 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 – "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; 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 combinations could be tested in under 6 hours. On average, it took half that time to find the correct match.
There were five bombe outstations off-site at Adstock, Gayhurst, Wavendon, Stanmore, and Eastcote.
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."
In September 2006, it was announced that a team led by John Harper were nearing the end of a 10 year-long project to reconstruct a working Bombe[1].
[edit] The challenge of the four rotor Enigma machine
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 "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 10 feet wide, 7 feet high, 2 feet 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.
[edit] See also
- Cryptanalysis of the Enigma
- Cryptologic bomb - a special-purpose machine designed about October 1938 by Polish Cipher Bureau cryptologist Marian Rejewski to break German Enigma machine ciphers.
- Colossus computer
- Heath Robinson
[edit] References
- Donald Davies, "The Bombe – a Remarkable Logic Machine," Cryptologia, 23(2), April 1999, pp. 108–138.
- Donald Davies, "Effectiveness of the Diagonal Board," Cryptologia, 23(3), July 1999, pp. 229–239.
- John Keen, "Harold 'Doc' Keen and the Bletchley Park bombe," 2003.
- Michael Smith, Station X, Channel 4 Books, 1998, ISBN 0-330-41929-3.
- Gordon Welchman, The Hut Six Story: Breaking the Enigma Codes, M&M Baldwin, 1997, 1998, ISBN 0-947712-34-8.
[edit] External links
- The Turing Bombe – what it was and how it worked by Graham Ellsbury
- Bombe rebuild project
- Tony Sale's description of the British bombe
- A bombe simulator (in Javascript)
- Enigma and the Turing Bombe by N. Shaylor, April 17, 1997. Includes a simulator (a Java applet and C)
- Solving the Enigma – History of the Cryptanalytic Bombe – NSA pamphlet
- The US Navy's Bombe exhibit
- Dayton Codebreakers – documentary on the US Navy's Bombe; information on Desch, personnel of the US Naval Computing Machine Laboratory.
