PURPLE — Volume 3 — RED — The Type 91 Machine and Its Break

3.1 About This Volume

PURPLE did not arrive out of nowhere. Before it, the Japanese Foreign Ministry enciphered its most important telegrams on an earlier machine, the 91-shiki ōbun injiki (九一式欧文印字機, “Type 91 printing machine for European characters”), also called Angōki Taipu A, the Type A cipher machine. The American codebreakers of the Army’s Signal Intelligence Service (SIS) called it RED. RED and PURPLE worked on entirely different principles, but PURPLE inherited one feature from RED that decided its fate: the division of the alphabet into a group of six letters and a group of twenty. This volume describes how RED was built, how its traffic first appeared, and how it was broken, first in Britain, then by the US Army and Navy. It ends where Volume 4 begins: with a RED message, read in Washington in December 1938, announcing the machine that would replace it.

The volume leans on three kinds of source. The machine’s construction comes from Freeman, Sullivan and Weierud’s study of PURPLE, which summarises RED from Deavours and Kruh (Cryptologia 27, 2003). The American solution comes from an NSA Cryptologic Quarterly article of 1984–85, “Red and Purple: A Story Retold”, which paraphrases an Army Security Agency history and was released in 2012 (copy on Wikimedia Commons). Dates and outcomes come from NSA’s Center for Cryptologic History and the Navy history by Frederick Parker. Where these disagree, the text says so.

3.2 A Machine for Pronounceable Cipher

In 1931 Herbert Yardley published The American Black Chamber, a memoir of his years running the US cryptanalytic bureau of the 1920s, including its success in reading Japanese diplomatic codes during the Washington Naval Conference (Volume 2 tells that story). NSA’s own history says the Foreign Ministry, “embarrassed by Herbert Yardley’s revelations”, turned increasingly to machine systems (NSA Center for Cryptologic History, “Red and Purple”). The Type 91 was the result. The number is the Japanese imperial year 2591, which is 1931.

The machine had to fit an odd commercial constraint. International telegraph tariffs of the time charged less for text that could be pronounced, a rule meant to favour plain language and code words over random letter groups. The Cryptologic Quarterly history defines pronounceable as “a minimum of two vowels per five-letter grouping” and notes that Romanised Japanese has an unusual property: if every vowel is replaced by a vowel and every consonant by a consonant, the result stays pronounceable (CQ 1984–85, p. 64). Freeman, Sullivan and Weierud point out that random-text telegrams cost twice as much as plain language, and that Boris Hagelin had patented a device (US Patent 1,484,477) that turned code numbers into pronounceable letter groups such as “olavuxutip” (FSW, p. 14).

So RED split the alphabet. The six vowels, A E I O U and Y, were enciphered only among themselves; the twenty consonants only among themselves. A message enciphered on RED in this mode still looked like a string of Japanese syllables. The split saved money and wrecked the security of the machine, and the habit of thinking in “sixes and twenties” outlived the tariff that prompted it.

3.3 How RED Worked

RED’s cipher element was a single wired wheel of an unusual kind, often called a half-rotor. On one side, 26 slip rings on the shaft each carried one letter in from the keyboard through a plugboard. On the other, a commutator of 60 contacts carried the letters out. The 26 input contacts were split into a group of 20 and a group of 6, and the rotor had 60 positions because sixty is the least common multiple of twenty and six: the twenty-letter wiring repeats three times around the commutator and the six-letter wiring ten times, so every step of the rotor presents a fresh alignment to both groups (FSW, p. 14, after Deavours and Kruh, Machine Cryptography and Modern Cryptanalysis, 1985, pp. 218–219).

A wired wheel that simply advanced one step per letter would produce a cipher with a short, obvious period. RED’s designers disguised the period with a break wheel: a pin wheel geared to the rotor. Freeman, Sullivan and Weierud describe it as advancing the rotor “one, two, or three positions for each letter enciphered and with a variable period of 41 to 43 positions.” The Cryptologic Quarterly history gives the American analysts’ picture of the same thing: a wheel of 47 teeth, “some of which were inoperative”; in the December 1936 traffic, 43 of the 47 were effective, giving four skips in each cycle (CQ, pp. 65–66). Pulling a pin made the rotor jump an extra step at that point in the cycle; which pins were pulled was part of the key.

The rest of the key was the plugboard, which connected keyboard letters to the slip rings and changed daily, and the starting positions of the wheels, which came from a five-digit indicator at the head of each message. Input and output were ordinary typewriter mechanisms: the operator typed on one, and the result was printed by another. In the Navy example now at Fort Meade, the plugboard is a nest of black cords in a well at the front of the case beside a maker’s plate.

3.3.1 Where the design came from

Accounts of RED’s origin agree that it came out of the Japanese Navy’s technical establishment and that it drew on commercial European designs. The English-language secondary literature says it was developed from a machine supplied by Boris Hagelin’s firm, which, unwilling to trust Japanese respect for its patents, sent a more primitive device based on Arvid Damm’s work; the separate encipherment of vowels is described as a Japanese addition (Wikipedia, “Type A Cipher Machine”, citing Kahn and Smith). Freeman, Sullivan and Weierud call the wheel a “Damm ‘half rotor’”, and note that the Japanese had bought other Hagelin devices. The detailed story of the purchase rests on secondary accounts and is not repeated here as fact.

3.3.2 The Navy’s machines

The Imperial Japanese Navy used Type 91 machines of its own, and it is a Navy example that survives at the National Cryptologic Museum, with the Navy Technical Research Institute’s plate on it. The US Navy’s codebreakers worked against a related naval-attaché system that they designated M-1, or ORANGE. Agnes Meyer Driscoll, the Navy’s senior civilian cryptanalyst, is credited with leading its solution early in 1935 (NSA Hall of Honor biography). Frederick Parker’s history of Navy communications intelligence gives the colour names the Americans settled on: Red for the A machine, Purple from 1939 for the B machine, and Coral for a naval-attaché machine introduced in 1939 (Parker, Pearl Harbor Revisited, p. 20). Volume 9 returns to CORAL and its sister JADE.

3.4 The Traffic Arrives

The dates of RED’s first appearance depend on which American history is read. The Cryptologic Quarterly account, drawn from an Army Security Agency history, says the first messages of the system it calls M-3 were intercepted in March 1933, and that they showed “two classes of letters, vowels and consonants, with different frequency distributions” (CQ, p. 64). NSA’s short web history says SIS “first encountered intercept from the ‘Type A’ machine in 1935” and that the Ministry adopted the machine that year (NSA, “Red and Purple”). Frank Rowlett’s NSA biography says the SIS team “began their analytic assault against Japanese diplomatic communications in 1932” and solved the machine “three years later” (NSA Cryptologic Almanac, “Frank Rowlett”). The likeliest reading is that a little Type 91 traffic was intercepted from 1933, that serious work began only when there was enough of it, and that the solution came in 1935–36; the sources do not allow a single date to be stated with confidence.

With little traffic at first, the messages went, in the Quarterly’s phrase, into one of those “to be looked at when there is nothing else to do” bins. The analysts had already guessed why the vowels behaved as a class: pronounceable text was cheaper. In March 1934 the character of the cipher changed. The text still fell into a class of six letters and a class of twenty, but the six were no longer the vowels. At the same time the telegraph regulations changed and the special rate for pronounceable text was withdrawn (CQ, p. 64). From then on the plugboard could put any six letters into the six-letter group, as Freeman, Sullivan and Weierud also record (FSW, p. 14). The tariff reason for the split had gone, but the split stayed in the machine.

The first study of the traffic established five things, which the Quarterly lists:

1. The messages had a five-digit indicator in the first group of the message.
2. The text was definitely cipher.
3. The nature of the substitution was such that repetitions were permitted to occur.
4. There was a radical change on the 1st, 11th, and 21st of each month.
5. The keying element produced a long cycle which appeared indeterminate in length.

— Cryptologic Quarterly 3 (1984–85), p. 64

The fourth observation mattered most. A key that changed on the 1st, 11th and 21st meant that every message sent in one ten-day period shared part of its key. Collect enough messages from one period and they could be attacked together.

3.5 The Break

That collection arrived from Manchuria. In 1936, the Quarterly says, an influx of cipher messages came in at ten to fifteen a day, with extensive traffic between 11 and 20 December, a single cipher period. The first attack on the December messages stalled, and the analysts went back to the 1933 messages, the ones in which vowels were still enciphered as vowels.

3.5.1 The vowel wheel

One of the analysts, “a Japanese linguist”, saw a way in through the language itself. Romanised Japanese is full of doubled vowels (oo, uu) and vowel–consonant–vowel patterns such as o-o. If the vowels were enciphered by a wheel that stepped one place per letter, then a doubled plaintext vowel would show up as two ciphertext vowels standing in a fixed relationship: adjacent on the wheel. The analysts counted, in the longest 1933 message, how often each vowel followed each other vowel directly, and how often each pair occurred with one consonant between. In the second table the highest count was 36, for I followed by O; the highest in the O row was O–A, at 35. Chaining the highest counts in this way gave two fragments, I–O–A and E–Y–U, and the table of adjacent vowels suggested the order Y–O–U–A–E–I. With a sequence for a six-letter wheel, the analysts could substitute trial values for the vowels and start guessing plaintext from what they knew of earlier messages (CQ, pp. 64–65).

Turning to the December 1936 messages, where the six letters were no longer vowels, they isolated the sixes and found their order to be B-E-I-H-O-X, but with a puzzle: some messages ran B-E-I-H-O-X and others ran X-O-H-I-E-B. The machine could evidently run in either direction. Later instructions confirmed it: for key numbers starting with 0 to 3 the machine ran forward, and for 4 to 9 in reverse (CQ, p. 66).

3.5.2 The break wheel

The sixes stepped irregularly, and the irregularity had to be explained. The Army analysts consulted the Navy. Lieutenant Joseph Wenger of the Navy’s Code and Signal Section reported that the Navy had worked a machine “with a 6-wheel, a 20-wheel, and a break wheel of 47 teeth, some of which were inoperative” — presumably the attaché machine that Driscoll’s section had solved. That gave the Army a model to test.

If the break wheel had 47 effective teeth, the sixes would repeat on a cycle of 6 × 47 letters; if some teeth were inoperative, on 6 × (the number that worked). The messages were under 2,000 letters, too short to see the full cycle of the whole machine, so the analysts concentrated on the sixes and counted coincidences at every width from 6 × 31 to 6 × 47. The highest count came at 6 × 43, a width of 258 letters. The hypothesis — a 47-position wheel with 43 effective teeth — was correct. Writing a message out on a cycle of 43 letters lined up the places where the wheel skipped, four skips per cycle, and comparing adjacent columns gave the relative shift between them (CQ, pp. 65–66).

“Further analysis,” the Quarterly says, “led to a complete understanding of the Red machine and of the indicator system of the messages.”

3.5.3 Rowlett and Kullback

The SIS work against RED is credited above all to Frank Rowlett and Solomon Kullback, two of the three junior cryptanalysts William Friedman hired in 1930 (the third was Abraham Sinkov). NSA’s museum account of the PURPLE exhibit tells the moment of the break as Rowlett remembered it: from the hundreds of messages he had examined, three were exceedingly long; if they had been enciphered with the same key, a pattern resembling Japanese words might show through. The team tested the idea the next morning, and “by noon they were on their way” (NSA, “The Magic of Purple”). SIS produced its first translation from a RED decrypt in February 1937 (NSA, “Red and Purple”).

3.6 The British Break

The British were first. At the Government Code and Cypher School, Hugh Foss, who had spoken Japanese from childhood, and Oliver Strachey worked together on a Japanese naval system that the Americans called M-1, and a few months later solved the Type A machine used by naval attachés and the Foreign Office (GCHQ, “Oliver Strachey”; GCHQ, “Hugh Foss”). GCHQ and most later accounts date this work to 1934, a year or more ahead of the American solution. There was no exchange of results between London and Washington at the time; cooperation on Japanese machines came only in 1941, when an American PURPLE analog went to Britain (Volume 6).

Foss’s connection with Japanese machines did not end there. In 1944 he went to Washington and, with Hugh Alexander, helped the Americans against CORAL, the Japanese naval-attaché machine that succeeded the M-1 (GCHQ, “Hugh Foss”).

3.7 Reading RED

Once a cipher machine is understood, reading it at speed means building something that does what it does. The SIS built analogs of RED, and two survive at the National Cryptologic Museum. One is a paper slide: two concentric alphabet discs, one for each class of letters, turned by hand. The other is a mechanical analog with a keyboard, built to step its two alphabet wheels the way the break wheel stepped the original.

The Cryptologic Quarterly describes the mechanical analog: “a plug board, an interrupter wheel, a large alphabet wheel, a small alphabet wheel, a reversing gear, and an operating handle. The two alphabet wheels are under the plugboard.” The large wheel carried the twenty-letter alphabet and the small one the six; the interrupter wheel reproduced the break wheel’s skips; the reversing gear handled keys that ran backwards (CQ, p. 66).

3.7.1 The operator’s recipe

The keys followed a routine that the Americans reconstructed in full. There were 240 indicators, each giving starting settings for the machine’s wheels; the plugboard order changed daily. The five-digit indicator at the head of a message was disguised by adding a number that depended on the ten-day period, and the analysts’ deciphering instructions for the later M-3A variant begin by taking it off again:

1. Obtain the message key number used in enciphering by subtracting from the transmitted key number the following numbers: a. 1st to 10th of the month — 32210 b. 11th to 20th of the month — 23120 c. 21st to the end of the month — 12320
2. Enter table 1-A with the date and pick out the plugboard sequence.
3. With the key number (obtained by subtraction) enter table 2, pick out the initial settings for wheels B, C, and D, and set the wheels accordingly.
4. From table 2 pick out pin settings for interrupter wheel and set pins.
5. Decipher the first five letters of text. Reset the machine to its original setting. Decipher the next 495 letters. Pause. Pull handle 10 times. Continue.

— Cryptologic Quarterly 3 (1984–85), pp. 66–67, paraphrasing the Army Security Agency history

The last step records a Japanese security rule — after the first 500 letters the machine was advanced ten idle steps — that, the history notes, “was in effect for only a few months.” Recipes like this one are the real product of a cryptanalytic break: once they exist, reading the traffic is clerical work.

3.7.2 What RED gave away

Reading RED gave Washington a view into Japanese diplomacy for several years. NSA’s history gives an example: a decrypt of November 1936 revealed to American policymakers a secret clause in the Anti-Comintern Pact with Germany, which committed each party to support the others “regardless of the circumstances” (NSA, “Red and Purple”). Japanese messages enciphered in RED were also read by the British, the Germans and the Russians (FSW, p. 15, citing Kelley, Big Machines).

3.8 Enter Type B

Reading RED also gave warning of its successor. In December 1938 a message appeared in RED authorising a man named Okamoto to put “certain cryptographic devices” into service. The diplomatic officer called them Type B cipher machines; they were to replace the Type A for highly secret communications between Tokyo and its important embassies, and they would go into effect on 20 February 1939 (CQ, p. 68, citing Friedman’s Preliminary Historical Report on the Solution of the “B” Machine, 1940). NSA’s history puts it more plainly: “In late 1938, a cipher expert traveled to Japan’s major overseas diplomatic posts to install a new cryptodevice.”

The first Type B message the Americans received after 20 February came from Warsaw. Its indicator was not of the A type, and six of its 26 letters had abnormally high frequencies — the signature of a machine that still split the alphabet six and twenty. The Americans assumed at first that the B machine was a modification of the A (CQ, p. 68). It was not, and that assumption would cost them months.

Only the larger posts — Washington, London, Berlin, Rome, Moscow among them — received the new machine. Smaller posts kept RED, and so did places like Hsinking and Shanghai. Washington held both, which allowed it to talk to other missions as well as to Tokyo (NSA, “Red and Purple”). Parker adds that “when maintenance was required on the new equipment, a Japanese embassy frequently reverted to the Type A machine” (Parker, p. 23).

Two consequences followed. First, the same message was often sent in both systems, to posts that held different machines; a message read in RED gave the plaintext of its PURPLE twin, a perfect crib. Second, the habits of the RED operators — message numbers at the start, stereotyped openings — carried over to the new machine. By 10 April 1939, Parker records, Rowlett and Robert Ferner had produced partial PURPLE texts “based on similarities between the A and B systems.” On 1 May 1939 the Japanese, apparently recognising the risk, introduced complications to the keying that slowed recovery again.

3.9 What RED Left Behind

RED’s legacy to its successor was a single design choice and a single analytical habit.

The design choice was the six-and-twenty split. Its tariff justification had disappeared in 1934, yet the Type B kept it. Freeman, Sullivan and Weierud, considering why, offer the simplest explanation: “the designer or designers did not recognize this division as a critical weakness” (FSW, p. 14). For SIS it was “a ready-made wedge”. The techniques that had isolated RED’s sixes isolated PURPLE’s within weeks; by April 1939 the sixes of most PURPLE messages could be deciphered (CQ, p. 68). The twenty-letter part took another seventeen months.

The analytical habit was the assumption that a cipher machine was a rotor machine. Everything SIS had studied — Hebern, Kryha, Hagelin, RED itself — had a cyclic mechanism of some kind, and the analysts went looking for one in PURPLE’s twenties. The Quarterly is blunt: “One reason that the solution of Purple was so difficult was that the analysts had assumed that Purple was a rotor machine, like Red. In fact Purple was a uni-selector machine” (CQ, p. 71). A rotor’s successive alphabets are related to each other by the rotor’s own wiring shifted one place; a stepping switch’s 25 alphabets are related by nothing at all. Volume 4 opens that machine.

---

Next — Volume 4: Inside the Type 97 — Sixes, Twenties and Stepping Switches. The telephone part at the heart of PURPLE, the four switches that do the enciphering, the rule that decides which of them steps, and one letter of the Pearl Harbor message traced wire by wire through the machine.