The Turing Bombe: Crib Graphs, Welchman's Diagonal Board & Deductive Contradiction

1. Historical Origins: From Poland's Bomba to Bletchley Park Hut 8

In December 1932, young Polish mathematician Marian Rejewski achieved one of history’s greatest cryptanalytic triumphs by mathematically reconstructing the internal wiring of the German military Enigma machine using permutation group theory. Rejewski’s automated electromechanical solver, the Bomba Kryptologiczna (comprising six coupled Enigma rotor units), operated by exploiting the German operational protocol of double-enciphering the three-letter message key at the beginning of each transmission (e.g. key "QWE" transmitted as "QWEQWE").

However, in May 1940, the German military abruptly altered their operational procedures: operators ceased transmitting double indicators, rendering Poland’s Bomba obsolete overnight. The Allied war effort faced an intelligence blackout.

At Bletchley Park (Station X in Buckinghamshire), British mathematician Alan Turing recognized that codebreaking could no longer depend on procedural mistakes in message preambles. Instead, it had to exploit stereotyped operational text—a technique known as known-plaintext cryptanalysis. Turing termed these suspected plaintext fragments "cribs."

German military transmissions were notoriously ritualistic: U-boats and weather stations transmitted daily morning reports opening with predictable phrases such as "WETTERVORHERSAGE" (Weather Forecast) or "KEINE BESONDEREN EREIGNISSE" (Nothing to report). By aligning an intercepted ciphertext against a hypothesized crib, Turing designed an entirely new electromechanical machine: the British Bombe. Engineered in metal by Harold "Doc" Keen at the British Tabulating Machine Company (BTM) in Letchworth, the first prototype ("Victory") began operational testing in March 1940.

2. Crib Menus & Graph Theory: Vertices, Edges & Loops

To break an Enigma transmission with the Bombe, codebreakers in Hut 8 first constructed a "Menu"—a directed multigraph derived from the alignment of a crib against the ciphertext.

Formally, let the alphabet be the vertex set V = {A, B, ..., Z}. At every character index t (1 ≤ t ≤ N) where the crib specifies plaintext letter M_t and the radio intercept yields ciphertext letter C_t, an edge connects vertex M_t and vertex C_t with label t.

The fundamental algebraic relationship at time step t is given by:

C_t = P · S_t · P⁻¹ (M_t)

Where P represents the Steckerbrett (plugboard) permutation, P⁻¹ = P is its self-reciprocal involution, and S_t = R_t⁻¹ · U · R_t is the scrambler permutation created by the internal rotors and reflector at mechanical step t.

Rewriting this equation isolating the internal rotor transformation yields:

P(C_t) = S_t (P(M_t))

Crucially, notice that while the rotor permutation S_t advances mechanically with every keystroke, the plugboard permutation P remains completely CONSTANT throughout the entire transmission. A closed cycle in the menu graph (e.g. E linked to B at step 1, B linked to R at step 4, and R linked to E at step 7) creates an electrical feedback loop that constrains the allowable rotor states to a microscopic fraction of the key space.

3. The Principle of Deductive Contradiction (Reductio Ad Absurdum)

The central genius of Alan Turing’s design lies in how the Bombe evaluated candidate rotor settings. Rather than searching for the "correct" key (which is overwhelmingly slow), the Bombe searched for logical contradictions (Reductio Ad Absurdum).

For any candidate rotor orientation (say Rotor I, II, III at dial setting B-F-K):

1. The operator selects a test letter from the crib menu (e.g. letter "E") and injects an electrical current into a hypothesized plugboard wire, say assuming P(E) = A.

2. This electrical signal propagates through the banks of rotating drums representing each edge in the crib graph. At each edge, the drum scrambles the current forward through the rotors, reflects it, and scrambles it backward.

3. The resulting output current defines the implied plugboard connection for the adjacent vertex letter. That implied connection feeds into the next edge of the menu graph, triggering a cascade of secondary and tertiary electrical deductions.

4. If the initial hypothesis P(E) = A is FALSE, the cascading electrical currents spread across alternative circuit paths, energizing letter after letter until all 26 lamp contacts on the test register are illuminated. An illumination of all 26 contacts constitutes a PROOF OF CONTRADICTION, meaning the hypothesis P(E) = A is physically impossible.

5. If all 26 hypotheses for letter E (P(E) = A, P(E) = B, ..., P(E) = Z) lead to all 26 contacts energizing, the candidate rotor setting B-F-K is mathematically IMPOSSIBLE and the Bombe’s drive motor advances to the next position without stopping.

A "STOP" occurs only when current fails to energize all 26 contacts. In that rare event, exactly 1 wire remains unenergized (or 25 wires remain dark), isolating the single mathematically consistent plugboard assignment and preserving that rotor position for human verification.

4. Welchman's Diagonal Board: The Involution Matrix

Turing’s original Bombe design suffered from a severe limitation: it required crib menus with multiple tightly interlocked closed loops. If a crib had only open branching trees or a single weak loop, the electrical current could not circulate sufficiently to produce contradictions, causing the machine to produce hundreds of false stops.

In early 1940, Gordon Welchman discovered a mathematical property of the Steckerbrett that revolutionized Bletchley Park codebreaking. Welchman realized that the plugboard is strictly self-reciprocal (an involution without fixed points for plugged letters):

P(X) = Y ⟺ P(Y) = X

In Turing’s original circuitry, if an electrical path deduced that letter G was plugged to letter K (P(G) = K), that deduction did not automatically inform the machine that letter K was plugged to letter G. Welchman conceived the "Diagonal Board"—an electromechanical crossbar matrix consisting of a 26 × 26 grid of electrical terminals where terminal (x, y) was permanently hardwired to terminal (y, x).

Whenever current energized terminal Y on the X-row, the diagonal board instantaneously cross-connected and energized terminal X on the Y-row. This reciprocal feedback caused constraint deductions to explode through the entire circuit across every letter simultaneously.

The impact was seismic: crib menus no longer required complex multiple loops. A menu with even a single loop—or even an open tree with diverse character links—could eliminate false hypotheses with 99.99% certainty.

5. Combinatorial Speedup: Collapsing 10²⁰ States to 10⁶

The Enigma machine boasted a theoretical key space of 1.58 × 10²⁰ states. Why was an electromechanical device built with 1940s technology able to crack it in under 20 minutes?

The mathematical answer lies in the algebraic decoupling of the rotor core from the plugboard:

1. The Steckerbrett plugboard accounts for 1.507 × 10¹⁴ combinations (over 99.9999% of Enigma’s key space). However, the plugboard is an external symmetric conjugate mapping: it does NOT alter the cycle structure of the internal rotor scrambler.

2. By using the crib menu and diagonal board, the Bombe deduces the plugboard connections purely as a byproduct of electrical current propagation. The Bombe NEVER searches through plugboard combinations!

3. Therefore, the physical search space is reduced solely to the mechanical rotor configurations: 60 possible wheel orders × 17,576 rotor positions = 1,054,560 candidate states.

Operating with banks of 36 Enigma equivalents spinning at 120 RPM, a single British Bombe scanned all 17,576 positions for a given rotor wheel order in approximately 12 to 15 minutes. By 1943, Bletchley Park operated over 200 Bombes, deciphering up to 4,000 German military signals every day.

6. Worked Deduction Trace: The "WETTER" Weather Intercept

Let us trace an authentic deduction chain using a Kriegsmarine weather intercept.

Ciphertext fragment: "KBZGRAUYDUWOL" | Known crib: "WETTERBERICHT"

Notice the crib character repetitions: letter "E" appears at positions 2, 5, and 8; letter "T" appears at positions 3 and 4; letter "R" appears at positions 6 and 10.

Consider testing rotor position (0, 0, 0) with Rotors I, II, III and Reflector B. We establish our test register on letter "E":

7. Complete Python Implementation: Menu Solver & Self-Test

Below is a production-grade, standalone Python implementation of the Turing Bombe contradiction engine. It models the internal scramblers of Rotors I, II, and III, constructs crib constraint graphs, and applies Welchman’s diagonal board symmetry to isolate authentic rotor stops.

8. Practice Cryptanalysis: The Hut 8 Naval Weather Intercept

Test your skills as a Bletchley Park cryptanalyst in Hut 8. Intelligence has intercepted an encrypted Kriegsmarine radio dispatch, and weather reconnaissance confirms the transmission contains the standard morning weather greeting:

9. Interactive Turing Bombe Workbench

Experience the electromechanical brilliance of Alan Turing and Gordon Welchman directly in your browser. Use the official CipherVerse Turing Bombe Simulator to input custom ciphertexts, formulate crib menus, and observe contradiction reduction in real time.

Everything executes completely client-side inside your browser with zero server data retention.