The machine that lost a war

After the First World War, cipher clerks were the bottleneck of every army: encrypting by hand was slow and error-prone, and the ciphers simple enough to use under fire were breakable. Several inventors had the same idea at the same time: wire the substitution into a rotating disc, and let the machine change the substitution after every letter. Edward Hebern in the United States, Hugo Koch in the Netherlands, Arvid Damm in Sweden, and Arthur Scherbius in Germany, who patented his machine in 1918 and sold it under the name Enigma from 1923. The German navy adopted it in 1926, the army in 1928 and the air force later; by 1945 tens of thousands of machines were in service.

§How Enigma works

Pressing a key closes an electrical circuit that ends in one of 26 lamps. On its way the current passes through:

1. the plugboard (Steckerbrett), where cables swap pairs of letters (ten pairs, by regulation);
2. three rotors, chosen from five and placed in any order; each rotor is a fixed scrambled wiring of 26 contacts on one face to 26 on the other, and its ring setting shifts the wiring relative to the letters on its rim;
3. the reflector (Umkehrwalze), which connects the letters in pairs and sends the current back through the three rotors by a different path;
4. the plugboard again, and a lamp.

Before the current flows, the right rotor turns one step. When it passes its notch, it also turns the middle rotor; when the middle rotor reaches its own notch, it turns the left rotor and itself on the next key press: the famous double step. Because the rotors move, the same letter is encrypted differently every time, and the substitution repeats only after $26\times 25\times 26=16900$ letters.

§A mathematical portrait

Each key press applies a permutation of the 26 letters. Write $P$ for the plugboard, $R_1,R_2,R_3$ for the three rotors in their current positions (right, middle, left) and $U$ for the reflector. The current goes through $P$, $R_1$, $R_2$, $R_3$, $U$ and back, so the permutation is

Proof

Write $S=R_3{R}_2{R}_{1}P$, so $E=S^{-1}US$. The reflector pairs letters, so $U^2=\mathrm{id}$ and $U(y)\ne y$ for every $y$. Then $E^2=S^{-1}US{S}^{-1}US=S^{-1}{U}^{2}S=\mathrm{id}$. And if $E(x)=x$ then $U(S(x))=S(x)$, a fixed point of $U$, which does not exist.

The symmetry was a convenience: the same machine, with the same settings, both encrypted and decrypted. The lack of fixed points was a gift to the enemy, as the crib attack below shows.

Counting the plugboard

Choose which 20 letters are plugged and how they pair up, leaving 6 unplugged. Line up the 26 letters in any order ($26!$ ways), plug the first 20 in consecutive pairs and leave the last 6 alone. Each wiring is counted $6!$ times (order of the unplugged letters) $\times 10!$ (order of the pairs) $\times 2^{10}$ (order inside each pair).

Almost all of that number comes from the plugboard. Rejewski's genius was to find a quantity that the plugboard does not change.

§Rejewski: a theorem breaks Enigma

In 1932 the Polish Cipher Bureau gave the problem to Marian Rejewski, a 27-year-old mathematician from Poznań, and later to Jerzy Różycki and Henryk Zygalski. The German procedure helped them: each message began with a three-letter message key, chosen by the operator, encrypted twice at the day's setting (“to make sure it arrives”). So letters 1 and 4 of every message were encryptions of the same letter, and so were 2 and 5, and 3 and 6. Calling $A,B,\dots ,F$ the permutations at the first six positions, the day's messages revealed the products $AD$, $BE$, $CF$ (if $A(x)=y$ and $D(x)=z$, then $AD$ sends $y$ to $z$, since $A$ is an involution).

Proof

If $(x_1{x}_2\dots x_k)$ is a cycle of $\sigma$, then $({\pi }^{-1}(x_1)\dots {\pi }^{-1}(x_k))$ is a cycle of ${\pi }^{-1}\sigma \pi$: indeed ${\pi }^{-1}\sigma \pi ({\pi }^{-1}(x_i))={\pi }^{-1}(\sigma (x_i))={\pi }^{-1}(x_{i+1})$. Relabelling the letters by ${\pi }^{-1}$ maps cycles to cycles of the same length.

The plugboard enters $AD$ only by conjugation, so the cycle structure of $AD$, $BE$ and $CF$ depends only on the rotor order and positions: $6\times 17576=105456$ possibilities, a number small enough to catalogue. The Poles built a machine, the cyclometer, to compute the catalogue, and from 1933 they read German traffic routinely. Rejewski had also reconstructed the wiring of the rotors, using the theory of permutations together with operating manuals and old keys sold to French intelligence (Gustave Bertrand) by a German clerk, Hans-Thilo Schmidt.

The Germans changed procedures and added two rotors in 1938, multiplying the work by ten. On 25 July 1939, five weeks before the invasion of Poland, the Poles met their British and French allies in the Pyry forest near Warsaw and gave them everything: their methods, Zygalski's perforated sheets and two reconstructed Enigma machines.

§Bletchley Park and the crib

At Bletchley Park, the British code-breaking centre, Alan Turing designed a new machine, the bombe (1940), improved by Gordon Welchman's diagonal board. It did not need the doubled message key, which the Germans dropped in May 1940. It needed a crib: a guess of some plaintext and its position. Military messages were full of them: WETTERBERICHT (weather report), KEINE BESONDEREN EREIGNISSE (nothing to report), call signs, ranks, the same greeting every morning.

The theorem above tells where a crib can go: since no letter encrypts to itself, any position where a crib letter coincides with the ciphertext letter below it is impossible. Sliding the crib along the ciphertext eliminates most positions at once; for each survivor, the bombe tested all rotor orders and positions against the chain of letter pairs the crib implied.

Navy Enigma, with four rotors from 1942 and stricter procedures, resisted longer; Joan Clarke, Turing and Hugh Alexander attacked it with Banburismus, a statistical method, and with codebooks captured from U-boats and weather ships (U-110 in May 1941, U-559 in October 1942). The intelligence, codenamed Ultra, was distributed with extreme care so that the Germans would not suspect. Historians estimate that it shortened the war in Europe by up to two years.

Not only Enigma. The German high command used a different machine, the Lorenz SZ40/42 teleprinter cipher. Bill Tutte reconstructed its logic in 1942 without ever seeing one, and Tommy Flowers built Colossus (1944) to attack it: the first programmable electronic digital computer.

§Why Enigma fell

• A structural flaw: no letter encrypts to itself, which turns every crib into a filter.
• Procedures that repeat information: the doubled message key gave Rejewski his equations.
• Predictable plaintext: weather reports, formulaic greetings, “nothing to report”.
• Human shortcuts: operators chose message keys like AAA or their girlfriend's initials (the “cillies”).
• Overconfidence: a key space of $2^{67}$ looked unbreakable, and the Germans never seriously considered that the machine was being read.

Every one of these lessons reappears in modern cryptography. The next chapter asks the opposite question: is there a cipher that cannot be broken at all?

§Further reading

1. Marian Rejewski, “How Polish mathematicians deciphered the Enigma”, Annals of the History of Computing 3(3), 1981.
2. Gordon Welchman, The Hut Six Story (1982).
3. Andrew Hodges, Alan Turing: The Enigma (1983).
4. Tony Sale's Codes and Ciphers pages and the Bletchley Park Trust archives.