Bombe

In the history of cryptography, the bombe was an electromechanical device used by British and American cryptologists to help break German Enigma machine signals during World War II. The bombe was designed by Alan Turing, with an important refinement subsequently contributed by Gordon Welchman.

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:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: exttt{T} = P(S_{10}(P( exttt{A})))

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:P( exttt{T}) = S_{10}(P( exttt{A})))

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:P( exttt{T}) = S_{10}(P( exttt{A}))) = S_{10}( exttt{Y})= exttt{Q}.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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 S2, we can deduce the steckered value for W as well using a similar argument, to get, say,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:P( exttt{W}) = S_{2}(P( exttt{T}))) = S_{2}( exttt{Q})= exttt{G}.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:P( exttt{A}) = S_{1}(P( exttt{W}))) = S_{1}( exttt{G})= exttt{F}.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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").

Related Topics:
Contradiction - Reductio ad absurdum

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~