SIGABA — Volume 8 — Why It Was Never Broken — Key Space and Modern Cryptanalysis

8.1 About This Volume

Volume 1 gave the short answer to why no one broke the SIGABA, and the historical evidence for it: German cryptanalysts studied American five-letter traffic in 1944 and gave it up “as unprofitable”, and their best man knew of no American machine but the Hagelin they did read. This volume gives the long answer, in numbers. It counts the key space carefully, because published figures range from 2^78 to 2^107 depending on what is counted; explains why each of the wartime methods of attacking rotor machines fails against the SIGABA’s stepping; and then describes the attacks that modern cryptologists have actually made, from John Savard and Richard Pekelney’s method for messages in depth (1999), through Mark Stamp and Wing On Chan’s known-plaintext attack (2007), to George Lasry’s meet-in-the-middle attack (2019) and its successor (2023).

The numbers come from the unit’s tools: sigaba_attack.py --keyspace, --index-space, --stats and --rate, which use the simulator sigaba_sim.py (Volume 11 lists its self-tests). Where a figure is someone else’s estimate, it is cited to them.

8.2 What “Never Broken” Means

“Never broken” is a claim about evidence, and the evidence has a particular shape. It is not that the Axis tried every method and failed; it is that the files and interrogations of German cryptanalytic agencies collected by TICOM after the war show the SIGABA traffic studied, unclassified and abandoned, and nothing at all from the Japanese side (Volume 1; Volume 9). The machine was never captured intact. The nearest miss, the theft of a truck carrying a SIGABA at Colmar in February 1945, ended five weeks later with the machine and its rotors recovered, unopened, from a river; even so, Eisenhower ordered a new set of wheels for every machine (Volume 6).

So the question this volume answers is not whether German cryptanalysts were careless but what they would have faced had they had every advantage. The standard advantage granted in modern analyses is very large: the attacker is assumed to know the wiring of every wheel. No wartime wiring has ever been published (Volume 3 explains why the simulator uses an invented set), and the Germans never had one.

8.3 Counting the Key Space

The key of a SIGABA, given the wheels, is the arrangement and setting of fifteen wheels. Counted step by step:

Table 1 — The key of a SIGABA, given the wheels, is the arrangement and setting of fifteen wheels. Counted step by step

Element	Count	log2
Order of the ten code wheels in ten slots (5 Alphabet + 5 Stepping)	10! = 3,628,800	21.8
Each code wheel normal or reversed	2^10 = 1,024	10.0
Starting positions of the ten code wheels	26^10	47.0
Code wheels together	about 5.2 × 10^23	78.8
Index wheels: order × positions	5! × 10^5 = 12,000,000	23.5
Nominal total	about 6.3 × 10^30	102.3
Index Maze: distinct effects on the stepping magnets	10!/2^5 = 113,400	16.8
Practical total (code wheels × index effects)	about 5.9 × 10^28	95.6

The first four rows are uncontroversial; Mucklow’s NSA history gives the same 5.2 × 10^23 (Mucklow 2015, Appendix A). The difference between the nominal 2^102.3 and the practical 2^95.6 is the index bank’s redundancy, pointed out by Lasry: what reaches the cipher wheels is only which of the five magnets each of the nine live index inputs ends on, and because the magnets take the index outputs in pairs, swapping the two members of a pair changes nothing. There are at most 10!/2^5 = 113,400 different effects (Lasry 2019, section 1.2; Library copy). Running all twelve million order-and-setting combinations of the real Pampanito index wheels through the simulator shows that they reach every one of the 113,400; the bound is exact.

Mucklow’s own totals are larger, about 2^107.3 and, once the index wheels’ order was frozen in June 1945, 2^100.4. He counts the index wheels as reversible (a factor of 2^5), although he notes they were always inserted forward in the war, and he does not remove the index redundancy. Neither convention is wrong; they answer different questions. The practical 2^95.6 is the number an attacker who knows the wirings has to search if nothing else is known, and it is the figure the modern papers use.

For comparison, the Army and Air Force Enigma I’s key space is about 2^77 by Stamp and Low’s count, and DES, the American data-encryption standard of 1977, has a 2^56 key.

8.3.1 Day and message

Real traffic narrowed the search in one direction and widened it in another. Under the 1944 procedures (Volume 5), the code-wheel arrangement and the index setting were the day’s key and were shared by every message of the day and classification: 10! × 2^10 × 12,000,000 choices, about 2^55.3. Each message then had its own five-letter alignment, 26^5 = 11,881,376 choices (2^23.5), and in the Navy’s general method the Alphabet Maze’s starting positions were not chosen at all but produced by the stepping, so the enemy could not treat them as five more independent letters. On the other hand, the Navy method sent the Stepping Maze’s five letters in clear as the internal indicator. An enemy who had somehow learned a day’s key would therefore read all of that day’s Navy messages at once. Volume 12 demonstrates the joint Army-Navy case, in which the alignment was itself enciphered, and shows how little stands between a captured key list and the plain text. The procedures, in other words, made the wheels’ secrecy and the key lists’ secrecy the whole of the system’s security. Both held.

8.4 Why the Wartime Methods Found Nothing

Every rotor machine broken in the Second World War was broken by exploiting regularity in how its wheels moved, or a property of the substitution that the movement could not hide. The SIGABA was designed, by people who had broken rotor machines, to offer neither.

Fast-wheel and isomorph methods. Enigma, Typex-like machines and the Hebern machines Friedman broke in the 1920s (Volume 2) moved one wheel every letter and the others rarely. For a stretch of 20 or so letters, the machine could be treated as a fixed substitution with one known moving part, and that part could be solved for. In the SIGABA, between one and four of the five cipher wheels move after every letter, and on average 2.89 do (Volume 4). Every wheel in the Alphabet Maze steps on more than half of all letters: on the demonstration key, between 51 and 68 per cent. There is no slow wheel, and no stretch of text in which the substitution is “mostly” fixed.

Periodicity. A meter of five wheels returns to its start after 26^5 letters, and analysts could look for the period. The SIGABA’s Alphabet Maze has no period of its own; its motion is driven by the Stepping Maze, whose three moving wheels do cycle every 17,576 letters, but the Alphabet Maze’s positions after 17,576 letters depend on everything that happened in between. And the 1944 procedures cut every message at 350 groups (1,750 letters), so no single message ever came near even the control cycle.

Properties of the substitution. The Enigma’s reflector meant that no letter could encipher to itself and that the substitution was a set of swapped pairs; both properties were the basis of the Polish and British attacks. The SIGABA’s current goes straight through, so any letter can encipher to any letter, itself included (3.8 per cent of the time on the demonstration key, the 1 in 26 of a random substitution), and the substitution has no pairs (Volume 3).

Stepping visible in the text. In the Hagelin machines, including the M-209 that the Germans did read, the key is a set of pins and lugs whose effect on each letter is a simple shift, and statistical tests on the cipher text reveal it (M-209 unit, Volume 8). The SIGABA’s stepping control has no direct path into the cipher text at all: it only decides which wheels move, and the effect of a wheel moving is a whole new substitution.

The Army and Navy said as much in their own assessment of the design, quoted by Mucklow: the use of “aperiodic stepping of cipher wheels, instead of regular or modified-regular stepping motion, precluded all known analytical solutions and prevented ‘short-cut’ solutions with captured cipher wheels” (Mucklow 2015, p. 18). That was a claim about the analytical methods of the 1940s, and it was correct.

8.5 Messages in Depth: Savard and Pekelney (1999)

The first published attack, in John Savard and Richard Pekelney’s “The ECM Mark II: Design, History, and Cryptology” (Cryptologia 23:3, 1999, pp. 211-228), takes the classic route around a strong machine: depth. If ten to fifteen messages are enciphered from the same starting position, letter n of every message has been enciphered by the same substitution, and the plain texts can be recovered column by column by Kerckhoffs’s superimposition, as with any polyalphabetic cipher. With the plain texts known, the analyst has the whole substitution of the Alphabet Maze at each position, and can look for positions at which only the leftmost or only the rightmost cipher wheel moved; comparing the substitution before and after such a step reveals that wheel’s wiring, and the inner wheels follow. Savard and Pekelney also suggest ways to recover the Stepping-Maze wirings (as summarized by Lasry 2019, section 2.1; Library copy).

It is a real method and needs little computing, but it depends on an operating blunder that the procedures were written to prevent. CSP 1100(C) required every message alignment under a key to be different, the letters to be chosen “entirely at random”, and messages over 350 groups to be split with a new alignment for each part (Volume 5). Lasry calls ten to fifteen messages in depth “an unlikely scenario, given the US Army and Navy’s strict operational security procedures”.

8.6 Known Plaintext with Known Wheels: Stamp and Chan (2007)

Mark Stamp and Wing On Chan’s “SIGABA: Cryptanalysis of the Full Keyspace” (Cryptologia 31:3, 2007, pp. 201-222), developed from Chan’s master’s project at San José State University, was the first attack on the full key space rather than on a weakened machine. Michael Lee’s 2003 master’s thesis at UC Santa Barbara had attacked simplified versions. Stamp and Chan assume the attacker knows the wirings and a stretch of plain text, and works in two phases:

1. The Alphabet Maze alone. For every choice of five cipher wheels, their order, orientation and starting positions, decipher the first cipher letter and compare it with the known plain letter. For each survivor, try all 30 possible stepping patterns (one to four wheels) and test the second letter, and so on. A wrong setting survives each letter with probability 1/26 per pattern tried, so the survivors thin out slowly: with 100 letters of known plain text, about 2^34.5 of the 2^43.4 possible cipher-wheel settings survive.
2. The rest of the key. Each survivor is tested against every setting of the Stepping and Index Mazes.

The total work is about 2^86.7, about 2^9 times better than trying every key; a variant reaches 2^84.5 with a 0.82 probability of success (figures as summarized by Lasry 2019, section 2.1; Library copy). It was an important result: it showed that the SIGABA’s key space was not as large in practice as it looked. But 2^86.7 operations is beyond any computer that exists. Stamp later published a SIGABA challenge on the MysteryTwister C3 site with part of the key space fixed, and two solvers cracked it.

8.7 Splitting the Machine: Lasry (2019)

The decisive insight came from George Lasry of the CrypTool team, in “A Practical Meet-in-the-Middle Attack on SIGABA” at HistoCrypt 2019 (Lasry 2019; Library copy). He noticed that the two halves of the machine meet at a narrow point. The Alphabet Maze only ever learns one thing from the rest of the machine: which of its five wheels to step after each letter, five bits per letter. And the Stepping and Index Mazes produce that sequence of five-bit patterns on their own, without any reference to the message.

So the attack runs the two halves separately and meets in the middle:

1. Phase 1. Split the ten code wheels into a cipher five and a control five (252 ways). For each split, try every setting of the cipher five against eight letters of known plain text, branching over the 30 stepping patterns after each letter, and record every setting that fits together with the stepping sequence it needed for the first seven letters (35 bits). Store them in a hash table keyed on the stepping sequence.
2. Phase 2. For the same split, try every setting of the control five and every one of the 113,400 index effects, run the Stepping and Index Mazes alone for seven letters, and look the resulting stepping sequence up in the table. A hit is a complete candidate key, which is then checked on the rest of the known text.

The work divides as a meet-in-the-middle always does: instead of multiplying the two halves’ key spaces, the attacker adds them. Lasry’s figures are about 2^47.1 for phase 1 over all splits and 2^52.2 per split, 2^60.2 over all splits, for phase 2, which dominates. The hash table for one split takes about 80 GB of memory. The whole attack is about 2^35 times faster than brute force and, for the first time, feasible with ordinary hardware. Lasry used it to solve Stamp’s MysteryTwister C3 Level III challenge in “a few days on a 10-core Intel Core i7 6950X”, the challenge’s partly fixed key bringing phase 2 down to about 2^41.3, and published six new challenges of increasing difficulty, the last on the full key space. His reference simulator, printed in the paper and “compatible with the source code given in (Pekelney, 1998), and … tested against another simulator (Sullivan, 2002a)”, is the source of the first self-test vector of this unit’s simulator.

His conclusion names the weakness exactly: “The functional separation between the cipher rotor bank, and the control and index rotor banks, is a significant weakness, and it allows for a practical MITM attack. This attack is not feasible on systems like the Siemens and Halske T52d, the Russian Fialka, and the Hagelin CX-52, in which rotors have two functions — encryption/decryption, and controlling the stepping of other rotors.”

In 2023 Lasry published a further attack, “Cracking SIGABA in less than 24 hours on a consumer PC” (Cryptologia 47:1, pp. 1-37, doi:10.1080/01611194.2021.1989522). By the account of its announcement it needs a high-end consumer PC and about 100 letters of known plain text (cryptography mailing list, November 2024); its method is not described here because the paper itself has not been checked for this volume.

8.8 Putting the Numbers on a Clock

A pure-Python SIGABA in this unit’s simulator runs about 137,000 machine cycles a second on a desktop PC (sigaba_attack.py --rate). Trying all 2^95.6 keys at one cycle each would take about 1.4 × 10^16 years at that rate. A machine a million times faster, testing 10^12 keys a second, would still need about 1.9 × 10^9 years: a little under half the age of the Earth.

Stamp and Chan’s 2^86.7 is about 500 times less work than that, and still far out of reach. Lasry’s 2^60.2 is about 1.4 × 10^18 operations: years on a single PC, and well within reach of a cluster, which is why he called it practical. His 2023 attack, by its own title, brings a full SIGABA key within a day of one computer’s time, given known plain text.

All of these numbers rest on the two assumptions that the wartime enemy never had: the wirings, and a long stretch of known plain text exactly aligned with its cipher text. In 1944 an attacker with the wirings, the method and a crib, but only the electromechanical bombes and punched-card machinery of the day, would have needed each of those 2^60 operations, about a billion billion, to be a mechanical test.

8.9 The Margin

The SIGABA was not unbreakable in principle; nothing with a finite key is. What it had was margin in every direction at once. Its key space was some 400,000 times the Enigma’s even after the redundancy is taken out. Its stepping defeated every analytical method of its time. Its weakest point, the split between the cipher and the control of the stepping, could only be exploited with known wirings, a crib and computing power that arrived sixty years later. And the procedures around it — unique random alignments, short messages, the 26-30 check, wheel sets guarded more closely than the machine (Volumes 5 and 6) — closed the doors that the machine itself left open.

Volume 12 makes the last point concrete. Given the wheels, the day’s key list and a twelve-letter crib, its attack demonstration recovers a message alignment from all 11,881,376 possibilities in about nine seconds of pure Python, using a small version of the same meet-in-the-middle idea. Take away the key list and the same problem is the 2^95.6 of this volume.

Sources

• John J. G. Savard and Richard S. Pekelney, “The ECM Mark II: Design, History, and Cryptology”, Cryptologia 23:3 (1999), pp. 211-228.
• Mark Stamp and Wing On Chan, “SIGABA: Cryptanalysis of the Full Keyspace”, Cryptologia 31:3 (2007), pp. 201-222; Wing On Chan, Cryptanalysis of SIGABA, MS project, San José State University, 2007: scholarworks.sjsu.edu/etd_projects/126.
• Mark Stamp and Richard M. Low, Applied Cryptanalysis: Breaking Ciphers in the Real World, Wiley, 2007.
• Michael Lee, Cryptanalysis of the SIGABA, MS thesis, University of California, Santa Barbara, 2003.
• Geoff Sullivan, “The ECM Mark II: some observations on the rotor stepping”, Cryptologia 26:2 (2002), pp. 97-100; and the CSG SIGABA simulator for Windows, cryptocellar.org/simula/sigaba.
• George Lasry, “A Practical Meet-in-the-Middle Attack on SIGABA”, Proceedings of HistoCrypt 2019, pp. 41-49: ep.liu.se/ecp/158/005 (Library copy).
• George Lasry, “Cracking SIGABA in less than 24 hours on a consumer PC”, Cryptologia 47:1 (2023), pp. 1-37: doi:10.1080/01611194.2021.1989522.
• Timothy J. Mucklow, The SIGABA/ECM II Cipher Machine: “A Beautiful Idea” (Library copy), NSA Center for Cryptologic History, 2015, Appendix A.
• US Navy, CSP 1100(C), ECM Operating Instructions, 1944: maritime.org/doc/crypto/ecm.

---

Next — Volume 9: After the War — Declassification, the 2001 Patent, Survivors and Museums. The machine that outlived the war by a decade and a half, the wholesale destruction of wheels and machines when it was retired, a patent application kept secret for fifty-six years, and the handful of SIGABAs that survive, including the one that worked again aboard a submarine in San Francisco Bay.