The Codebreakers — Volume 8 — Reconstructing a Machine Never Seen

8.1 About This Volume

Volumes 6 and 7 described the tools: coincidence statistics, which found PURPLE’s six-letter group and its 25-letter cycle, and cribs, stereotypes, isomorphs and homologs, which turned guessed plaintext into evidence about the machine’s internal structure. This volume follows the chain of inference to its end. It asks a question that sounds impossible: how do you work out the wiring of a machine you have never seen, from nothing but its output and some guesses about its input? And then: how do you build one?

The answer is a sequence of steps, each of which depends on the one before. The volume takes them in order — the sixes, the stepping law, the twenties, the build — and for each gives the historical record and a computed demonstration. The demonstrations are run by 03-outputs/tools/reconstruct.py, which uses the PURPLE unit’s simulator to generate traffic and to grade the answer, but never to supply the answer. The sixes are recovered from the real Part 1 intercept of 6 December 1941 and graded against the wiring published by Freeman, Sullivan and Weierud. The twenties are recovered from modelled messages in depth, sized like the indicator-59173 set of September 1940. The self-test checks every claim made here.

The machine’s anatomy is in PURPLE Volume 4 and the narrative of the break in PURPLE Volume 5. Neither is repeated. The figure below is the map for this volume.

8.2 What “Reconstructing” Means

The US Navy’s PURPLE manual of January 1941, R.I.P. 77, separates the problem into three parts. To read a PURPLE message one needs “1) the basic wiring of the rotary switches … 2) the settings of those elements governed by the keys, and; 3) the plugboard sequence” (R.I.P. 77, p. 2-4; CryptoCellar; Library copy). The wiring was fixed for the life of the machine. The settings — starting positions and the order of motion of the three twenties switches — came from an indicator drawn from a list of 120. The plugboard sequence, the daily alphabet, changed every day. The manual notes that the wiring was “determined in the solution of the first few messages”, after which the daily problem “resolves itself into the matter of solving a new sequence for each day’s traffic”.

That ordering conceals the difficulty. Recovering the wiring took eighteen months. Once it was known, the other two parts were routine.

There is a second subtlety, which runs through everything below. An analyst working from outside the machine can never recover its wiring exactly. If every wire between two switches were relabelled — terminal 3 called 7, 7 called 12 and so on — and the next switch rewired to match, the machine would encipher identically. The outside world cannot see the labels. What can be recovered is wiring up to relabelling: an equivalent machine. That turned out to be enough, and it explains why the SIS analog worked perfectly even though, as PURPLE Volume 4 describes, it was built quite differently inside.

8.3 Step One: the Sixes, Cell by Cell

The sixes switch has 25 positions. At each position it applies a fixed permutation of six contacts, so its complete wiring is a table of 25 rows and 6 columns, 150 cells in all. Friedman’s report describes the analysts building “a deciphering chart”, correcting it day by day, until by 10 April 1939 it was complete: “a series of 25 heterogeneous and differently mixed alphabets … a carefully selected set of 25 of the possible 720 permutations” (Friedman 1940, pp. 1–2).

The raw material was known plaintext. Freeman, Sullivan and Weierud point to the most important source: Japanese messages had always begun with a message number, the SIS had kept careful records of the numbers from RED traffic, and the same numbering continued when PURPLE came in, so that “many ciphertext–plaintext pairs” were available from the start (FSW, p. 14, citing Rowlett, The Story of Magic, p. 146; Library copy). Each sixes letter of known plaintext, at a known position in the 25-letter cycle, fills one cell of the table: at position k, cipher contact a deciphers to plain contact b.

The tool does exactly this with the one real message available, the intercept of Part 1 of the Fourteen-Part Message and its plaintext. It is given the day’s alphabet and the sixes starting position from the indicator, and nothing about the wiring. It walks through the message, records every sixes pair, and fills the table, taking the majority where a cell is observed more than once and completing any row in which five of the six cells are known (the sixth is then forced, because each row is a permutation).

Table 1 — Step One: the Sixes, Cell by Cell

Letters of the message read	Sixes pairs seen	Cells filled (of 150)	Complete rows (of 25)
100	29	25	0
200	60	45	0
400	125	75	0
600	180	85	2
800	234	95	3
1,000	292	100	4
1,285	374	112	8

The real intercept, garbles and all, yields 112 of the 150 cells with no conflicting observations, and every one of the 112 agrees with Figure 6 of Freeman, Sullivan and Weierud. A single long message gets three-quarters of the way. The last quarter is slow — the curve flattens — because the missing cells need particular plain letters at particular positions, and a message supplies them only by chance. With the day’s traffic pooled and a few weeks of messages, the table fills. That matches the historical timescale: PURPLE came into use on 20 February 1939, and the chart was complete on 10 April.

The NSA’s later course on PURPLE printed a worksheet for this step. Its rows are the 25 positions, its columns the six cipher contacts, and the entries are the plain contacts. The first six rows read 2 1 3 5 4 6; 6 3 5 2 1 4; 1 5 4 6 2 3; 4 3 2 1 6 5; 3 6 1 4 5 2; 2 1 6 5 3 4 — the same as the first six rows of the published wiring table, and the same as every cell of those rows that the tool recovered.

The worksheet also shows something the tool takes as given: the day’s order of the six letters. The arrows on its right-hand side chain letter equivalences found at different positions — Z with T, T with X, Z with J, J with X — exactly the chaining technique of Military Cryptanalysis Part III described in Volume 7. In practice the wiring and the daily order were recovered together, each correction to one tightening the other.

Once the chart existed, Leo Rosen proposed doing the deciphering with a six-level, 25-point telephone selector switch, and within about two weeks the “six-buster” was running (PURPLE Volume 5). It was the first physical piece of the reconstruction, and it was built to the wiring recovered on paper.

8.4 Step Two: the Stepping Law

The twenties could not be attacked as the sixes were, because their alphabets did not repeat in a short cycle. The first thing to establish was how they moved.

The sixes, once read, told the analysts exactly when the sixes switch passed from position 25 to position 1 — the point at which RED’s machine had shown its own peculiarities. From the solved messages the analysts learned that the twenties’ behaviour changed there too. Friedman’s report of October 1940 summarises the law as it was understood a week after the break: three banks of switches, a “3-2-1” motion — fast, medium and slow — and six possible orders in which the three banks could take those roles, each order used by 20 of the 120 indicators (Friedman 1940, p. 7). Freeman, Sullivan and Weierud give the precise rule from the reconstructed machine: after every letter the sixes switch steps and exactly one twenties switch steps; normally the fast one, but the middle one when the sixes switch stands at 25, and the slow one when the sixes is at 24 and the middle at 25 (FSW, p. 15).

The interval-26 isomorph of Volume 7 is the fingerprint of this rule. A suppression of repeated encipherments at interval 26, and chains of cipher equivalents at interval 26, are what one fast switch coming back to the same position while one middle switch moves a single step must produce. Volume 7’s tool finds the peak at 26 for every order of motion it is given; the relation lies on the cipher side or the plain side according to which switch is the middle one. That is enough to label every letter of a message by two numbers: where the fast switch is (one of 25 positions, counted relative to the start), and which stretch the letter belongs to — the run of letters between two moves of any switch other than the fast one. Letters in the same stretch share the same middle and slow positions.

In the tool this labelling is computed from the stepping rule alone, with no wiring; it is the analyst’s knowledge after the step described here. The self-test confirms the property on which everything else rests: 26 letters apart, the fast-switch position is the same and the stretch number has advanced by one.

8.5 Step Three: From Isomorphs to Wires

Now the twenties wiring. In any stretch the twenties alphabet at each letter is the fixed middle-and-slow combination applied after the fast switch at its current position (or before it, depending on the order of motion; the logic is the same either way). Write the fast switch’s output terminals as wires. Then each observation of known plaintext says: at fast position k, the plain letter p leaves on some wire w, and in stretch s the wire w arrives at cipher letter c.

None of the wires is labelled, so the analyst cannot say which wire w is. But two observations can be shown to share a wire. If, in the same stretch, two different observations — perhaps at different fast positions, from different messages — arrive at the same cipher letter, then they left the fast switch on the same wire, because the rest of the machine is fixed within the stretch and a permutation cannot send two wires to one letter. Collecting all such identities sorts every observation into wire classes. Each class is one terminal of the fast switch. Once the classes are known, the fast switch’s wiring is a table — at position k, plain letter p goes to class w — and each stretch’s combined middle-and-slow wiring is another — class w goes to cipher letter c.

This is the computational form of what Volume 7 called chaining, and it uses only the facts the analysts had established by the end of September 1940: the sixes, the stepping law, and depth. The tool runs it on six modelled messages of 1,000 letters in one indicator, two with plaintext complete and four with fragments covering about a third of their length — the shape of the 59173 set, in which “two … had been reconstructed completely or nearly so; in the other four, only fragments” (Friedman 1940, para. 11). The key used has switch #1 fast and #2 middle.

Table 2 — Step Three: From Isomorphs to Wires

Measure	Result
Twenties observations	2,032
Stretches covered	43
Wire classes found	27 (the real switch has 20)
Classes that mix two real wires	0
Fast-switch cells filled	390 of 500
Stretch wirings filled	734 of 860 cells
A new message in the same indicator, read with only the recovered tables	489 of 581 twenties letters correct, 92 unreadable, 0 wrong

Twenty-seven classes for twenty real wires means that seven of the wires have each been seen as two separate classes that no observation has yet joined. That is incompleteness, not error: the grading checks that no class ever contains two different real wires, and none does. The recovered tables are, as far as they go, the real fast switch up to relabelling. Used as a machine, they decipher 84 per cent of the twenties letters of a fresh message correctly and leave the rest blank. They never produce a wrong letter.

The amount of known plaintext matters, as it did in 1940:

Table 3 — The amount of known plaintext matters, as it did in 1940

Messages in depth with plaintext	Fast-switch cells (of 500)	New message read
1 complete + 5 at 35%	377	468 of 581
2 complete + 4 with none	350	377 of 581
2 complete + 4 at 35%	390	489 of 581
2 complete + 4 at 60%	411	545 of 581

8.6 Step Four: Bootstrapping

The figures above describe a single moment. The attack did not stop there, because a message read 84 per cent of the way, with its sixes already known, is a message whose blanks a linguist can fill from context. Every message read becomes known plaintext for the next. The tool models this by adding, one at a time, further messages in the same indicator as if read and completed:

Table 4 — The figures above describe a single moment. The attack did not stop there, because a message read 84 per cent of the way, with its sixes already known, is a message whose blanks a linguist can fill from context. Every message read becomes known plaintext for the next. The tool models this by adding, one at a time, further messages in the same indicator as if read and completed

Messages in depth	Fast-switch cells	Wire classes	Next new message read	Wrong letters
6	390	27	507 of 592	0
7	405	21	546 of 592	0
8	410	21	556 of 592	0
9	416	21	566 of 592	0
10	424	20	572 of 592	0

By the tenth message the wire classes have merged to exactly twenty — every terminal of the real fast switch identified — and 97 per cent of the next message is read. The cells still missing belong to plain letters that the traffic never happens to place at certain positions; they fill as more text arrives.

The historical pace matches the shape. The first two messages in indicator 59173 were solved and their translations handed in on 27 September 1940, a week after Grotjan’s discovery. Over the following weeks the same principles were applied to the other indicators, each requiring its own starting positions and order of motion; by 14 October 1940 more than a third of the 120 had been solved (Friedman 1940), and by 1 April 1941, according to R.I.P. 77, all 120 original starting points and about half of the alphabets in the Japanese key book had been recovered, and “about 99 percent of the intercepted traffic” could be read (R.I.P. 77, p. 2-1A).

The middle and slow switches were recovered by the same method one level up: once the fast switch is known, the stretch wirings are known, and successive stretches differ by exactly one step of the middle switch, so they stand in the same relation to the middle switch as successive letters do to the fast one. The tool does not repeat the exercise; the logic is identical.

8.7 Step Five: Building It

The SIS’s analog was built from the reconstruction, not from a description of the Japanese machine. Friedman’s report of October 1940 gives its anatomy: 13 rotary, six-level, 25-point switches “of the type employed in automatic telephony” — one for the sixes with 150 cross-connections, and three banks of four for the twenties, each bank with 500 cross-connections (Friedman 1940, p. 7). Those numbers are the size of the reconstruction: 25 positions × 6 contacts for the sixes, and 25 positions × 20 contacts for each twenties stage. A hand-operated machine was working by 14 October 1940. Rosen’s two automatic analogs followed, at a cost Rowlett recorded to the cent, $684.65 for each (PURPLE Volume 5).

The choice of the telephone selector switch was the one inspired guess in the whole reconstruction, and it was Rosen’s. The analysts had assumed for eighteen months that the machine was a rotor machine like RED, and the NSA’s later course notes list that assumption as one reason the solution took so long (NSA, “Red and Purple”, p. 71). Freeman, Sullivan and Weierud observe that PURPLE and its naval relatives, CORAL and JADE, “were the first, and perhaps the only, known cryptographs to use stepping switches to permute the plaintext”, and that the defining property of a stepping switch as a cipher element is that “the alphabets which the switch produces are totally unrelated” (FSW, pp. 15–16). A rotor’s 26 positions are shifts of one wiring; a stepping switch’s 25 positions are 25 independent wirings. That is exactly what the recovered tables showed, and it is why a telephone switch, not a rotor, was the right thing to build.

The analog’s internal wiring did not match the Japanese machine’s, and did not need to. PURPLE Volume 4 describes the difference found after the war: the Japanese built each twenties stage from three seven-level switches geared together, where Rosen used four six-level switches. Within each stage the labelling of the internal wires was arbitrary. What had to match was the relation between what goes in and what comes out at every position, and that is precisely what reconstruction up to relabelling delivers. Rowlett’s verdict on the comparison — “of the several hundred connections we had recovered, only two were incorrect, and their effect on decipherment was negligible” — is a statement about that relation.

The Navy named its own version of the reconstructed machine R.I.P. 72 — “built for deciphering only”, as R.I.P. 77 notes (p. 1A-1). The analog was a cryptanalytic instrument: a machine whose only purpose was to embody, in copper, a theory of the enemy’s machine, and to be tested against traffic every day.

8.8 The Same Problem, Sixty Years Later

In 2003 Freeman, Sullivan and Weierud solved a PURPLE message of 27 July 1942 from ciphertext alone, knowing the wiring but not the key. Their method shows how differently the same problem looks to a computer. They did not identify the sixes by frequency, because in that message they could not (“there is no obvious group of six letters as suitable candidates”). Instead they hill-climbed: starting from a random alphabet, they swapped pairs of letters and kept any swap that raised a score built from the bigram frequencies of five known Japanese plaintexts, restarting a hundred times at each of the 25 sixes positions. That took 812,500 trial decipherments and found the sixes alphabet XPILRQ at position 13. The twenties, scored on trigrams and searched at every one of 25³ × 6 settings, needed about 8.9 × 10⁸ trial decipherments and several hours on four personal computers, and gave the key: motion 321, sixes at 13, twenties at 25, 23 and 12 (FSW, pp. 30–36).

The 1940 analysts had no computer and no wiring, and they solved the harder problem — the wiring itself — in eighteen months, with paper, pencils and a few IBM machines. The computer solution needs the wiring that they recovered.

8.9 What It Teaches

The reconstruction of PURPLE is the classic case of what cryptographers now call recovering an unknown algorithm from its input and output. It established, decades before the principle was widely written down, that the security of a cipher machine cannot rest on the secrecy of its design: a determined analyst with enough known plaintext and enough time will rebuild it, and the rebuilt version need not resemble the original inside to be perfect outside. Auguste Kerckhoffs had stated the principle in 1883, as a requirement for military ciphers; the SIS demonstrated it against a real one.

It also shows what made the reconstruction possible, step by step. The sixes fell because they had a short period. The stepping law was readable because the sixes, once read, marked the moments when the twenties’ behaviour changed. The twenties fell because only one of their switches moved at a time, so that alphabets 26 letters apart were relabellings of each other, and because a short list of indicators gave depth. Every one of those conditions was a design choice. The next two volumes follow the same people as they made the opposite choices in SIGABA.

---

Next — Volume 9: Inventing SIGABA — The Lessons Turned Inward. While the PURPLE analogs were being built, Friedman and Rowlett were designing the American answer: a machine whose stepping was itself enciphered, so that no switch came back to the same place on any schedule an enemy could learn. Rowlett’s stepping maze, the Army–Navy bargain, and the patents kept secret for half a century.