Reference / Paper · 2003
Reconstruction of the Japanese Type B (PURPLE) cipher machine: sixes and twenties wiring, stepping, a simulator, and the 14-part message of 6–7 December 1941 worked through. Cryptologia 27(1).
PURPLE Revealed: Simulation and Computer-aided Cryptanalysis of Angooki Taipu B Wes Freeman,1 Geoff Sullivan 2 and Frode Weierud 3 ADDRESSES: (1) 2527 Mardell Way, Mt View CA 94043 USA. Email: [email protected]; (2) 64 Tennyson Road, Headless Cross, Redditch, Worcs., B97 5BJ UNITED KINGDOM. Email: [email protected]; (3) Le Pre Vert, 1041 Rte de Mategnin, F-01280 Prevessin-Moens FRANCE. Email: [email protected] ABSTRACT: PURPLE was the designation given by U.S. cryptanalysts to the cipher machine used by the Japanese Foreign Office for secure communications before and during WW 2. We present the structure and internal wiring of the machine, as well as details of the keying procedures and a system of abbreviations, which was used in the messages. We have also written a computer simulation of the PURPLE machine. Operation of the simulator is demonstrated by deciphering portions of the 14-part message delivered to the United States on Dec. 7, 1941. Finally, an automated cryptanalysis method for the PURPLE system is presented. KEYWORDS: Pearl Harbor, PURPLE, RED, Rowlett, Stepping Switch, Computer Simulations, Hill Climbing, Roma-ji, Romazi. Introduction On December 6, 1941, the Japanese Government sent a message, which was divided for transmission into 14 parts (the 14-part message), to its embassy in Washington. An accompanying message directed that the 14-part message be delivered to the United States Government on December 7 at 1:00 p.m., which corresponded to 7:30 a.m. at Pearl Harbor, Hawaii. The 14-part message, which broke off negotiations between Japan and the United States, was enciphered on the PURPLE machine. The 97-shiki-obun In-ji-ki (Cipher Machine 97) was also referred to as Angooki Taipu B by the Japanese. When cryptanalysis of the PURPLE machine began, the American cryptanalysts also referred to it as the “B Machine.” However, it did not seem prudent to use the Japanese designation so a ‘cover name’ of PURPLE was adopted [5, p. 142]. The allied cryptanalytical services also used trigram designators, so-called short titles, for the various cryptographic systems Page 1 of 40 pages under study. PURPLE was given the short title JAA, with the sub-designations JAA-1 and JAA-2 for variants of the PURPLE keying method. The operation of the PURPLE machine has been described in detail in [1–3]. Therefore, only a general overview of the machine will be presented, as well as specific details regarding the internal wiring of the machine. The PURPLE machine was a substitution device, which replaced each plaintext letter with a ciphertext letter (or vice versa) from a permuted or ‘scrambled’ alphabet. The alphabet permutation changed after each letter was enciphered or deciphered, producing a polyalphabetic substitution system. Input and output to the PURPLE machine was provided by two conventional electric typewriters. Messages to be enciphered or deciphered on the PURPLE machine were entered on the keyboard of the input typewriter and the resulting ciphertext or plaintext was printed on the output typewriter. The primary cryptographic element of the PURPLE machine is a 25 position stepping switch (also known as a stepping relay or uniselector). This device connects an input terminal to one of 25 output terminals. An electro-magnet, attached to the switch, advances the switch to its next position (e.g. from output 1 to output 2) in response to an electrical pulse. When the magnet is properly connected to the electric typewriter circuit, the stepping switch will advance to the next consecutive position each time a key on the typewriter is pressed. After reaching position 25, the next pulse will return the switch to position 1. The stepping switch was originally developed in response to a need to automate the routing of telephone calls. An early U.S. patent (No. 447,918) for a stepping switch was granted to Almon B. Strowger on March 10,1891. This device, with one input connected to the originating telephone, selected one of ten levels of switches, and then one of ten contacts on the selected level. This Strowger switch could, therefore, route a telephone call to one of 100 possible receivers. Over time, Strowger switches were developed with a wide variety in the number of levels and the number of contacts per level. One model, which is important to the discussion of the PURPLE machine, had six levels of switches and 25 contacts per level. Each level had a separate input, so that six inputs could simultaneously be connected to one of 25 outputs. Figure 1 shows a similar switch with eight levels and 25 contacts. Page 2 of 40 pages Figure 1. Two views of an eight level, 25 position stepping switch, showing the electromagnet that advances the switch. This particular example includes a second electromagnet which steps the switch in the reverse direction, but this feature was not required for the PURPLE machine. For the purposes of this discussion, it is important to understand that the internal components of the PURPLE machine which we present are actually the components that were used in the U.S. Army Signal Intelligence Service (SIS) recreation, or analog, of the original machine. The SIS cryptanalysts never actually saw the Japanese machine, and, as far as has been revealed in the literature, only a few parts of one machine were ever recovered at the end of World War 2. Block Diagram A simplified wiring diagram of the PURPLE cryptographic unit is shown in Figure 2 1. The cryptographic elements are an input plugboard, stepping switches to permute the text, and an output plugboard. The design of the PURPLE machine is such that the input and output pluggings can be unrelated. However, Japanese 2 practice was to have the plugging sequences identical or related . In fact, the ‘PURPLE ANALOG No. 1’ on display in the U.S. National Cryptologic Museum at Ft. Meade, MD, has only one physical plugboard (only one plugboard is required 1 Adapted from: NARA. RG457. NSA Historical Cryptographic Collection. Schematic Drawings for the PURPLE Machine. NR. 3204, Box 1017. The original drawing labels the twenties switches as “Special Sel” and the sixes switch “Master-6,” and implies the plugboard shown in Figure 3. 2 NARA. RG457. NSA Historical Cryptographic Collection. Tentative List of Enigma and other Machine Usages. NR. 1417, Box 580 Page 3 of 40 pages if the plugboard connections are identical and double-contact jacks and plugs are used). Figure 2. Simplified wiring diagram of the PURPLE deciphering unit. As can be seen from Figure 2, the 26 alphabetic characters (A-Z) are divided into one group of six and another group of twenty characters. These two groups are designated the sixes and the twenties, respectively, and represent the English vowels (AEIOUY) and consonants (BCDFGHJKLMNPQRSTVWXZ). However, the PURPLE machine did not specifically encipher vowels as vowels and consonants as consonants. (Further information on this arrangement will be presented later, in the “Regarding the 6-20 Alphabet Division” section.) The input jacks of the sixes portion of the plugboard are connected to the inputs of a six-level, 25 position stepping switch. The outputs of the switch are wired so as to permute (or rearrange) the input letters. As the switch advances through its 25 positions, the output is 25 scrambled alphabets (out of a possible 6!, or 720 alphabets). Unlike a rotor machine such as the ENIGMA, the 25 alphabets of the sixes are completely unrelated. The input jacks of the twenties portion of the plugboard are connected to the inputs of a 20-level, 25 position stepping switch. As with the sixes, this switch is wired to produce 25 unrelated alphabets. However, the outputs of the first Page 4 of 40 pages twenties switch are connected to a second switch and then in turn to a third switch. As will be shown shortly, the result is a twenties cycle of 25 x 25 x 25, or 15,625. Each twenties switch was actually constructed from four of the six-level switches, since 20-level, 25 position switches were not available. All four sections moved as one. The sixes switch included a second six-level section which also moved in parallel. The second section of the sixes switch controlled the stepping of the twenties switches and also the lamps which indicated the switch position. The outputs of the stepping switches, either sixes or twenties #1, are connected to the output plugboard. This plugboard is then connected to an output typewriter, where the plaintext or ciphertext is printed. It is important to note that during encipherment or decipherment any sixes letter was only replaced by itself or another sixes letter. Similarly, twenties letters were only substituted among themselves. This feature was very important in the cryptanalysis of PURPLE, as will be shown in the ”Regarding the 6-20 Alphabet Division” section of this paper. The simplified diagram of Figure 2 shows a plugboard wherein two sets of jacks are located on the PURPLE analog machine itself. Individual patch cords or jumper wires would then be used to make the plugboard connections. Another possible arrangement is shown in Figure 3, where individual wires from the typewriter are inserted into one set of jacks in the PURPLE machine. Either method will produce a correct result, and it is impossible to know which system the Japanese used. Figure 3 also supplies more detail of the connections between the input typewriter, the plugboard, and the stepping switches. Any letter coming from the typewriter (i.e. on the left side of the diagram) can be connected to any input of the PURPLE machine (on the right). Therefore, pressing a key on the typewriter may result in that letter being enciphered either through the sixes switch or through the twenties switches. Selecting the alphabet permutation is covered in “The PURPLE Keying System” section of this paper. Page 5 of 40 pages Input Electric Current from Plugboard Input Typewriter To Stepping Switches of PURPLE Machine Typewriter Letter A A Sixes Switch Level 1 Typewriter Letter E E Sixes Switch Level 2 Typewriter Letter I I Sixes Switch Level 3 Typewriter Letter O O Sixes Switch Level 4 Typewriter Letter U U Sixes Switch Level 5 Typewriter Letter Y Y Sixes Switch Level 6 Typewriter Letter B B Twenties Switch #3 Level 1 Typewriter Letter C C Twenties Switch #3 Level 2 Typewriter Letter D D Twenties Switch #3 Level 3 Typewriter Letter F F Twenties Switch #3 Level 4 Typewriter Letter G G Twenties Switch #3 Level 5 ... ... Z Twenties Switch #3 Level 20 ... Typewriter Letter Z Figure 3. Wiring of the PURPLE machine’s input plugboard. As an example, if the “B” wire from the typewriter is plugged into the “E” input of the machine, then the letter “B” will be enciphered by level 2 of the sixes switch. If “B” is plugged into the “F” input, on the other hand, then “B” will be enciphered on level 4 of the twenties switches. Notice that the plugboard connections shown above are alphabetic, while the stepping switch connections (Level 1 etc.) are numeric. This nomenclature follows the SIS convention shown in the switch wiring tables (Figures 6-9). Assigning numbers instead of letters to the switches is a logical choice because the plugboard allows any letter to replace any other letter. The physical layout of the Japanese plugboard is unknown, since no machine was ever recovered. Whatever the physical layout was, however, the wiring of the plugboards of the Japanese machine and the SIS analog were different [7, p. 2-1A]. The respective electrical (not physical) layouts of the plugboards were: Japanese A O B F J M Q T X E U C G K N R V Z I Y D H L P S W SIS Analog A O C L J V Q Z G E U F T K X W B D I Y R S N P M H Because of the difference in plugboard layouts, the Japanese plugboard alphabet sequence (which is part of the daily PURPLE key) must be modified for use with the SIS analog machine. This operation is a simple substitution (for Page 6 of 40 pages example, the letter in the ‘V’ position of the Japanese alphabet would be plugged into the ‘B’ socket of the SIS analog). In this paper, we will use the SIS alphabet. Figure 2 shows the input typewriter connected to Switch #3 while the output 3 typewriter is connected to Switch #1 . These are the correct connections for deciphering a normal PURPLE message. The input and output connections would be reversed when enciphering the message. However, messages could also be enciphered in ‘reverse’ mode (i.e. enciphered in decipher mode and vice versa). Not shown in Figure 2 is the wiring of the switches, which required almost 2,000 wired connections. The sixes switch has six levels with 25 output contacts per level. The wiring table for the sixes switch is shown in Figure 6, where the top row denotes the input connection and each of the succeeding 25 rows denotes the permutation output at that switch position. For each of the 25 output levels, all of the “1” outputs of the switch must be connected together. The same rule applies to outputs 2 through 6. Then each group of outputs at each level must be wired together. With six levels and 25 contacts, this requires a total of 150 wires. Figure 4 shows the wiring of level 5 of the sixes switch and gives an example of the wiring complexity. The remaining levels of the sixes switch would show similar complexity. The twenties switches have 20 inputs and 25 positions, which requires 500 wires for each of the three switches. The result was what has been described as a “rat’s nest” of wiring surrounding each switch [2, p. 232]. To understand the operation of the PURPLE machine, consider the circuit of Figure 4 with electric typewriters connected to the input and output. When a key on the input typewriter is pressed, for example “K,” an electric current is applied to the “K” input of the plugboard. Depending on the plugboard substitution, “K” may be changed to one of the sixes, such as “U.” Since “U” is the fifth vowel, the typewriter current will be applied to level 5 of the sixes switch. If the sixes switch is in position 3, then Figure 6 tells us that input 5 is connected to output 2 (which then connects to “E”). Next the output plugboard connects “E” to some other letter, perhaps “S,” and finally the current causes an “S” to be printed on the output typewriter. 3 The U.S. Army Signal Intelligence Service (SIS) cryptographers numbered the switches as #3, #2, and #1, while the Japanese order was #1, #2, and #3. This would not have been obvious from cryptanalysis, but was only discovered because the Japanese occasionally sent new switch settings in messages, which were themselves enciphered, in the PURPLE system. Hereafter the SIS numbering will be used. Page 7 of 40 pages Figure 4. The electrical path through the PURPLE analog for a sixes letter. If the plugboard converts the input letter to one of the twenties letters, the operation of the machine is similar but more complicated. The input typewriter current must pass through Switch #3, then Switch #2 and finally Switch #1 before proceeding through the output plugboard and on to the output typewriter. After each letter is enciphered or deciphered, the sixes switch and one of the twenties switches will move to the next position and create a new permutation. The result is a polyalphabetic system with a period of 25 for six letters and 15,625 for the remaining twenty letters. The path through the PURPLE machine is therefore dependent on the switch permutations, the switch movement, and the alphabet plugboard substitution. A specific example of deciphering an actual message will be presented in the “Deciphering a PURPLE Message” section. First, however, the switch wiring and movement portions of the cryptographic system will be examined in more detail. Switch Wiring Tables The wiring of the PURPLE switches is shown in Figures 6 through 9 [7, pp. A5-2, A4-4–7]. Each column represents one level of the stepping switch and each row is the permutation of the inputs at that position. For example, an electric current applied to the input of level 1 would appear at output 2 when the sixes switch is in position 1 and at output 6 at position 2. As previously mentioned, the switch inputs are connected to the alphabet plugboard, so input 1 of the sixes switch, Page 8 of 40 pages Figure 6, is connected to plugboard letter A, input 2 to E, etc. For twenties switch #3, Figure 9, input 1 connects to B, etc. One interesting feature of the switch wiring is that position 20 of Switch #1 is the identity permutation (1=1, 2=2, etc.). This cannot be a statistical anomaly since, as will be shown shortly, the switch wiring appears to be carefully chosen. One possibility is that this position was part of a test function of some sort, although no combination of switches #2 and #3 produce a corresponding identity permutation. Another feature which should be noted is the balanced distribution of multipleletter connections in the switches. For example the sixes switch has six inputs but 25 outputs, so each input must go to more than one output. Looking at column 1 of Figure 6, we find that input 1 is connected to output 1 at positions 3, 15, 19 and 22. Input 1 is also connected to outputs 2 through 5 at four positions, but is connected five times to output 6 (at positions 2, 7, 17, 21 and 23). Examining the remaining columns of Figure 6 reveals that each input level is connected to one output level five times, and that each output level has five connections once. A chart of the connections for the sixes, Figure 5, makes the wiring symmetry more obvious. Note that each row and each column contains exactly one position with five output connections. Input Level 1 2 3 4 5 6 Output 1 4 5 4 4 4 4 Number of Connections to Each Output Output 2 Output 3 Output 4 Output 5 4 4 4 4 4 4 4 4 4 4 5 4 5 4 4 4 4 4 4 5 4 5 4 4 Output 6 5 4 4 4 4 4 Figure 5. The grouping of output connections for the sixes switch. The twenties switches have 20 inputs but 25 outputs, and they show similar regularity. Looking at Figure 7, for example, we find on twenties switch #1 that input 1 is connected to output 17 at positions 3 and 9 and to output 16 at positions 7 and 23. Outputs 1, 5 and 12 are also “doubled.” For all three of the twenties switches, every input is connected to every output at least once, and every input is connected to two outputs exactly five times. Furthermore, output 17 of switch #1 has doubled connections at inputs 1, 6, 9, 17 and 18. Again, every output of every twenties switch has exactly five doubled connections. As previously mentioned, the PURPLE machine will operate in either the ‘normal’ or ‘reverse’ mode. It should be noted, however, that the switch connections shown in Figures 6 through 9 are for the decipher mode. For enciphering Page 9 of 40 pages messages with the switch tables, the reciprocal of each position must be used. For example, at position 2 the connections for the sixes switch for enciphering would read 5, 4, 2, 6, 3, 1 instead of 6, 3, 5, 2, 1, 4. Switch Sixes switch input (1=A, 2=E, etc.) Position 1 2 3 4 5 6 1 2 1 3 5 4 6 2 6 3 5 2 1 4 3 1 5 4 6 2 3 4 4 3 2 1 6 5 5 3 6 1 4 5 2 6 2 1 6 5 3 4 7 6 5 4 2 1 3 8 3 6 1 4 5 2 9 5 4 2 6 3 1 10 4 5 3 2 1 6 11 2 1 4 5 6 3 12 5 4 6 3 2 1 13 3 1 2 6 4 5 14 4 2 5 1 3 6 15 1 6 2 3 5 4 16 5 4 3 6 1 2 17 6 2 5 3 4 1 18 2 3 4 1 5 6 19 1 2 3 5 6 4 20 3 1 6 4 2 5 21 6 5 1 2 4 3 22 1 3 6 4 2 5 23 6 4 5 1 3 2 24 4 6 1 2 5 3 25 5 2 4 3 6 1 Figure 6. Sixes stepping switch - Decipher mode. Page 10 of 40 pages Switch Twenties Switch #1 Input (1=B, 2=C, 3=D, 4=F, etc.) Position 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 6 19 14 1 10 4 2 7 13 9 8 16 3 18 15 11 5 12 20 17 2 4 5 16 17 14 1 20 15 3 8 18 11 12 13 10 19 2 6 9 7 3 17 1 13 6 15 11 19 12 16 18 10 3 7 14 8 20 4 9 2 5 4 3 14 20 4 6 16 8 19 2 12 17 9 5 1 11 10 7 13 15 18 5 19 6 8 20 13 5 18 4 10 3 16 15 14 12 7 2 17 11 1 9 6 2 11 9 14 7 19 6 3 18 13 12 8 10 15 16 17 20 4 5 1 7 16 7 6 18 9 10 13 1 17 2 5 4 11 19 20 14 8 15 3 12 8 1 20 7 16 12 14 5 18 15 10 13 6 8 3 4 9 11 17 19 2 9 17 9 11 8 20 18 7 14 1 16 15 5 19 2 6 12 4 10 13 3 10 12 8 17 9 3 20 4 10 14 5 7 18 2 16 13 6 1 19 15 11 11 20 1 16 11 2 17 9 4 8 15 10 13 3 18 14 5 6 7 12 19 12 5 4 15 2 13 19 6 16 12 14 8 7 17 10 18 3 9 1 11 20 13 15 17 10 19 16 2 11 8 9 7 3 14 18 13 12 1 5 20 6 4 14 11 12 7 3 8 15 16 6 4 20 2 5 1 9 19 18 10 14 17 13 15 12 16 2 7 4 8 15 19 5 1 11 9 20 17 6 14 13 3 18 10 16 8 15 18 1 12 11 17 14 20 16 13 19 9 7 3 4 2 5 10 6 17 7 3 5 18 17 13 19 20 14 11 9 10 2 6 1 15 12 16 4 8 18 10 13 4 14 18 3 2 17 11 19 20 1 6 12 9 7 15 8 5 16 19 13 7 9 12 20 16 14 10 19 6 1 2 11 4 5 3 18 17 8 15 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 9 20 12 5 10 17 1 13 7 15 4 3 16 8 18 11 19 2 14 6 22 18 15 2 13 1 7 10 5 19 17 6 20 9 11 12 8 3 4 16 14 23 16 18 19 10 11 20 5 9 1 4 12 13 7 6 17 2 14 15 3 8 24 5 8 1 15 19 9 12 2 6 3 14 17 4 20 16 13 18 10 7 11 25 14 10 4 8 9 12 3 11 17 20 19 6 15 5 2 18 16 7 1 13 Figure 7. Twenties stepping switch #1 - Decipher mode. Page 11 of 40 pages Switch Twenties Switch #2 Input (1=B, 2=C, 3=D, 4=F, etc.) Position 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 15 9 1 5 17 19 3 2 10 8 11 18 12 16 6 13 20 4 14 7 2 12 6 15 2 4 9 8 16 19 17 5 11 20 7 10 18 1 14 13 3 3 4 18 5 8 16 1 12 15 20 14 13 17 11 2 7 9 6 3 10 19 4 6 11 2 20 14 7 18 12 15 3 8 5 10 1 17 19 9 16 4 13 5 7 2 13 3 9 4 17 14 1 12 18 20 6 11 16 15 5 8 19 10 6 5 17 14 7 10 9 19 20 8 13 1 2 16 3 4 12 11 18 6 15 7 8 4 3 11 19 13 2 9 12 16 10 17 14 15 20 6 18 1 7 5 8 20 1 16 10 15 8 14 11 18 5 3 7 13 17 19 4 2 9 12 6 9 9 8 7 15 5 2 4 13 17 1 11 6 19 18 14 10 3 20 16 12 10 10 12 11 18 8 16 20 17 5 6 9 3 4 19 13 7 1 14 15 2 11 11 7 14 4 18 20 6 1 13 19 12 15 5 9 16 2 17 10 8 3 12 2 3 9 10 13 14 15 16 7 11 20 12 18 6 1 5 8 17 19 4 13 16 10 15 1 17 3 13 9 4 7 6 8 2 14 5 11 12 19 18 20 14 19 16 18 12 3 13 9 10 6 2 17 14 11 4 7 20 15 5 1 8 15 18 14 12 19 1 7 10 6 11 15 5 9 8 20 17 4 3 13 2 16 16 20 3 19 2 4 5 11 14 9 10 18 16 15 12 8 7 13 6 17 1 17 3 6 4 14 2 12 16 5 18 20 7 19 1 15 9 8 10 11 13 17 18 5 15 20 9 10 17 1 19 13 12 4 2 7 6 11 14 16 8 3 18 19 14 20 13 17 5 18 8 4 2 15 16 1 9 19 3 6 7 10 12 11 20 8 11 1 6 19 14 5 18 17 3 10 13 12 20 15 16 4 2 7 9 21 17 19 6 1 12 15 20 7 16 9 3 11 13 10 2 18 8 4 5 14 22 1 5 12 20 6 11 14 8 9 7 19 4 3 13 10 17 18 16 15 2 23 16 8 10 13 11 6 19 5 3 4 15 20 17 2 18 1 14 7 9 12 24 19 13 8 16 20 10 7 1 2 18 14 6 9 5 12 3 17 15 11 4 25 13 1 17 15 7 4 16 3 14 5 2 10 18 8 11 9 19 12 20 6 Figure 8. Twenties stepping switch #2 - Decipher mode. Page 12 of 40 pages Switch Twenties Switch #3 Input (1=B, 2=C, 3=D, 4=F, etc.) Position 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 7 19 11 3 20 1 10 6 16 12 17 13 8 9 4 18 5 14 15 2 2 15 17 14 2 12 13 8 3 1 19 9 4 10 7 11 20 16 6 18 5 3 2 11 20 12 1 19 4 10 9 14 6 15 13 3 7 16 18 8 5 17 4 16 3 12 9 4 20 6 19 18 2 5 8 14 11 10 1 15 17 13 7 5 12 18 16 4 9 3 15 13 6 20 8 2 7 10 5 19 14 1 17 11 6 13 9 5 6 8 7 12 17 14 18 20 10 2 19 11 15 4 3 1 16 7 4 7 2 15 17 10 19 5 8 16 1 12 3 13 6 14 20 9 11 18 8 9 6 4 10 18 16 8 14 5 12 17 1 20 15 13 19 2 11 7 3 9 5 14 18 17 13 15 11 12 7 8 3 6 1 2 20 4 9 10 16 19 10 11 16 9 18 3 12 5 15 10 1 14 17 2 4 19 6 8 7 13 20 11 19 8 3 15 14 5 1 11 2 10 12 16 18 20 17 7 13 4 9 6 12 1 12 17 13 9 7 14 2 15 4 5 11 6 16 3 8 18 19 20 10 13 3 4 10 12 1 18 2 8 14 13 19 7 16 6 15 9 17 20 5 11 14 9 11 6 5 10 4 17 19 13 15 7 2 12 18 14 20 1 16 8 3 15 8 13 14 16 19 12 20 7 10 3 15 9 4 17 1 11 5 2 6 18 16 18 16 15 4 2 17 13 12 6 11 20 19 14 5 9 1 8 7 3 10 17 14 1 7 20 6 13 16 18 12 9 4 17 5 11 2 3 10 15 19 8 18 17 19 1 11 7 2 18 4 3 8 10 5 15 12 16 9 6 13 20 14 19 10 15 2 14 11 6 7 1 16 20 13 3 9 8 18 17 19 5 12 4 20 20 9 8 6 12 11 2 5 4 7 16 14 17 3 15 10 13 19 18 1 21 11 20 13 8 16 10 18 14 19 6 15 4 1 17 7 5 3 9 2 12 22 16 5 10 19 4 18 15 17 1 3 2 20 11 6 8 13 7 12 14 9 23 6 10 19 16 5 9 1 20 17 4 11 18 7 14 13 2 12 8 3 15 24 8 7 5 1 15 14 9 16 11 17 18 6 19 20 3 12 4 2 10 13 25 13 2 17 7 14 8 3 9 20 5 16 10 6 1 12 15 11 18 4 19 Figure 9. Twenties stepping switch #3 - Decipher mode. Page 13 of 40 pages Regarding the 6-20 Alphabet Division Dividing the alphabet into vowels and consonants was carried over from PURPLE’s predecessor, Angooki Taipu A or the RED machine. When first introduced, the RED machine enciphered vowels (A, E, I, O, U, and Y) as vowels and consonants as consonants [5, p. 115]. The ciphertext thus produced was ‘pronounceable’ under the telegraphic rules in force at the time, and this was important because random text telegrams were charged twice as much as plain language or ‘pronounceable’ (but nonsense) text. For example, Boris Hagelin patented (U.S. Patent 1,484,477) a machine (CRYPTOCODE-TYPER, Model A 4), which would convert numeric code groups (for example “7342589016”) into ‘pronounceable’ letter groups (such as “olavuxutip”) [4, pp. 341–344]. The Japanese would have certainly been aware of this device, since they had purchased other cryptographic devices from Hagelin. However, the RED and PURPLE machines were entirely different in their cryptographic operation. RED utilized the Damm ‘half rotor’ with 26 contacts for slip rings on the shaft. These contacts were split into two groups of 20 and 6 contacts. These contacts were connected to a rotor of 60 positions (the least common multiple of 20 and 6) at the end of the shaft. A pinwheel controlled the movement of the rotor, advancing one, two, or three positions for each letter enciphered and with a variable period of 41 to 43 positions [2, pp. 218, 219]. Since the operating principles of the RED and PURPLE machines are entirely different, it is difficult to speculate on why the 6-20 division was maintained. The simplest explanation is that the designer or designers did not recognize this division as a critical weakness. Especially when vowels are only enciphered as vowels, as happened when RED was first introduced, the effect is startling. The distribution of vowels in Romanized Japanese language includes many bigrams, such as OO, UU, AI and IA, and even trigrams such as YUU and YOO [5, p. 117]. These combinations made it possible for cryptanalysts to guess at plaintext words and thereby recreate the operating principles of the machine. The Japanese abandoned the vowel/consonant division a few months after the introduction of the RED machine, and thereafter any of the 26 letters could be plugged into the sixes [5, p. 123]. It seems logical to assume that Japanese cryptographers realized that mapping vowels to vowels reduced the security of the machine. Unfortunately, the damage was already done because SIS cryptographers had the earlier messages and used them to establish the operating principles of the machine. The new keying procedure simply meant that SIS had to develop methods to separate the sixes and the twenties. This was accomplished by analyzing the letter frequencies and noting that the sixes usually had a higher or lower frequency of occurrence than the twenties. With the Page 14 of 40 pages decryption process established and the alphabets recovered, RED was deciphered continuously by SIS until the machine was removed from service in 1941. RED messages were also deciphered by the British, Germans, and Russians. [3, p. 82] Although the operating principles of RED and PURPLE were entirely different, the 6-20 division gave SIS cryptographers a ready-made wedge into cryptanalysis of the PURPLE machine. Using the techniques already developed for RED, the sixes of PURPLE messages were identified and the encryption algorithm was revealed. Japanese messages in the RED system typically began with a message number. The U.S. Army’s SIS kept careful records of these numbers, which gave them many ciphertext-plaintext pairs. The same numbering system was continued with the PURPLE machine, and this provided enough data to enable the recovery of the system for enciphering the sixes [5, p. 146]. With the sixes recovered, the underlying plaintext of some messages could be identified. Eventually enough plain text was recovered to reveal the switch motion and wiring of the twenties and the PURPLE machine was solved. Switch Motion The motion of the sixes switch is straightforward, advancing one position after each letter is enciphered. When the sixes switch reaches position 25, the next letter enciphered will return the sixes switch to position 1. However, the position of the sixes switch does control the movement of the twenties switches. For the twenties, one switch moves after each letter is enciphered. A ‘fast’ switch advances one position after each letter is enciphered, unless the sixes switch has reached the 25 position. In this case, the ‘middle’ switch advances while the ‘fast’ switch does not. If the ‘middle’ switch has also reached the 25 position, then the ‘slow’ switch will advance when the sixes reaches 24, followed (on the next encipherment) by the ‘middle’ switch. An example of the switch motion when the slow switch moves is shown in Figure 10. Page 15 of 40 pages Sixes 21 22 23 24 25 1 2 Switch Positions Twenties #1 Twenties #2 Twenties #3 1 25 5 2 25 5 3 25 5 4 25 5 4 25 6 4 1 6 5 1 6 Figure 10. Turnover of the twenties switches is controlled by the sixes switch. Note that only one twenties switch moves with each letter enciphered. For this example, the motion is: #1 is fast, #2 is middle, and #3 is slow. Since only one of the twenties switches moves with each letter enciphered, 25 x 25 x 25 letters can be enciphered before the cycle will repeat. Any of the three twenties switches can be the fast, middle or slow position, giving six possible switch movements. The Stepping Switch as a Cryptographic Element PURPLE and its naval cousins, CORAL and JADE, were unique in that they were the first, and perhaps the only, known cryptographs to use stepping switches to permute the plaintext. One feature of the stepping switch as a cryptographic element is that the alphabets which the switch produces are totally unrelated. This was a new concept for the SIS cryptographers. Frank Rowlett, Solomon Kullback and others had, under the direction of William F. Friedman, studied a variety of cryptographic machines, such as the Hebern, KRYHA, and Hagelin [5, ch. 6]. Rowlett and Kullback had even solved the RED machine in a ciphertextonly attack. All of these machines, however, had a cyclic operation of some sort. PURPLE’s sixes were solved fairly quickly, since there were only 25 permutations, but no exploitable pattern could be identified for the twenties. The output of the PURPLE machine is cyclical, of course, but Japanese keying methods, combined with the complexity of the machine, conspired to hide the patterns. Some plaintext could be identified through the deciphered sixes, such as English language messages that had been delivered to the United States State Department. Although the Japanese initially used only 120 different switch starting positions (out of 15,625), they did use a different alphabet every day. This ensured that very few messages would be sent with exactly the same key (additional information on keying methods is presented in The PURPLE Keying System section of this paper). Without matching cipher and plain text, in depth, Page 16 of 40 pages the motion and wiring connections of the twenties switches could not be established. The PURPLE machine has six switch motions, which affect the cryptographic process in two different ways [2, p. 239]. All six possible motions of the twenties switches are shown in Figure 11. The designations of the Motion Indicators, 1 through 6 in the left hand column, are those used by SIS to set the motion on their PURPLE analog machines. The switch motion, e.g. 132, is given in fast, middle and slow notation (i.e. Switch #1 is fast, Switch #3 is middle and Switch #2 is slow). The first two lines of each motion indicator are the consecutive decipherments of each of the twenties letters (i.e. only the fast switch has advanced one position). The third and fourth lines of each indicator are the identical letter encipherments except that they also include one step of the middle switch. The deciphered letters only represent the permutation of the twenties switches, since the plugboard was plugged ‘straight through’ (i.e. B=B, C=C, etc.). Motion indicators 1, 2, and 4 show that the columns are permuted as the middle switch turns (in motion 1, for example, the letters “Q” and “D” under input B are moved to column Z when Switch #2 advances). Indicators 3, 5, and 6 show isomorphic substitutions (for motion 5, “D” exactly replaces “Q” when switch #1 advances). Even though the effects of the motion are either permutation or isomorphism, however, each of the six possible switch motions produces its own unique output. Page 17 of 40 pages Motion Switch Positions Input to Twenties Indicator #1 #2 #3 Motion B C D F G H J K L M N P Q R S T V W X Z 1 1 24 6 123 Q Y V L H C F G M S B P D K W T N J Z R D G J K F Z B C R M V H P W Q N Y S L T 2 24 6 P W C B R N L Z J T F M H V Y K S G D Q 1 25 6 H Q Z V T Y K L S N B R F J G W M C P D 2 25 6 2 1 2 1 2 24 24 24 24 6 6 7 7 132 Q Y V L H C F G M S B P D K W T N J Z R D G J K F Z B C R M V H P W Q N Y S L T N C D T G P K V H R Z F J Q L M B Y W S Y Z P N C H W J F T L B S D K R V G Q M 3 1 1 2 2 24 25 24 25 6 6 6 6 213 Q Y V L H C F G M S B P D K W T N J Z R P W C B R N L Z J T F M H V Y K S G D Q D G J K F Z B C R M V H P W Q N Y S L T H Q Z V T Y K L S N B R F J G W M C P D 4 1 1 1 1 24 25 24 25 6 6 7 7 231 Q Y V L H C F G M S B P D K W T N J Z R P W C B R N L Z J T F M H V Y K S G D Q N C D T G P K V H R Z F J Q L M B Y W S S N H K Z M V C R Q D L G P B J F W Y T 5 1 1 2 2 24 24 24 24 6 7 6 7 312 Q Y V L H C F G M S B P D K W T N J Z R N C D T G P K V H R Z F J Q L M B Y W S D G J K F Z B C R M V H P W Q N Y S L T Y Z P N C H W J F T L B S D K R V G Q M 6 1 1 1 1 24 24 25 25 6 7 6 7 321 Q Y V L H C F G M S B P D K W T N J Z R N C D T G P K V H R Z F J Q L M B Y W S P W C B R N L Z J T F M H V Y K S G D Q S N H K Z M V C R Q D L G P B J F W Y T Figure 11. Permutations of the twenties letters for all switch motions. One feature of PURPLE which is ignored in Figure 11 is the effect of the sixes switch. As mentioned previously, the middle switch will advance when the sixes switch advances from 25 to 1, while the fast switch does not move. Figure 12 shows a decipherment matrix for the twenties letters before, during, and after the sixes switch passes position 25. As can be seen from Figure 12 at positions 4 and 30, an unrelated alphabet is inserted after each 25 letters are deciphered. If the slow switch also moves, then two unrelated alphabets will be inserted. Page 18 of 40 pages Switches # of Letters Input to Twenties Sixes #1 #2 #3 Enciphered B C D E F G J K L M N O P R S U V W Y Z P C D W N S T J F G B K R Z V H L Q X M 22 1 12 6 1 X B G R Q D J T W Z V C L P F M H S N K 23 1 13 6 2 K F R D L Q W S B M J X N H G C T P Z V 24 1 14 6 3 J K H C F L Q R V D N S W X M G Z T P B 25 1 15 6 4 Z L W G R S X H F B P Q T J C V N K M D 1 1 15 7 5 X K R J D L G B W C V N Z S M T H Q P F 2 1 16 7 6 W N F Q L V D X M J R Z B H T S G P C K 3 1 17 7 7 22 23 24 25 1 2 3 4 1 1 1 1 1 1 1 1 11 12 13 14 14 15 16 17 7 7 7 7 8 8 8 8 26 27 28 29 30 31 32 33 B F C N G Z J P H X K S W M V Q R D T L L S R H J K Z D N M X T Q P W F B C V G H D L M T C P G Q K N J S X R W V B F Z T Q N C S X H R L V Z W P K D B J F G M F D T X M V L B R W S Z J C K H N G Q P K C Z S D B F V H Q R P N G J X W M L T Q M X L F C W T B N D V H J S G R P K Z P T W V K J M S X Z L R G Q H D F C N B Figure 12. Cipher alphabets of the twenties as the middle switch advances. Note one random alphabet after every 25 characters. The appearance of the unrelated alphabet in Figure 12 is evidence of an interesting feature of PURPLE. An examination of all of the switch wiring tables reveals that no input is connected to the same output at two successive positions, even at the ‘roll over’ from position 25 to 1. Since only one switch moves at a time, the PURPLE machine will never encipher the same plaintext letter to the same ciphertext letter twice in succession. Unlike some other machines such as the Enigma, however, PURPLE will encipher a plaintext letter to the same ciphertext letter. The PURPLE Keying System PURPLE messages utilize a 2-part key. The first part of the key provides the switch starting positions and movement, while the second part of the key defines the daily alphabet. The switch settings were determined by a 5-digit indicator group at the beginning of each message. Initially, the indicator was selected from a list of 120 4. Sixty of the indicators had all odd numbers (e.g. 73159), while the remaining 60 had all 4 See Appendix A. This is not the original Japanese document. The indicators were recovered by cryptanalysis. Page 19 of 40 pages even numbers (e.g. 60284). By 1 May 1942, an additional 120 indicator groups, including both odd and even numbers, had been added [7, pp. A2-A-4, A2-A-5] To resist cryptanalysis, it is desirable that messages not be produced ‘in depth.’ Since PURPLE is a hard-wired machine, the number of starting positions must be limited in order to prevent overlaps when sending long messages. On the other hand, limiting the starting positions increases the chances that two or more messages will be sent with the same settings. To disguise the limited number of starting positions, the message indicator was enciphered by adding (with carry) a predetermined five-digit number. This additive was changed monthly. For example, PURPLE messages sent in November, 1941 used an additive of 82313; December, 1941 messages used an additive of 03210. The indicator of the 14-part message was further disguised by first transposing the true indicator and then applying the additive group. For example, part 1 of the 14-part message was enciphered with the switch settings corresponding to indicator 15739. This indicator was enciphered as follows: Message indicator Digit sequence 15739 ABCDE Transposition sequence Transposed indicator BEDAC 59317 December additive Encrypted indicator 03210 62527 It should be noted that not all PURPLE messages used the 240 starting positions mentioned previously. Certain highly sensitive messages, sent between Tokyo and Berlin, carried the external designation HIKAL. The HIKAL messages derived their switch starting positions from the original list of 120, but modified the normal starting positions (for example by reading the switch positions down a column instead of across the row). HIKAL messages were also read by SIS, either by cryptanalysis or because the keying instructions were transmitted in PURPLE messages that were broken. U.S. codebreakers often recorded the switch positions and movement using the format a-b,c,d-ef, where a is the starting position of the sixes switch, b, c, and d are the twenties switches #1, #2, and #3 respectively, e is the fast switch and f is the middle switch. For example, the indicator for part 1 of the 14-part message would have been written: 9-1,24,6-23. Another format for recording the indicator was a-b-c-d-n, where n represents one of the six possible switch motion indicators given in Figure 11. For this second case, the part 1 indicator would be 9-1-24-6-4, where 4 represents switch motion 231. Page 20 of 40 pages The PURPLE daily alphabets were derived from a list of 1,000 basic alphabets, which was arranged as 50 pages with 20 lines per page 5. On any given day, all messages were enciphered using the same basic alphabet. However, the alphabet was permuted before being used 6. There were several methods of selecting the alphabet, and these methods changed over time, but the method employed during December 1941 was as follows: 1. Add the month and day to get