The Codebreakers — Volume 10 — The Mathematics of Irregular Stepping

10.1 About This Volume

Volumes 6 to 8 followed the Signal Intelligence Service (SIS) through the break of PURPLE. The step that mattered most was structural. Only one of PURPLE’s twenties switches moved at each letter; one of them, the fast switch, came back to the same position every 26 letters; and so two alphabets 26 letters apart were relabellings of each other. That regularity was an invariant in Solomon Kullback’s sense — a characteristic of the system that survived encipherment — and it was enough to reconstruct the machine.

Volume 9 tells how William Friedman and Frank Rowlett, in the years in which they were learning to break regular machines, designed an American machine that would not be regular: SIGABA, in which the stepping of the cipher rotors is controlled by a second bank of rotors through a third. This volume asks the mathematical question. What exactly does regular stepping leak, how much does irregular stepping remove, and what is left? It measures three machines with the same instruments: Enigma, as the representative of the classic rotor odometer; PURPLE’s twenties; and SIGABA.

All the numbers come from 03-outputs/tools/stepping_stats.py. It imports, without copying, the simulators of the Enigma, PURPLE and SIGABA units of this collection, each of which has been checked against published test vectors; the SIGABA simulator reproduces the stepping table printed in the Navy’s operating manual, CSP 1100(C), out to 10,000 steps. One caution applies throughout. No wartime SIGABA rotor wiring has ever been published, so the SIGABA simulator, like every public one, uses the simulated wirings of Richard Pekelney’s emulator. The stepping logic and the index rotors are historical; the cipher-rotor wirings are not. Nothing measured here depends on the cipher-rotor wirings except the isomorph test, and that only through their being unrelated permutations, which the wartime ones were.

The machine itself — its banks, maze wiring and procedure — is described in the SIGABA unit, Volumes 3 to 5. Modern cryptanalysis of it is SIGABA Volume 8. This volume does not repeat them; it compares.

10.2 What Regular Stepping Gives Away

A rotor machine’s security comes from changing the alphabet at every letter. How the alphabet changes is the whole story.

In the Enigma, the rotors step like the wheels of an odometer. The right-hand rotor moves at every letter. Once in 26 letters it carries the middle rotor one step, and once in 26 steps of the middle rotor the middle carries the left — with the well-known complication of the “double step”, in which the middle rotor moves twice in succession when it carries the left. In PURPLE’s twenties the arrangement is the same in principle: a fast, a middle and a slow switch, with exactly one of them stepping at each letter.

The tool counts, over a full period of each machine, how often only the fastest element moves between one letter and the next.

Table 1 — What Regular Stepping Gives Away

Machine	Letters counted	Only the fastest element moved
Enigma I, rotors I-II-III	16,900 (a full period)	96.00%
PURPLE twenties	15,625 (a full period)	95.84%
SIGABA CSP-889: one end cipher rotor alone	40,000 (40 random keys)	0.33%

The Enigma figure is exactly 16,224 of 16,900 letters: 25 of every 26, less the double steps. PURPLE’s is 599 of every 625 letters: in each block of 625 the middle switch steps 25 times and the slow switch once, and every other letter moves the fast switch alone.

Why that matters is the whole of Volumes 7 and 8. When only the fast element moves, the rest of the machine is a fixed scrambler for that stretch of text, and the analyst faces one moving part and one constant. In PURPLE, the constant was revealed by comparing alphabets 26 apart. In the Enigma, the same structure — a fixed core of middle rotor, left rotor and reflector, with one moving rotor in front — underlay every British and Polish method, from the rodding of a single rotor to the bombe’s usual working assumption that the middle rotor did not turn over within a crib. Regular stepping makes the machine spend almost all its time in its simplest state.

10.3 The Answer: Encipher the Stepping

Rowlett’s idea, as Volume 9 describes, was to make the stepping of the cipher rotors depend on a second cipher process. In SIGABA, as the US Navy’s operating manual CSP 1100(C) of May 1944 specifies, the five control rotors (the Navy’s “stepping maze”) form an odometer of their own: the centre rotor steps at every letter, the fourth rotor when the centre passes O, the second when both have passed O, and the first and fifth never move. At each letter four contacts on one side of the control bank are energised. The currents emerge on four of 26 contacts at the other side, which are wired in nine groups to nine of the ten inputs of the index bank — five ten-contact rotors set by hand and never stepped. The index bank’s ten outputs are wired in pairs to the stepping magnets of the five cipher rotors. The result is that at every letter some cipher rotors step and others do not, according to a pattern that is itself the output of a cipher (the wiring is set out in the SIGABA simulator’s documentation and in SIGABA Volume 4).

Three properties follow from that design, and the tool measures each.

At least one cipher rotor and at most four step at every letter. Four currents entering the index bank can light at most four of the five pairs of magnets; the grouping guarantees at least one. Over 40,000 letters the simulator never steps none and never steps five. The distribution is 0.9 per cent one rotor, 25.2 per cent two, 56.7 per cent three and 17.2 per cent four. All 30 possible patterns — every subset of one to four of the five rotors — occur, the commonest at about 6.5 per cent each. (The post-war CSP-2900 modification, which energises more contacts, can step all five; the simulator shows it doing so on 8 per cent of letters.)

Simple steps are rare. The step most useful to an attacker is one in which a single end rotor moves alone, so that the alphabet changes by one rotor’s motion at the edge of the bank — the SIGABA equivalent of Enigma’s fast rotor moving alone. It happens on 0.33 per cent of letters: about once in three hundred.

The stepping is unpredictable from the stepping. The information-theoretic entropy of the stepping pattern measures how much an observer must be told, on average, to know which elements move at the next letter:

Table 2 — The stepping is unpredictable from the stepping. The information-theoretic entropy of the stepping pattern measures how much an observer must be told, on average, to know which elements move at the next letter

Machine	Entropy of the pattern	Given the previous pattern
Enigma I	0.25 bits per letter	0.24
PURPLE twenties	0.26	0.25
SIGABA CSP-889	4.39	4.36

A quarter of a bit per letter means that Enigma’s and PURPLE’s next steps can be guessed almost always: “the fast one”. SIGABA’s 4.39 bits is close to the 4.91 bits that a pattern chosen uniformly at random from 30 possibilities would need, and knowing the previous pattern hardly helps.

10.4 Twenty Letters Side by Side

The difference is easiest to see letter by letter. The tool sets each machine just before a carry, so that something other than the fast element moves early on, and records what moves at each of the first twenty letters. For the Enigma (rotors I-II-III, starting at A D T), L, M and R are the left, middle and right rotors. For PURPLE (sixes starting at 22, switch #1 fast and #2 middle), the entry is the twenties switch that moved. For SIGABA (one random key), it is the cipher rotors, numbered 1 to 5, that stepped.

Table 3 — Twenty Letters Side by Side

Letter	Enigma	PURPLE	SIGABA		Letter	Enigma	PURPLE	SIGABA
1	R	#1	1 4 5		11	R	#1	1 2 4
2	R	#1	1 4		12	R	#1	1 2 5
3	M R	#1	1 2 3		13	R	#1	2 4 5
4	L M R	#2	1 2 3		14	R	#1	2 5
5	R	#1	1 5		15	R	#1	1 2 3 5
6	R	#1	1 2 3 4		16	R	#1	1 2 4 5
7	R	#1	2 3 4 5		17	R	#1	1 2 5
8	R	#1	2 4		18	R	#1	2 4 5
9	R	#1	1 2 4		19	R	#1	2 3 5
10	R	#1	1 2 3 5		20	R	#1	1 2 3

The Enigma column shows the regular carry and, at letter 4, the double step, in which the middle rotor moves for a second letter running and carries the left. Apart from those two letters, only the right rotor moves. PURPLE’s middle switch moves once, at letter 4, when the sixes switch stands at 25; for the other nineteen letters the fast switch moves alone. In the SIGABA column no two consecutive letters are alike in any useful way, no rotor moves alone, and every rotor sits still for some letters and moves for others. An analyst who knew the Enigma’s or PURPLE’s position at letter 1 could write down their columns to the end of the message. The SIGABA column cannot be written down without the key.

10.5 Periods

A period is the number of letters before a machine returns to the same state and starts repeating. It is often quoted as a measure of strength. It is a poor one.

Table 4 — Periods

Machine	Period of the stepping	Period of the whole alphabet sequence
Enigma I	16,900	16,900
PURPLE	15,625	15,625
SIGABA (three random keys)	17,576	456,976

SIGABA’s control bank is itself an odometer of three moving rotors, so its stepping pattern repeats every 26³ = 17,576 letters; the tool confirms the repeat for every key it tests. Over one such period each cipher rotor advances by some number of steps, and the cipher bank returns to its starting position only after enough periods for every rotor to come round; for the three keys tested that is 26 periods, 456,976 letters.

None of these periods mattered in practice. PURPLE’s 15,625 letters already exceeded any message the Japanese sent, and PURPLE was broken in eighteen months. What mattered was the structure within the period: how much of the time the machine spent in a simple state, and whether an analyst could tell when it changed. A long period built from a regular odometer is a long sequence of short, related stretches. SIGABA’s advantage was not that its period was long but that its sequence had no short stretches.

10.6 The Isomorph Test Fails

The cleanest demonstration is to run the instrument that broke PURPLE against SIGABA. The test from Volume 7 takes six messages of 1,000 letters in depth — the same key and starting position, which for SIGABA is the most favourable situation an attacker could hope for, and one that strict procedure was designed to prevent — and asks, for every interval from 1 to 60, whether the alphabets at positions i and i + d are related by one fixed substitution that holds from one position to the next.

PURPLE gives agreement 0.79 at interval 26 and 0.75 at 52, against a background near 0.05. SIGABA’s highest value anywhere in the range is 0.15, at an interval of 35 that has no significance, and its mean is 0.065. There is no interval at which the alphabets are related, because there is no schedule on which any rotor comes back to the same place while the others stand still. The invariant that Grotjan found does not exist.

10.7 Key Space — and Why It Is the Wrong Measure

The arithmetic of SIGABA’s key space has been worked out carefully by modern analysts. Following George Lasry’s 2019 analysis (Lasry, “A Practical Meet-in-the-Middle Attack on SIGABA”, §1.2; Library copy), which the tool reproduces:

Table 5 — The arithmetic of SIGABA's key space has been worked out carefully by modern analysts. Following George Lasry's 2019 analysis ([Lasry, "A Practical Meet-in-the-Middle Attack on SIGABA"](https://ep.liu.se/ecp/158/005/ecp19158005.pdf), §1.2; [Library copy](/library/george-lasry-a-practical-meet-in-the-middle-attack-on-sigaba-proceedings-of-histocrypt-2019-linkoping-2019)), which the tool reproduces

Element	Count	Power of two
Choice and order of ten rotors from ten, each either way round, at any of 26 positions: 10! × 2¹⁰ × 26¹⁰	5.2 × 10²³	2^78.8
Index rotors: order and setting, 5! × 10⁵	12,000,000	2^23.5
Index bank, distinct effects only: 10!/2⁵	113,400	2^16.8
Nominal total		2^102.3
Practical total (distinct effects)		2^95.6

For comparison, Stamp and Low put the Enigma I’s key space at about 2⁷⁷, and the Data Encryption Standard of 1977 has a 56-bit key.

The figure includes one line that should give pause. Freeman, Sullivan and Weierud count PURPLE’s key space, for an attacker who knows its wiring, as 25 sixes positions, 25³ twenties positions, six motions and 26! plugboard orders — about 9.45 × 10³², or 2^109.5 (FSW 2003, p. 31). By that measure PURPLE was stronger than SIGABA. It was read daily. The 26! plugboard orders were never searched; they were recovered with cribs, a letter at a time, because the structure of the machine let partial knowledge be checked and extended. Key space measures the cost of an attack that tries every key. Irregular stepping made SIGABA strong by making that the only kind of attack available.

10.8 What Modern Attacks Achieve

Three published attacks show how much effort SIGABA demands even of a modern attacker, and what each must assume.

Depth. John Savard and Richard Pekelney described an attack that needs ten to fifteen messages in depth. Their method reconstructs the alphabets at each position, identifies the positions at which only the leftmost or rightmost cipher rotor has moved, and compares the alphabets on either side of those positions to recover the rotors’ wiring (summarised by Lasry 2019, §2.1). It is the isomorph idea again, and it depends on exactly the event that the tool finds on one letter in three hundred. It also depends on depth, which SIGABA procedure — a fresh five-letter alignment for every message — was designed to prevent. Lasry’s own footnote calls the scenario “unlikely, given the US Army and Navy’s strict operational security procedures”.

Stamp and Chan, 2007. Mark Stamp and Wing On Chan’s known-plaintext attack (Cryptologia 31, 2007) assumes the rotor wirings are known and searches the rest in two phases. First, every setting of the five cipher rotors is tested against the known plaintext, allowing at each letter any of the 30 possible stepping patterns; with 100 letters of known plaintext, about 2^34.5 of the 2^43.4 cipher-rotor settings survive. Second, each survivor is tested against every setting of the control and index banks. The total work is about 2^86.7, with a variant at 2^84.5 that succeeds with probability 0.82 (as summarised by Lasry 2019, §2.1). That is about 480 times (2^8.9) less work than exhaustive search over the practical key space, and still far beyond any computer.

Lasry, 2019. George Lasry’s meet-in-the-middle attack also assumes known wirings and known plaintext, at least eight letters. It splits the ten large rotors between the cipher and control banks, builds a table of cipher-rotor stepping sequences that reproduce the plaintext, and then searches control and index settings for a match. Its work factor is 2^60.2 with under 100 GB of memory — “feasible with modern technology”, in his words — and he used a version of it, on a challenge whose key space was reduced by the way it was set, to solve the MysteryTwister C3 SIGABA Level III challenge in “a few days on a 10-core Intel Core i7” (Lasry 2019, §2.6). He adds: “Still, the attack on SIGABA proposed here would not have been feasible given WWII technology.”

The SIGABA unit’s Volume 12 works a laptop-sized version of the known-plaintext idea, in a situation where a captured key list has already given away everything but the message alignment.

Every one of these attacks begins by assuming the rotor wirings are known. No wartime enemy had them; the machines were guarded under rules described in SIGABA Volume 6, and Lasry notes that the German codebreaking services are believed to have made no inroads at all (citing Mucklow 2015, Budiansky 2000 and Kelley 2001).

10.9 What Was Still Regular

SIGABA was not free of invariants; it moved them out of reach. Three remain visible in the measurements above.

The control bank is an odometer. Its stepping pattern repeats exactly every 17,576 letters, and within that period its own rotors spend most of their time with only the centre one moving. An attacker who could observe the control bank directly would face a regular machine. The design’s strength is that the control bank is never observed: its output reaches the cipher bank only through the index bank, as a pattern of which magnets fire.

The index bank is smaller than it looks. Its 12,000,000 settings collapse to 113,400 distinct effects, because it is a fixed permutation of ten wires whose outputs are then paired. Every published attack exploits this.

And the cipher bank, between steps, is still a fixed series of five rotors. The 0.33 per cent of letters at which a single end rotor moves alone are the remnant of the regular machine, and an attack with enough depth can find them. Kullback’s footnote in Volume 6 drew the line exactly: “A cryptographic system which had no invariant characteristics would be secure against unauthorized decipherment.” SIGABA did not reach that ideal. It made its invariants rare, hid them behind a second cipher, and relied on procedure to deny the depth needed to find them — and that was enough.

10.10 Why It Is Still Studied

Irregular stepping did not end with rotor machines. Its electronic descendant is irregular clocking in stream ciphers built from shift registers, where one register decides whether another advances. The alternating step generator and the shrinking generator of the 1980s and 1990s are examples, and the A5/1 cipher of GSM mobile telephones clocks its three registers by a majority rule — each register steps only if its clocking bit agrees with the majority — for the same reason SIGABA stepped its rotors irregularly: to destroy the regular structure that makes linear analysis easy. A5/1 was broken anyway, by attacks that exploit the regularities its clocking left behind, which is the lesson of SIGABA’s 0.33 per cent in another form.

The deeper lesson is the method of this volume: measure a design with the instruments that break designs. The isomorph test, the count of simple steps, the entropy of the stepping — each is a question an attacker would ask, turned into a number before the machine is built. The SIS had learned to ask those questions against PURPLE. In SIGABA they asked them of themselves first.

---

Next — Volume 11: Mechanising Cryptanalysis — Sorters, Tabulators and the Road to Computers. Counting by hand could not keep up with the traffic. How IBM punched-card machines came into the SIS and OP-20-G, what a sorting run actually computed, why Vannevar Bush’s Comparator failed, and how the special-purpose machines of the war led to ATLAS, ABNER and HARVEST.