The Codebreakers — Volume 7 — Cribs, Stereotypes, Isomorphs and Homologs

7.1 About This Volume

Volume 6 ended where statistics end. Coincidence counts exposed PURPLE’s six-letter group and its 25-letter cycle within weeks of the machine’s introduction in 1939, but the other twenty letters — the twenties — passed every test as random text. For the next eighteen months the attack on them rested on four older ideas, all of which the Signal Intelligence Service (SIS) taught as named techniques: the crib, a guessed piece of plaintext; the stereotype, a formula that the enemy’s own procedure guaranteed would be there to guess; the isomorph, a pattern of repetitions that survives encipherment; and the homolog, a letter treated identically by the machine in two messages that look nothing alike. This volume takes each in turn: where the idea came from in the SIS’s training literature, how it was applied to PURPLE, and a computed demonstration of what it could and could not do.

Two of the demonstrations use real traffic — the intercepted ciphertext of Part 1 of the Fourteen-Part Message of 6 December 1941, and the stereotyped message openings that the Navy’s PURPLE manual printed in January 1941. The rest use the PURPLE simulator of the PURPLE unit to generate modelled traffic, because the six messages in indicator 59173 on which the break of September 1940 actually turned have not been published. Where a demonstration is a modern reconstruction rather than a record of what the analysts did, the text says so. All the numbers come from 03-outputs/tools/cribs_isomorphs.py, which checks its own results in a ten-part self-test. The narrative of the break itself is in PURPLE Volume 5; this volume goes inside the method.

7.2 Cribs and the Probable Word

A crib is plaintext the analyst expects to find. The idea is as old as cryptanalysis, and the SIS taught it from its first textbook. Friedman’s Military Cryptanalysis, Part I (1938) calls it the “probable-word method” and shows the essential trick that makes it work without knowing where the word is: some words have a shape. DIVISION has the pattern ABCBDBEF — its second, fourth and sixth letters are the same — and BATTALION is ABCCBDEFG. Friedman called such words idiomorphs, from the Greek for “own form”, and showed how a “strikingly idiomorphic” word could be slid along a monoalphabetic ciphertext, one place at a time, until its pattern of repeats lined up with a pattern in the cipher (Friedman 1938, Part I; Library copy).

The SIS’s own history has a perfect example, recorded by Frank Rowlett. Some time in the first half of the 1930s, before RED was broken, Solomon Kullback, working on Japanese diplomatic traffic in the vault with Rowlett and John Hurt, suddenly beat on his table: “That’s it! That’s what they have done! It’s an English monoalphabet!” He had underlined three cipher groups in red. “Look at the letter patterns for those three words. Can they be anything but a monoalphabetic substitution of the English words ‘The Japanese Government’?” Hurt, the section’s Japanese linguist, guessed what would follow — a request “that the Government of the United States” do something — and the message fell. Friedman, who at first could not believe that any competent government would use such a system, left the vault saying, “Well done, Mr. Kullback” (Hannah, “Frank B. Rowlett: A Personal Profile”, pp. 11–13; Library copy).

A crib against a machine cipher is harder, because a pattern of repeated letters does not survive polyalphabetic encipherment. Something else has to locate it. Against RED, the SIS’s way in was the Japanese word oyobi, “and”, which recurred often enough to give a vowel–consonant pattern in the six-letter vowel group (the RED break is described in PURPLE Volume 3). Against PURPLE, the locator was the sixes.

7.3 Placing a Crib in the Real Part 1 Intercept

From April 1939 the SIS could decipher the sixes of any PURPLE message whose day’s alphabet it knew. That turned every message into a skeleton: about a quarter of the letters readable, the rest blank. Friedman’s report of October 1940 gives the method in one line — the skeletons “offered themselves for completion by the ingenuity and the imagination of the cryptanalyst” — and one example, in which the sixes E, Q, A, D, R and H revealed the bones of “the Japanese government requests that” (PURPLE Volume 5 reproduces it).

The tool repeats the exercise on the real intercept of Part 1. On 6 December 1941 the sixes were N, O, K, T, Y and U. The first 120 letters of the ciphertext, with what the sixes reveal beneath them, look like this — a question mark is a twenties letter, which could not be read:

?O?T?T?K?????N??U???NO?O???O??U?????Y????K?????OO??TN?Y???????O??N?U???O?O?OO?O????K????Y??????Y????????T???O??-N??NTO??
ZTXODNWKCCMAVNZXYWEETUQTCIMNVEUVIWBLUAXRRTLVARGNTPCNOIUPJLCIVRTPJKAUHVMUDTHKTXYZELQTVWGBUHFAWSHULBFBHEXMYHFLOWD-KWHKKNXE

A crib can now be tested in two stages, and neither requires reading a single twenties letter. First, its pattern: a crib letter that is one of the day’s six must stand over a cipher letter that is also one of the six, and a crib letter from the twenties must stand over a twenties cipher letter, because the plugboard and switches never mix the two groups. That alone is a strong filter. Second, its content: where the crib has a sixes letter, the deciphered sixes must show that very letter.

Table 1 — Placing a Crib in the Real Part 1 Intercept

Crib	Letters	Sixes in it	Places to try	Fit the 6/20 pattern	Also fit the sixes read	True place
MEMORANDUM	10	3	1,276	4	1	59
NEGOTIATIONS	12	6	1,274	3	1	361
PEACEOFTHEPACIFIC	17	2	1,269	2	2	273
THEGOVERNMENTOFTHEUNITEDSTATES	30	12	1,256	2	2	186 and 413

Ten letters of “MEMORANDUM”, three of them sixes, are enough to put the word in exactly one place out of 1,276. The 30-letter formula “the government of the United States” survives at two places, and both are real: the phrase occurs twice in Part 1, once with a garbled letter in the intercept. “Peace of the Pacific” survives at its true place and at one false one, position 1,255, in the last few dozen letters of the intercept, which are so badly garbled that the test has almost nothing to test against. The crib works because the sixes impose a pattern — sixes here, twenties there — on every stretch of text, a pattern the plaintext must share. It is Friedman’s idiomorph, transplanted from repeated letters to letter classes.

What the crib gives, once placed, is a set of twenties plaintext–ciphertext pairs at known positions. That is the raw material of every later step.

7.4 Stereotypes: the Enemy’s Procedure as a Crib Supplier

A crib is only as good as the guess. What made PURPLE traffic so rich in good guesses was Japanese procedure. The Foreign Ministry’s telegrams were formal documents with fixed beginnings, and the analysts learned the formulae as thoroughly as the Japanese clerks did.

The fullest primary account is in the Navy’s PURPLE manual, R.I.P. 77, prepared by OP-20-G and dated 15 January 1941. Its chapter on recovering a day’s alphabet is blunt about the method:

The method employed in this procedure is definitely a “Probable Word Method” and is based on the fact that the messages transmitted in this system, with very rare exception, begin with the message number. As a matter of fact, the appearance of a message without the usual stereotyped beginning is so unusual that for the purposes of solution it can be ignored.

— US Navy, R.I.P. 77, Instructions for M-5 (Orange Diplomatic “B” Machine) (PURPLE), 15 January 1941, p. 2-9 (CryptoCellar; Library copy)

The next page, reproduced at the head of this volume, prints the beginnings of six messages from Berlin to Tokyo. Five open FYC, and the letters after FYC are the message number. Embassies numbered their telegrams serially “regardless of the system used in their encipherment”, so a well-kept index of all intercepted traffic from a station — including messages in systems the SIS could already read — predicted the next number to within a few. The manual’s worked example takes a message from Rome of 30 December 1940 and concludes from the traffic index that its serial number “is probably either 123_ or 124_”. That is a crib of six or seven letters at a known position, before a single letter of the message has been read.

The pieces of the formula are known from Friedman’s report and from the abbreviation lists the American analysts compiled. Friedman’s report of 1940 translates one complete opening (Friedman 1940, p. 3, footnote):

Table 2 — The pieces of the formula are known from Friedman's report and from the abbreviation lists the American analysts compiled. Friedman's report of 1940 translates one complete opening ([Friedman 1940](/library/friedman-1940-preliminary-report-solution-b-machine), p. 3, footnote)

Group	Meaning
XFC	Dai-go, “Number”
GJW	15
FOV … FYX	open and close parenthesis
DD NO BB	2 of 1 — “part 1 of 2”
FOC	Gokuhi, “Secret”
FYL	Kanchō fugō atsukai, “to be kept within the Department”
CCF	new paragraph
MS GTS JVRK HI	3rd month, 16th day
FIC … FEL	begin and end spelling in kana
BKW	Beikoku, the United States
TLSI	Taishi, ambassador (with L for ai)

The groups recur because the procedure required them. FOC FYL stands at the head of secret telegrams; CFC ends sentences; LFL is a comma; FAE and FIO bracket a word in a foreign language. In the plaintext of Part 1 of the Fourteen-Part Message the English memorandum is introduced as FAE MEMORANDUM FIO — which is why MEMORANDUM was a crib worth trying above (Freeman, Sullivan & Weierud 2003, pp. 22–26).

Even the Japanese countermeasures became stereotypes. Part 1 of the Fourteen-Part Message begins with a parenthesis, FOV TATAKIDASI NI MUIMI NO MOXI WO IRU BESI FYX, which appears to be an instruction that meaningless letters are to be inserted at the opening; Parts 2 and 3 do in fact begin with runs of keyboard letters, HJKLFDSA and UREOPWNVBSKM (FSW, pp. 25–26; their own translation of the instruction is hedged). From 20 August 1941 every PURPLE message was to be divided into two to five parts and the parts enciphered out of order, with DDDD marking the end of the second part and DDBB the end of the first. That removed the message number from the front of the ciphertext. It also put DDDD and DDBB into almost every message, and the Navy’s manual promptly listed them as cribs (FSW, p. 27, citing R.I.P. 77 p. 2-37).

There were two further sources of plaintext that no procedure could hide. Embassies quoted, verbatim, the notes they received from the US government; when a few deciphered words suggested what a message was quoting, Army intelligence found the original, and some English messages were recovered 90 to 95 per cent this way. And the same message was sometimes sent to one post in PURPLE and to another in a system the SIS could already read — what the NSA’s later course called an isolog (NSA, “Red and Purple”, p. 70). By the summer of 1940, by these means, the SIS had plaintext for parts of about fifteen long PURPLE messages.

7.5 The Repetitions PURPLE Would Not Make

With fifteen messages’ worth of pairs, the analysts went looking for the cyclic structure that every machine they had met — Hebern, Enigma, their own M-134 — had shown. They found the opposite. Friedman listed the phenomena in his report; two concern this volume. Two identical plain letters in a row were never enciphered as two identical cipher letters, and there was “suppression of duplicate encipherments at the 1st and 26th intervals”.

The tool measures this on the whole English note enciphered under Part 1’s key, counting only twenties letters, since the sixes have their own 25-letter law:

Table 3 — The tool measures this on the whole English note enciphered under Part 1's key, counting only twenties letters, since the sixes have their own 25-letter law

Interval	Pairs of equal twenties plain letters	Equal cipher letters	Rate
1	242	0	0.000
2	189	3	0.016
3	438	4	0.009
25	383	20	0.052
26	456	4	0.009
27	422	17	0.040
52	442	8	0.018

At interval 1 the suppression is absolute. Freeman, Sullivan and Weierud explain why: no switch in PURPLE connects any input to the same output at two successive positions, even across the roll-over from 25 to 1, and only one twenties switch moves per letter (FSW, p. 19). The short intervals 2 and 3 are also well below chance, matching Friedman’s further note that within a line of 26 letters identical encipherments were “rare at intervals of 2 to 5”. Twenty-six is the curious one. It is far below 25 and 27 on either side. A suppression at a specific interval is a fingerprint: something in the machine is doing something specific every 26 letters.

What it is doing appears from the stepping law (PURPLE Volume 4). After each letter the sixes switch steps and exactly one twenties switch steps — normally the “fast” one, but when the sixes switch is at position 25 the “middle” switch steps instead. In any run of 26 letters, therefore, the fast switch normally steps 25 times and the middle switch once. Twenty-five steps bring a 25-position switch back to where it started. Twenty-six letters apart, the fast switch is in the same position and the middle switch has moved by one.

7.6 Isomorphs

The SIS had a word for what that implies. Military Cryptanalysis Part III (1939) defines it:

The term isomorphism (from the Greek “isos” meaning “equal” and “morphe” meaning “form”) designates the phenomena arising from the existence of two or more idiomorphs with identical formulae. Two or more sequences which possess identical formulae are said to be isomorphic.

— W. F. Friedman, Military Cryptanalysis, Part III (1939), para. 12

WARRANT, LETTERS and MISSION are isomorphic: each has the pattern of a repeated pair in the same places. Friedman adds that isomorphism is a monoalphabetic phenomenon, “but there are instances wherein it is latent and can be made patent in polyalphabetic cryptograms”, and that “in practical cryptanalysis the phenomena of isomorphism afford a constantly astonishing source of clues”. He then shows the essential technique: two isomorphic sequences are written one above the other, the letters are paired, and the pairs are linked into chains — V with C, C with S, S with L — which reconstruct fragments of the alphabets that produced them.

In PURPLE the isomorphism is latent between alphabets rather than words. The twenties pass through three switches in series. The fast switch varies from letter to letter; the slow switch stays put for 625 letters at a time; and the middle switch stays put for 25. Take the alphabet at some letter, and the alphabet 26 letters later. The fast switch is in the same position in both, and so is the slow. Only the middle switch differs, by one step. Whichever side of the fast switch the middle one sits on, the second alphabet is then the first with a fixed relabelling applied — of all the cipher letters, if the middle switch is nearer the output; of all the plain letters, if it is nearer the input. And that relabelling is the same for every letter in the stretch of 25 between two steps of the middle switch. In Friedman’s language the alphabets 26 apart are isomorphic, and the pairs of cipher letters they produce chain into a single substitution.

No single message shows this, because each position of a single message reveals only one letter of its alphabet. It needs depth: several messages enciphered from the same starting point, so that each position is seen several times with different plain letters. The tool generates six messages of 1,000 letters each in one indicator — the size of the set that broke the machine in 1940 — and asks, for every interval d from 1 to 60, whether the pairs (cipher letter at position i, cipher letter at i + d) for the same plain letter form one consistent substitution from one position to the next.

Table 4 — Isomorphs

Key (fast / middle switch)	Relation	Agreement at d = 26	Agreement at d = 52	Typical other interval
9-1,24,6-23 (#2 / #3)	cipher side	0.79	0.75	0.04–0.16
9-1,24,6-31 (#3 / #1)	plain side	0.97	0.92	0.00–0.13
9-1,24,6-12 (#1 / #2)	cipher side	0.85	0.86	0.00–0.07

At every other interval the relation between neighbouring positions agrees about as often as chance allows. At 26, and again at 52 (two middle steps, still a fixed relabelling within a stretch), it is consistent three times out of four or better. The agreement falls short of 1.00 only because a few pairs of positions straddle a step of the middle switch.

The same structure appears as chains. In the six modelled messages the plain letter T is seen at positions 13, 39, 65 and 91 — each 26 apart — and is enciphered J, P, M and K. Each cipher letter is the one before it put through the relabelling of its stretch: a chain of the kind Friedman taught analysts to build from isomorphs. Friedman’s report records the analysts finding exactly such a thing in a real English message of 1940: E enciphered as Q, then 26 letters later as Y, then 26 later as V, and the same three cipher letters QYV standing elsewhere in the message for three equally spaced E’s. “Every attempt to extend it failed,” the report says — because, as the analysts then realised, a single message did not contain enough repetitions of the same plain letter at the right spacing to build the chains out (Friedman 1940, para. 8). They estimated they needed 20 to 25 messages on the same day in the same indicator. In a thousand messages they had never found more than two.

7.7 Homologs: Making Depth That Does Not Exist

PURPLE’s key had two parts: the switch starting positions, set from an indicator chosen from a list of 120, and the plugboard alphabet, changed daily. Two messages on the same day in the same indicator were enciphered identically. Two messages in the same indicator on different days went through exactly the same sequence of switch positions, but each was wrapped in a different plugboard alphabet. Their ciphertexts looked unrelated — Friedman’s list of phenomena calls them “absolutely different” — yet underneath they were in depth.

The way out was to convert messages from different days to a common base. Friedman named the method and refused to explain it:

A method for this conversion to the same base was developed and was termed “the identification of homologs.” That is, an attempt was to be made to establish that a given letter on a certain day and another letter on a different day were treated in an absolutely identical or, more accurately speaking, homologous manner by the machine when set to the same indicator. This conversion process is too involved to explain in this report …

— Friedman, Preliminary Historical Report, 14 October 1940, para. 11

In modern terms, the two days’ alphabets differ by an unknown one-to-one correspondence between letters, and the machine underneath is the same. The tool shows both halves of the problem.

The Navy’s manual shows the same idea in working form. Its analysts kept, for each of the 120 keys, “Key Sequence Development Sheets” giving the machine’s alphabets under a standard plugboard sequence, A E I O U Y B C D F G … Z — the six followed by the twenty. A day’s cipher text was first “converted” into that standard sequence, deciphered with the sheet, and converted back; and the manual’s example shows the result agreeing with the text “as it was deciphered by means of the cryptograph” (R.I.P. 77, p. 2-9). Converting every day’s traffic to one standard alphabet is reduction to a common base, made routine once the hard part was done.

The sixes half is easy. The sixes switch’s wiring was fully known from April 1939, so on any day whose alphabet was recovered, the sixes alphabet at every position of an indicator was known. For a second day in the same indicator, the tool takes a message with about a third of its sixes plaintext known — 47 letters — and tries all 720 ways of matching that day’s six letters to the first day’s. The true matching agrees with all 47 known letters; the next best agrees with 35. The sixes of the two days are identified in a fraction of a second, as they would have been by hand in an afternoon.

The twenties half is hard, and the tool shows why. For the twenties, the first day’s alphabets are known only where that day’s messages had known plaintext — one letter per position per message. A known letter on the second day ties the two days together only where the first day happens to have seen the corresponding letter at the same position:

Table 5 — The twenties half is hard, and the tool shows why. For the twenties, the first day's alphabets are known only where that day's messages had known plaintext — one letter per position per message. A known letter on the second day ties the two days together only where the first day happens to have seen the corresponding letter at the same position

Messages known on day one	Second-day twenties letters tied to day one (of 886)
1	21
2	46
4	96
6	119

Even with the second day’s plaintext complete, one message from the first day ties fewer than 3 per cent of its letters to anything. Each tie gives one pair of homologous letters; enough of them, assembled carefully, give the whole correspondence and with it a common base. With little data, the correspondence is a jigsaw with most of its pieces missing. That is consistent with Friedman’s report that the method “succeeded in two cases” out of the whole archive — and it is why the one success that produced six messages in indicator 59173, two of them with plaintext complete or nearly so, was so precious. Freeman, Sullivan and Weierud summarise the result in one sentence: the SIS “converted all of the ciphertexts to the same alphabet, which then gave them enough messages in depth to map the switch connections of the twenties” (FSW, p. 21, citing Kelley, Big Machines).

The tool’s homolog demonstration is a reconstruction of the principle, not of the SIS’s procedure, which has not been published in detail.

7.8 Friday, 20 September 1940, Reconsidered

The six 59173 messages, reduced to a common base, were written out as distribution tables: for each plain letter, the cipher letters that stood for it, position by position. On 20 September 1940, at about two in the afternoon, Genevieve Grotjan showed Rowlett, Ferner and Small three examples on her worksheets, and the section erupted (the scene is in PURPLE Volume 5). Friedman’s report describes what she had seen only as “certain symmetries between the successive cipher equivalents of a given plain-text letter and the successive appearances of that plain-text letter in the cryptographic text” (para. 12). No published primary source shows her worksheets.

The computation above suggests what such symmetries would look like. In a set of messages in depth, the cipher equivalents of a plain letter at one position and at the position 26 later are linked by a single fixed substitution, which holds across a whole stretch of positions; the successive equivalents of one letter at 26-letter spacing form chains through those substitutions — J, P, M, K for T in the modelled message; Q, Y, V for E in the 1940 one. A distribution table makes both visible: the same pairings recurring, column after column, at a fixed interval. That is an isomorph in exactly Friedman’s sense, and the technique the SIS had been teaching for years — pair the letters, chain the pairs — was the one needed to exploit it. Whether Grotjan’s three examples were chains at 26, or the permuted columns that appear when the middle switch sits on the other side of the fast one, cannot be determined from the published record. Either way, it was the first sign that the twenties had structure at all, and from that structure the wiring followed. How it followed is Volume 8.

7.9 What These Methods Teach

Each technique in this volume exploits something the designers did not control. Cribs and stereotypes exploited procedure: message numbers, formal openings, abbreviation codes, quoted notes, the same text sent twice. None of these is a weakness of the machine, and no machine can fix them; they are why every modern cipher is designed to be secure even when the attacker knows or chooses the plaintext. Isomorphs exploited structure: the fact that only one of PURPLE’s three switches moved at a time, and that one of them came back to the same place every 26 letters. Homologs exploited keying: a short list of 120 starting points, reused for months with only the plugboard changed. All three lessons were absorbed by the same people when they designed SIGABA — irregular stepping to destroy isomorphs, and strict procedure to deny cribs (Volumes 9 and 10).

---

Next — Volume 8: Reconstructing a Machine Never Seen. From the pattern to the wiring: how 25 sixes alphabets were recovered from known plaintext — tested here on the real Part 1 intercept — how wire classes of the fast switch fall out of messages in depth, and how a working copy was built from telephone stepping switches before anyone had seen the Japanese machine.