The Codebreakers — Volume 6 — Statistics as a Weapon

6.1 About This Volume

Volumes 1 to 5 of this series describe the people of the Signal Intelligence Service (SIS) and how they were trained. This volume and the two after it describe what they were trained in. The subject here is the oldest and most general of their tools: the statistics of coincidence. It began with a single paper written by William Friedman at Riverbank around 1920, was turned into a set of named tests by Solomon Kullback in the 1930s, and by 1939 was the first thing any SIS analyst did with a new cipher. It is also the part of the school’s method that has lasted longest. The index of coincidence is still the first statistic taught in any course on classical cryptanalysis, and it is still used to score candidate decipherments in computer attacks on historical machines, including the modern computer solution of PURPLE.

The volume works through the tests in the order an analyst of 1939 would have applied them. First the index itself, computed on seven kinds of text, from plain English to a real PURPLE intercept. Then Kasiski’s repeats, the column test and Kullback’s chi test, used together to take apart a Vigenère cipher — the textbook case, and the case for which the tests were designed. Then the phi test, which asks of a short sample whether it is a single alphabet or many. Last, the same tests applied to PURPLE, where they show both what they could do — expose the six-letter group and its 25-letter cycle within weeks — and what they could not: the twenties, which look statistically like random letters.

Every number in the volume was computed by 03-outputs/tools/stats_tests.py, which imports the PURPLE simulator of the PURPLE unit (Purple/03-outputs/tools/purple_sim.py, checked against fifteen published test vectors) and runs a self-test of its own. The texts are real: the English of the Japanese note of 7 December 1941 (the “Fourteen-Part Message”), a Japanese story romanised in the Foreign Ministry’s spelling, and the intercepted PURPLE ciphertext of Part 1 of that note as it was received by the US Navy on 6 December 1941. How the PURPLE machine works is described in PURPLE Volume 4; the narrative of the break is PURPLE Volume 5. Neither is repeated here.

6.2 The Problem Statistics Solves

A simple substitution cipher keeps the shape of its plaintext. If E is the commonest letter of the message, then whatever letter stands for E is the commonest letter of the ciphertext, and an analyst can count, guess, and test. Every serious cipher from the sixteenth century onwards was designed to break that link by using many alphabets in turn. In a Vigenère cipher with a five-letter key, every fifth letter is enciphered in the same alphabet, so each letter of the plaintext is spread over five different cipher letters. In a rotor machine or a stepping-switch machine the alphabet changes with every letter. The frequency count of the ciphertext flattens out, and the old method has nothing to hold.

Flat is not the same as random, however. A polyalphabetic ciphertext is a mixture of several monoalphabetic ciphertexts, and each component keeps its plaintext’s shape. The problem is to find the components. Before Friedman, there was one general method. Friedrich Kasiski, a retired Prussian infantry officer, published it in Berlin in 1863 in Die Geheimschriften und die Dechiffrir-Kunst: when a word recurs in the plaintext at a distance that is a multiple of the key length, it produces a repeated sequence in the ciphertext, so the distances between repeated sequences are multiples of the period. Charles Babbage seems to have found the same thing independently in the 1840s and never published it (Kasiski examination). Kasiski’s test depends on repeats, and repeats are luck. Short messages, or messages whose plaintext happens not to repeat at the right distance, defeat it.

What was missing was a way to measure “how much like plaintext” a set of letters is, without knowing any of the plaintext. That is what Friedman supplied.

6.3 Friedman’s Paper

William Friedman wrote The Index of Coincidence and Its Applications in Cryptography at Riverbank Laboratories, George Fabyan’s private research estate at Geneva, Illinois, where he and Elizebeth Friedman ran the Department of Ciphers (Volume 2). Riverbank published it as Publication No. 22 in 1922, printed in Paris; a French edition dated 1921, translated by General Cartier, in fact appeared after the English one (Shulman, An Annotated Bibliography of Cryptography, 1976, pp. 84–85, as quoted by HistoryofInformation.com). David Kahn called it “the most important single publication in cryptology”, a verdict the National Security Agency still quotes in its introduction to the Friedman Collection (NSA, Friedman Collection: Background).

The paper’s opening states its claim with Friedman’s usual care: the frequency tables of certain ciphers “have definite characteristics of a mathematical or rather statistical nature”, and these can be used to solve them “without any assumptions whatever of plain-text values for the cipher letters” (Introduction, p. 1, in the War Department reissue of 1935). Its two worked examples were the cipher used by the American Expeditionary Forces’ headquarters clerk Vogel, a disk cipher with up to 125 mixed alphabets, and a combined substitution-transposition published by Schneider in 1912. Both were solved by counting coincidences — places where the same letter stands in the same column when two stretches of text are laid one above the other — and choosing the arrangement that produced the most.

Two details of the paper are worth knowing, because both are often lost in retelling.

First, the paper was a manual of physical work. Friedman instructs the reader to write the message on “long strips of cross-section paper”, 125 letters to a line, so that “the various strips can then be arranged to bring the proper letters into superimposition according to each hypothesis in turn” (1935 edition, p. 11, footnote). The coincidence count was made by sliding strips and counting by eye.

Second, what Friedman called the “index of coincidence” in that paper is not the statistic that now bears the name. On p. 39 he defines it as a measure of fit between two superimposed sequences: the number of coincidences, less the number of non-coincidences, divided by the total. The modern index — the probability that two letters drawn from a text are the same — appears in the 1935 text only in a note added in revision, which cites later work by Friedman and Kullback and gives the two constants that every analyst of the 1930s learned: the ratio of actual to possible coincidences is “.038 for an incorrect case and .066 for a correct one”. The name stayed while the definition matured.

6.4 Kappa, Phi and Chi

The names came from Solomon Kullback, one of the three junior cryptanalysts Friedman hired in 1930 (Volume 3). Kullback had a doctorate in mathematics from George Washington University, and in the 1930s he wrote the SIS textbook Statistical Methods in Cryptanalysis; its revised edition was printed by the Government Printing Office in 1938 (NSA scan; Library copy). It gives the coincidence ideas the form in which they were taught for the next half century. Three tests do almost all the work.

Kappa. Kullback begins with the probability that two letters chosen at random coincide. For random text in a 26-letter alphabet it is 1/26: “The foregoing italicized expression is important enough to warrant assigning a special symbol to it, viz, κr (read ‘kappa sub-r’). For a 26-element alphabet, then, κr = 0.0385.” For English telegraphic plaintext the corresponding sum of squared letter probabilities “is found to be 0.066”, κp. The kappa test superimposes two texts and counts the fraction of columns in which they agree. If the two were enciphered by the same sequence of alphabets — if they are “in depth” — the fraction approaches κp, because each column is then a single alphabet and two letters in it coincide exactly when the plaintext letters do. If not, it approaches κr. The same test applied to a text and a shifted copy of itself finds a period.

Phi. For a single distribution of N letters with frequencies f, the observed number of coincident pairs is φ = Σ f(f − 1). Its expected value is κ × N(N − 1), so for a sample of English Kullback gives 0.0661 N(N − 1) and for random letters 0.038 N(N − 1). “For convenience we shall refer to the test described above as the φ (Phi) test.” Dividing φ by N(N − 1) gives the modern index of coincidence. Kullback’s table of constants includes, beside English, French and German, a line for “Japanese (Romaji)”: 0.0819. The figure matters for PURPLE, whose plaintext was very often romanised Japanese.

Chi. To decide whether two distributions are the same alphabet — whether two columns of a polyalphabetic cipher were enciphered with related alphabets, or whether a column, slid to a trial shift, matches plain English — Kullback multiplies the frequencies letter by letter and sums: χ = Σ f₁f₁′. For two matching distributions χ approaches 0.066 N₁N₂; for unrelated ones, 0.038 N₁N₂.

Behind all three is one idea, which Kullback put in a footnote that deserves to be better known:

Indeed, we might venture to define cryptanalysis as the solution of cryptograms by an analysis and application of the “invariant” characteristics of the cryptographic system employed. A cryptographic system which had no invariant characteristics would be secure against unauthorized decipherment.

— S. Kullback, Statistical Methods in Cryptanalysis (1938), p. 81, note

Volume 10 returns to that sentence, because SIGABA was an attempt to build exactly such a system.

The normalised form now common in textbooks — the index multiplied by 26, so that random text scores 1.00 and English about 1.73 — is the “delta I.C.” of the later Friedman–Callimahos Military Cryptanalytics. It is the same number on a friendlier scale.

6.5 Seven Texts, One Number

The index of coincidence needs only a count. The table and figure below give it for seven texts, each counted in full by the tool.

Table 1 — Seven Texts, One Number

Text	Letters	Σ f(f − 1)	Index	× 26
English: the Fourteen-Part Message	12,643	11,448,820	0.0716	1.86
Japanese romaji: Niimi Nankichi’s “Gongitsune”	6,714	4,101,216	0.0910	2.37
The same with ai → L and ei → X	6,569	3,697,410	0.0857	2.23
Random letters	12,643	6,153,656	0.0385	1.00
Vigenère, key MAGIC, on the English	12,643	7,022,688	0.0439	1.14
PURPLE: the real Part 1 intercept	1,257	62,844	0.0398	1.03
PURPLE: the whole English note, Part 1’s key	12,643	6,338,952	0.0397	1.03

Several things in the table repay a second look.

The English text scores 0.0716, higher than Kullback’s 0.0661. That is not an error; it is the point of the statistic. The Fourteen-Part Message is diplomatic prose in which “the Government of the United States” and “the Japanese Government” recur dozens of times. A narrower vocabulary means more coincidences. Kullback’s constant was an average over “telegraphic plain text”; any particular text sits near it, not on it.

The romaji text scores 0.0910 against Kullback’s 0.0819, for the same reason in a stronger form. Japanese written in Latin letters is dominated by five vowels and a handful of consonants, so it is more repetitive than English at the level of single letters. The story used here is ordinary narrative, romanised in the spelling the Foreign Ministry used for its telegrams (si, ti, tu, zi rather than shi, chi, tsu, ji) (Freeman, Sullivan & Weierud 2003, p. 24; Library copy). Diplomatic Japanese was different again. From 1 May 1939 the Foreign Ministry abbreviated its PURPLE texts with a system Friedman likened to the Phillips Code of American telegraphers — CFC for a full stop, BKW for Beikoku (the United States), L for ai, X for ei — and many of the code groups were words with their vowels removed (Friedman 1940, pp. 2–3). Applying only the two vowel contractions lowers the index from 0.0910 to 0.0857. For fully abbreviated diplomatic Japanese the SIS documentation gave an expected index of 0.0554, and the actual plaintext of one PURPLE message of 27 July 1942 measures 0.0578 against 0.0392 for its ciphertext (FSW, p. 32). The abbreviations were meant to save cable charges; they also pushed the plaintext’s statistics towards the random value, which made every test in this volume weaker.

The Vigenère cipher scores 0.0439: five alphabets averaged together. The PURPLE texts score 0.0398 and 0.0397, within a few thousandths of random. On this measure alone, PURPLE ciphertext cannot be told from a stream of letters drawn from a hat.

6.6 A Vigenère, Taken Apart

The tests were built for periodic ciphers, and it is worth seeing them work there before turning to PURPLE. The tool enciphers the 12,643 letters of the English note with the key MAGIC and attacks the result as an analyst of the 1930s would.

Kasiski. The ciphertext contains 2,359 trigrams that occur more than once, giving 7,986 distances between successive occurrences. Of those distances, 6,976 are divisible by 5; only 1,904 by 4, 1,348 by 6 and 1,247 by 7. The factor 10 scores 3,571 and 15 scores 2,245, as multiples of 5 must. The period is 5.

The column test. Writing the ciphertext in rows of p letters and averaging the index of coincidence of the columns gives a second, independent answer:

Table 2 — The column test. Writing the ciphertext in rows of p letters and averaging the index of coincidence of the columns gives a second, independent answer

Trial period	1	2	3	4	5	6	7	8	9	10
Mean column index	.0439	.0439	.0439	.0439	.0716	.0439	.0440	.0438	.0439	.0716

At the right period each column is a single Caesar alphabet and recovers the index of the English, 0.0716. At every wrong period, the columns stay mixed. (Period 10 scores the same as 5 because each of its columns is half a column of period 5.) No repeated sequence is needed; with enough text the column test finds the period by itself.

Chi. With the period known, each column is a Caesar shift of English. Sliding the column through all 26 shifts and computing Kullback’s chi against the frequencies of the English note picks the shift whose distribution matches:

Table 3 — Chi. With the period known, each column is a Caesar shift of English. Sliding the column through all 26 shifts and computing Kullback's chi against the frequencies of the English note picks the shift whose distribution matches

Column	Best shift	χ at best	χ at next best
1	M	0.0711	0.0476
2	A	0.0727	0.0482
3	G	0.0715	0.0471
4	I	0.0719	0.0486
5	C	0.0713	0.0475

The key is MAGIC. In every column the best shift scores near κp and the runner-up near κr: the gap between a right and a wrong hypothesis is the gap between 0.066 and 0.038, measured in a form that a clerk with a pencil could compute.

6.7 The Phi Test on a Short Sample

A long text makes every test easy. The real question for an analyst is often whether a short stretch — a single column of a few dozen letters, a fragment of one message — is one alphabet or several. The phi test answers it. For 200 letters, the expected number of coincident pairs is κp × 200 × 199 = 2,850.9 if the sample is monoalphabetic (using the index of the English corpus for κp) and 1,530.8 if it is random. The tool measures:

Table 4 — A long text makes every test easy. The real question for an analyst is often whether a short stretch — a single column of a few dozen letters, a fragment of one message — is one alphabet or several. The phi test answers it. For 200 letters, the expected number of coincident pairs is κp × 200 × 199 = 2,850.9 if the sample is monoalphabetic (using the index of the English corpus for κp) and 1,530.8 if it is random. The tool measures

200 letters of…	Observed φ	Expected if one alphabet	Expected if random
English plaintext	2,834	2,850.9	1,530.8
The Vigenère	1,636	2,850.9	1,530.8
The real PURPLE intercept	1,566	2,850.9	1,530.8

The English sample is unmistakably a single alphabet, and the two ciphertexts are unmistakably not. The test cannot say what the alphabets are. It says where to stop looking.

6.8 The Sixes as a Statistical Signature

When the first messages in the new Japanese machine arrived in March 1939, the SIS had already broken its predecessor, RED (PURPLE Volume 3). In RED the alphabet was split into six letters and twenty, enciphered separately, so that six cipher letters always stood for six plain letters. Friedman’s report of October 1940 records that in the first PURPLE messages, “six of the twenty-six letters” appeared with abnormal frequency (Friedman 1940, p. 1). The analysts concluded that the new machine kept RED’s split. They were right, and the reason the six showed is simple arithmetic.

The plugboard sends six plain letters to the sixes switch and twenty to the twenties. Whatever the six plain letters are, the six cipher letters must carry all of their occurrences between them. If the six plain letters are, between them, more common than an average six — as they are whenever they include two or three of E, T, A, O, N — then the six cipher letters are more common than an average six cipher letters, and they stand out. On 6 December 1941 the day’s alphabet began N O K T Y U, so those were the six. In the English of Part 1 they account for 29.8 per cent of the letters against the 23.1 per cent (6/26) they would carry if all letters were equally common.

The figure shows both the method and its limits. In the real intercept the six commonest letters are O K U N I H; two of the true six are missing and two impostors are present. Freeman, Sullivan and Weierud found the same thing in their analysis of this message — “two letters, H and I, are more numerous than the actual sixes letter T, while ten letters exceed the sixes letter Y” — and showed that in a 565-letter message of November 1941 whose plaintext was a two-letter code, frequency gave almost no help in picking them out (FSW, pp. 22–24). The cure was more text. All messages sent on one day used the same alphabet, so the day’s traffic could be counted together: FSW’s count of Parts 1 to 7 of the Fourteen-Part Message puts the six at the top. The tool’s encipherment of the whole note does the same.

6.9 Coincidences at Twenty-Five

Frequency says which letters are the sixes. Coincidence says how they are enciphered. The sixes switch steps once per letter through 25 positions, so every 25 letters it returns to the same alphabet. Two identical sixes plaintext letters 25 places apart are therefore enciphered identically. The tool slides the real Part 1 intercept against itself and counts, at every shift from 1 to 80, the positions where the two copies show the same letter.

At a shift of 25 the intercept shows 69 coincidences in 1,260 comparisons, a rate of 0.0548; at 50, 65 in 1,235 (0.0526); at 75, 63 in 1,210 (0.0521). The average over every other shift from 1 to 80 is 0.0381. Measured against that background, the three peaks stand 3.1, 2.7 and 2.5 standard deviations high. No other shift in the range reaches 2. In a single 1,285-letter message — the real one, with its garbles — the period of the sixes is visible.

The same idea can be pushed down to individual letters. For each cipher letter, the tool counts how often it recurs exactly 25 and exactly 50 places later. The top three by that count are K, O and T, all sixes; T, which frequency had ranked seventh, is lifted into the six by the coincidence count while H falls out. I still intrudes and Y is still hidden, but the two measures together point at five of the six correct letters from one message. Over the long text both measures pick out exactly N O K T Y U.

Friedman’s report says only that the analysts found the sixes to be enciphered by “a series of 25 heterogeneous and differently mixed alphabets” used in a fixed cycle, “a carefully selected set of 25 of the possible 720 permutations”, and that the deciphering chart for them was complete by 10 April 1939. It does not say which test showed the 25-cycle first. The NSA’s later course on the problem taught the analyst to find the sixes’ starting point by trying all 25 positions (NSA, “Red and Purple: A Story Retold”, pp. 78–79). The computation above shows that the period was within reach of the tests in Kullback’s book, from the first messages, which is consistent with the speed — a few weeks — with which the sixes fell.

6.10 What the Statistics Could Not See

The twenties are another matter. Twenty plain letters pass through three stepping switches in series, one of which moves at every letter, and the 25 positions of each switch are wired independently, so that no alphabet is a shifted copy of another (PURPLE Volume 4). The whole machine does not repeat for 15,625 letters, far longer than any message. There is no column test to make, because there is no period inside a message; the twenties’ index of coincidence is the random one.

The report of October 1940 shows the analysts finding exactly that, and finding something stranger. Repetitions of three or four cipher letters occurred, but the number “was less than the number to be expected had the letters comprising them been drawn at random out of a hat!” 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” (Friedman 1940, paras 7–8; quoted more fully in PURPLE Volume 5). The real Part 1 intercept, profiled above, shows the second of those effects even in its ciphertext: at a shift of 26, the coincidence rate falls to 0.0286, the lowest value in the whole range, 1.8 standard deviations below random. Ciphertext that is too orderly in the wrong direction is also a signature. Volume 7 follows it to the discovery that broke the twenties.

6.11 By Hand

None of this was computed. Every count in this volume was, in 1939, a count made by a person. Friedman’s Military Cryptanalysis, Part I (1938) describes how: a frequency distribution is made by “indicating every fifth occurrence of a letter by an oblique tally”, so that the count can be read off in fives, and “cross-section paper is very useful for this purpose” (Friedman 1938, Part I; Library copy). The facsimile below is a tally of the first 300 letters of the Part 1 intercept, drawn in that convention from the tool’s counts.

The Navy’s manual for working PURPLE traffic, R.I.P. 77 of January 1941, includes a printed form for exactly this work: Worksheet 6-A, a “Cipher Text Frequency Tally Sheet” with 25 numbered rows under each block of letters. Twenty-five rows is not an accident. It is a tally of each cipher letter at each of the 25 positions of the sixes cycle — a coincidence table for the sixes, laid out for a pencil.

Counting at this scale was the first thing to be mechanised. The SIS had IBM punched-card machines from late 1934, and Friedman’s report of 1940 credits the tabulating supervisor Ulrich J. Krapfl and Mary J. Dunning with “countless tabulating machine operations” in the PURPLE work. The Navy paid Vannevar Bush at MIT to build a machine that would count coincidences between punched tapes at 20,000 comparisons a minute. How that worked, and failed, is Volume 11.

6.12 Why It Is Still Taught

The tests survived their machines. Abraham Sinkov, the third of Friedman’s 1930 hires, wrote the textbook through which most English-speaking students still meet them: Elementary Cryptanalysis: A Mathematical Approach, published by the Mathematical Association of America in 1966 as volume 22 of its New Mathematical Library. Freeman, Sullivan and Weierud’s computer solution of a PURPLE message in 2003 used the index of coincidence as its first scoring function, then moved to logarithms of bigram and trigram frequencies, citing Sinkov for the method (FSW, pp. 32–33). Every modern hill-climbing attack on a classical cipher does the same thing: it measures how close a trial decipherment is to the statistics of language, and climbs.

Kullback took the ideas further than anyone. After the war, with Richard Leibler, he published “On Information and Sufficiency” (Annals of Mathematical Statistics, 1951), which defined the measure of the difference between two probability distributions now known as the Kullback–Leibler divergence. It is a direct descendant of the chi test: a principled way of asking whether two distributions are the same. It is used today throughout statistics and machine learning, by people who have never heard of a tally sheet.

The deepest lesson is Kullback’s footnote. A cipher is broken through whatever it leaves invariant. Coincidence statistics are simply the most general way of detecting invariants that no one has yet identified. RED left its vowels invariant; PURPLE left its sixes period invariant, and — as Volume 7 shows — an invariant in its twenties that no frequency count could see. The designers of SIGABA, who were the same people, set out to leave nothing at all (Volumes 9 and 10).

---

Next — Volume 7: Cribs, Stereotypes, Isomorphs and Homologs. When statistics run out, the analyst guesses — and Japanese diplomatic formulae made the guesses good. How a crib was placed in the real Part 1 intercept, why the twenties repeated themselves 26 letters apart, and what Genevieve Grotjan saw on 20 September 1940, reconstructed letter by letter.