respectively. Then A P = C and if it is the case that gcd(det(P),26) = 1,

the matrix P-™ (mod 26) exists. If the inverse matrix exists, Trudy can

compute P-l and from P-™ she can determine A via A = C P - l . Once

Trudy finds A , the decryption matrix A-™ is easily calculated.

The Hill cipher is an example of a linear cipher. The linearity of the Hill

cipher effectively creates a large number of substitutions, which is desirable.

However, the linear structure can be exploited, since linear equations are easy

to solve. The lesson here is that a cipher must have some nonlinear compo-

nent. However, linear components are useful and, in fact, modern ciphers

combine both linearit,y and nonlinearity. In Shannon™s terminology [ 1331, lin-

earity provides an effective method to increase diffusion while nonlinearity is

essential for confusion.

CLASSIC CIPHERS

18

One-Time Pad

1.4.3

I 1 1917, Gilbert Vernam and Joseph Mauborgne invented a cipher system

1

which would eventually become known as the one-time pad. When correctly

used, this system is invulnerable to a ciphertext only attack. This is the only

real-world cipher that is provably secure.

Suppose Alice wants to send a message to Bob and she wants to encrypt

her message using a one-time pad. Alice first converts her plaintext message P

into binary. She then generates a random binary key K of the same length

as P . Encryption is accomplished by adding K to P , bit by bit, modulo 2,

to obtain the ciphertext C. That is, C = P @ K , where “@” is XOR.

To recover the plaintext P from the ciphertext C, Bob, knowing the key K ,

computes C @ K = ( P @ K ) @ K = P . For example, suppose P = 01001100

and K = 11010110. Then

c = P CB K = 01001100 CE 11010110 = 10011010

and P can be recovered from C via

P = c @ K = 10011010 CB 11010110 = 01001100.

The one-time pad is immune to a ciphertext only attack, since the ci-

phertext yields no information about the plaintext, other than its length. To

see why this is true, consider the eight-letter alphabet in Table 1.8, with the

given binary encodings.

N

T 0 E

Letter G

D

A

C

101 110 111

000 001 010 100 011

Binary

The plaintext message CAT is encoded as 000 001 010. Suppose the

key K = 110 100 001 is used for encryption. Then the ciphertext is given

by C = 110 101 111 which corresponds to EGN. Now, suppose Trudy inter-

cepts C and she guesses the putative key K™ = 010 110 010. Using K™, Trudy

computes the putative plaintext

c 69 K™ = 110 101 111 @ 010 110 010 = 100 011 101

P™ =

which corresponds to the message DOG. Based on the ciphertext and the pu-

tative plaintext, Trudy has no way to judge whether the message DOG is any

more likely than the message CAT, or any other three letter message that car1

be spelled from the eight letters in Table 1.8. That is, “decrypting” C with

any one of the possible 83 = 512 keys gives one of the 512 possible plaintext

messages and the ciphertext itself gives no hint as to which of these is correct.

1.4 SELECTED CLASSIC CRYPT0 TOPICS 19

The “one-time” in the one-time pad is crucial. If a key K is used more

than once, then the one-time pad (which is, technically, no longer a one-time

pad) is subject to an attack. Different messages encrypted with the same key

are said to be in depth.

Suppose that plaintext messages Po and PI are in depth, that is, both

are encrypted with a one-time pad using the same key I(, yielding cipher-

texts Co and C1, respectively. Then if Trudy obtains both ciphertexts, she

can compute

that is, Trudy can obtain the XOR of the two plaintexts. It might then

be possible for Trudy to “peel apart” these two messages, depending on the

properties of the plaintext. The fundamental issue here is that the attacker

can, in effect, use one of the messages as a check on any guess for the other

message (or the key). Consequently, the ciphertext now provides information

about the underlying plaintext and the security can no longer be assured.

The problem only gets worse (or, from Trudy™s perspective, better) the more

the one-time pad is reused.

An obvious practical problem with the one-time pad is that a key having

the same length as the plaintext must be securely transmitted to the recipient,

and this key can only be used once. If the key can be securely distributed,

why not send the message by the same means, in which case there is no need

to encrypt?

However, it is important to note that there are some cases where a one-

time pad is practical. In some situations it may be easy to send the key at

a particular time, and then use it at a later time when it would be difficult

or impossible to communicate securely. For example, in the 1930s and 1940s,

the Soviet Union used a one-time pad cipher to t,ransmit intelligence gathered

from spies in the United States. Soviet agents would simply bring their one-

time pads with them when entering the United States, then use these to en-

crypt sensitive messages as necessary. In fact, these one-time pads were often

used more than once and, as a result, many of the messages were eventually

broken by United States cryptanalysts. The famous Project VENONA [151]

details this impressive cryptanalytic success. The VENONA decrypts pro-

vide tremendous insight into Soviet spying in general, and nuclear espionage

in particular.

Modern stream ciphers are a generalization of the one-time pad, where

provable security is traded for practicality. In a stream cipher a short secret

key is “stretched” into a long pseudo-random string of bits, which is then used

just like a one-time pad. The provable security is lost since the number of

possible keys is much smaller than the number of possible messages. Stream

ciphers are discussed in Chapter 3.

CLASSIC C1PHER.S

20

1.4.4 Codebook Ciphers

Finally, we discuss codebook ciphers, which are, literally, books filled with

“codes”. In a classic codebook cipher, there are two books, one of which has

the plaintext words (or phrases) listed in alphabetical order, each of which

is adjacent to its corresponding codeword. A particular word or phrase is

encrypted by looking it up in the codebook and replacing it with the appro-

priate codeword. A corresponding codebook indexed by codewords is used to

decrypt. For example, Table 1.9 contains an excerpt from a famous (encryp-

tion) codebook of World War I. In fact, this excerpt is froni the codebook

that was used to encrypt the infamous Zimmermann Telegram [149]. In this

particular codebook, the plaintext consists of German words and the cipher-

text consists of 5-digit numbers. The inverse codebook, where the words are

indexed by the Corresponding 5-digit codewords, would be used to decrypt.

Table 1.9: Excerpt from World War I German Codebook

plaintext ciphertext

13605

Februar

13732

f est

13850

finanzielle

13918

f olgender

17142

Frieden

17149

Friedenschluss

The security of a classic codebook cipher depends heavily on the physical

security of the book itself. That is, the book must be protected from capture

by the enemy. In addition, statistical attacks such as those described above

for the simple substitution cipher apply equally to codebooks, although the

arnount of data required to attack a codebook would be much larger. This

is due to the fact that the size of the “alphabet” is larger for a codebook,

arid consequently much more data must be collected before the statistical

information can rise above the noise.

As late its World War 11, codebooks were in widespread use. Cryptogra-

pliers realized that these ciphers were subject to statistical attack, so code-

books were regularly replaced with new codebooks. Since this was an expen-

sive and risky process, it was necessary to extend the life of a codebook as

milch as possible. To this end, an additive book was generally used.

Suppose that for a particular codebook cipher, the codewords are all 5-

digit numbers. Then the additive book would consist of a long list of randomly

generated 5-digit numbers. After a plaintext message had been converted to

1.5 SUMMARY 21

a series of 5-digit codewords, a random starting point in the additive book

would be selected, and the subsequent 5-digit additives would be added t o the

codewords to create the ciphertext. For a codebook with 5-digit codewords,

the addition would be taken modulo 100,000. In this case, the i t h ciphertext

word would be

+

Ci = F ( P i ) Aj (mod 100,000),

where F ( X ) is the result of looking up plaintext word X in the codebook, Aj

is the additive and P is the plaintext. To decrypt,

i

P

i = Fpl(Ci - Aj (mod 100,000)),

where F - l ( Y ) is the plaintext word that corresponds t o codeword Y . Note

that the additive book is required t o encrypt or decrypt a message.

Often, the starting point in the additive book was selected at random by

the sender and sent in the clear (or in a slightly obfuscated form) at the start of

the transmission. The additive information was part of the message indicator

(MI). In general, an MI includes any information (other than the key) needed

by the recipient t o decrypt the message correctly. More examples of MIS

appear in the next chapter, where we discuss World War I1 cipher machines.

Note that if the additive material were only used once, the resulting cipher

would be a one-time pad and therefore, provably secure. However, in prac-

tice, the additive was reused multiple times and, therefore, any messages sent

with overlapping additives would have their codewords “encrypted” with the

same additives. Therefore, any messages with overlapping additive sequences

could be used t o gather the statistical information needed to attack the un-

derlying codebook. In effect, the additive book simply increased the amount

of ciphertext required t o mount a statistical attack on the codebook, which

is precisely the effect, the cryptographers hoped t o achieve.

Modern block ciphers are, in a sense, the descendants of classic codebook

ciphers. In addition, the concept of an additive also lives on, in the form of

a so-called initialization vector (IV), which is often used with block ciphers

(and sometimes with stream ciphers as well). The use of IVs in block ciphers

is discussed in detail in Chapter 4.

Summary

1.5

In this chapter, we introduced the basic terminology used in the remaining

chapters, and we gave an overview of a few selected classical cryptosystems.

These classic systems illustrate many of the important concepts seen in later

chapters where we analyze modern ciphers.

We also considered various aspects of elementary cryptanalysis. Specifi-

cally, we mentioned attacks based on each of the following:

CLASSIC CIF™I‚¬ER.S

22

Exhaustive key search

0

Divide and conquer

0

Statistical weaknesses.

0

Linearity of the underlying cipher.

These same crypt analytic principles appear in various forms throughout the

subsequent chapters of this book.

The remaining chapters are primarily focused on case studies illustrating

thc cryptadysis of specific real-world ciphers. In the next chapter we dis-

cuss the cryptanalysis of the three most famous cipher machines from World

War 11. Then we turn our &tention to modern ciphers, including examples

of stream ciphers, block ciphers, hash functions and public key systems. All

of these attacks are “applied” in the sense that they are realistic attacks that

can be used t o break the security of real ciphers.

Problems

1.6

1. Many companies use proprietary cryptosystems. Google to find a spe-

cific example of a company that has violated Kerckhoffs™ Principle.

2. Edgar Allan Poe™s 1843 short story. “The Gold Bug,” features a crypt-

analytic attack. What type of cipher is broken and how?

3 . Solve the following congruence: 19, (mod 26).

=3

4. Fill in the missing steps in the derivation of the formula for the index

of coincidence in (1.2).

5. Consider the ciphertext QJKES REOGH GXXRE OXEO, which was gener-

atcd using an affine cipher. Recover the decryption function and de-

ciplicr the message. Hint: Plaintext T encrypts to ciphertext H and

plaintext 0 encrypts to ciphertext E.

6. Decrypt the ciphertext

TNFOS FOZSW PZLOC GQAOZ WAGQR PJZPN ABCZP QDOGR AMTHA

RAXTB AGZJO GMTHA RAVAP ZW.

Hint: This is from a simple substitution cipher and the word “liberty”

appears in the plaintext.

7. Cryptanalyze the following message, which is from a Vigenkre cipher

with a :<-letter English keyword:

CTMYR DOIBS RESRR RIJYR EBYLD IYMLC CYQXS RRMLQ FSDXF

OWFKT CYJRR IQZSM X.

1.6 PROBLEMS 23

8. Write a comput,er program to calculate the index of coincidence for an

English ciphertext. Compute the index of coincidence for the ciphertext

in (1.1).

9. Using the result of Problem 8, compute k in (1.4) for the ciphertext

in (1.1).

10. Write a computer program to approximate the key length for a VigenGre

ciphertext. Verify your program on the ciphertext in (1.1).

11. The following ciphertext is from a columnar transposition cipher:

TSEHVAIESSRYIYQ.

Find the corresponding plaintext.

12. The following ciphertext is from a double transposition cipher, where

the encryption matrix is 10 x 11:

TNOSSKAIMAGAEITMHETHTSRHXXIHEUXDX

NUEIDSATDTDDSARAHHENTTTDSOUIOEART

FHDAOMWYWFERTNEONFDYAHSEIMEDGRWTA

TISURUARTHJ .

Find the corresponding plaintext.

13. Verify the derivation of (1.4), which can be used to find the number of

letters in the keyword of a Vigenkre cipher.

14. Consider the Hill cipher with matrix A as given in (1.5).

a. Find A-™ (mod 26).

b. Using the result of part a, decrypt the ciphertext EWXJEWYTKZ and

verify that the corresponding plaintext is MEETMEHERE.

c. Using the same A matrix as in part a, decrypt the ciphertext

QCNDVUHLKGANIYVUWEGMWTNHHXXD.

15. Consider a onetime pad using the letter encodings in Table 1.8. Sup-

pose that Trudy intercepts C = 110 101 111.

a. Find a putative key K™ such that the corresponding putative plain-

text P™ yields the word GET.

b. Find anot,her putative key K” such that the corresponding putative

plaintext is TAG.

CLASSIC CIPHERS

24

16. Using the codebook excerpt in Table 1.9 and the additive sequence

188,900, A1 = 92,331, A2 = 23,546

A0

encrypt and decrypt the plaintext message

folgender Frieden Februar.

Assume that the additive arithmetic is taken modulo 100,000. Show all

intermediate steps.

17. Consider two ciphers, Cipher A and Cipher B, and suppose that Ci-

pher A has a 64-bit key, while Cipher B has a 128-bit key. Alice prefers

Cipher A, while Bob wants the additional security provided by a 128-bit

key, so he insists on Cipher B. As a compromise, Alice proposes that

they use Cipher A, but they encrypt each message twice, using two in-

dependent 64-bit keys. Assuming that no shortcut attack is ava.ilable

for either cipher, is Alice™s approach sound?

Chapter 2

World War I1 Ciphers

. . .obstacles do not exist to be surrendered to, but only to be broken.

- Adolf Hitler, Mein Kampf

Introduction

2.1

In the previous chapter, we covered a few classic “pen and paper” cipher

systems. In this chapter we discuss the three most famous World War I1

era cipher machines. We first consider the German Enigma and we present

enough cryptanalysis to illustrate a serious weakness in the cipher. Then

comes the Japanese Purple cipher and its cryptanalysis. Finally, we con-

sider the American Sigaba machine which was never broken during its service

lifetime. We present an attack on Sigaba that would have been impractical

using WWII technology, but nicely illustrates the strong points of the cipher

as compared to the Enigma and Purple.

It is important to remember that World War I1 was the first significant

use of cryptographic machines. This was necessitated by the vast increase

in the volume of communication required for modern, highly mobile military

operations. Prior to WWII, most military cipher systems were codebooks,

with additives used to increase the amount of data required to successfully

recover the codebook. Obviously, the security of a codebook depends on the

physical security of the book itself. With the advent of machine cryptosys-

tems, much more ciphertext was available to the cryptanalyst, which changed

the nature of the threat considerably. With a cipher machine, physical se-

curity of the machine was almost irrelevant in comparison to the statistical

properties of the cipher itself. However, the developers and users of these

early machine systems failed to fully grasp the changed nature of the threat,

since their thinking was grounded in the earlier codebook era. Consequently,

they tended to overemphasize the importance of the physical security of the

25

WORLD WARI I CIPHERS

26

machine, as opposed to the stat)istical security of the ciphertext, as discussed

in some detail in [ 2 3 ] . We return to this theme a t the end of the chapter after

we have analyzed the most famous cipher machines of the war.

While there are many sources of information on WWII ciphers, much of

the information is unreliable. Among the best sources are [23, 291.

Enigma

2.2

It 1na.y well be doubted whether human ingenuity can construct an enigma.. .

which human ingenuity may not, by proper application. resolve.

Edgar Allen Poe. The Gold Bug

˜

The Enigma cipher was used by Germany prior to and throughout World

War 11. The forerunner of the military Enigma machine was originally devel-

oped by Arthur Scherbius as a commercial device. The Enigma was patented

in the 1920s but it continued to evolve over time. However, all versions of

the Enigma a,re “rotor” machines, and they share certain additional common

features.

The German military eventually become interested in the Enigma and, af-

ter further modifications, it became the primary cipher syst,em for all bmnches

of the German military. The German government also used the Enigma

for diplomatic communications. It is estimated that approximately 100,000

Enigma machines were constructed, about 40,000 of those during World

War 11. The version of Enigma that we describe here was used by the German

military throughout World War I1 [47].

The Enigma was broken by the Allies, and the intelligence it provided

was invaluable--as evidence by its cover name, ULTRA.The Germans had an

unwavering belief in the security of the Enigma, and they continued to use it

for vital communications long after there were clear indications that it had

been compromised. Although it, is impossible to precisely quantify the effect

of Enigma decrypts on the outcome of t.he war, it is not. farfekhed t.o suggest™

that the intelligence provided by Enigma decrypts may have shortened the

war in Europe by a year, saving hundreds of thousands of lives.

Enigma Cipher Machine

2.2.1

An Enigma cipher machine appears in Figurr 2.1. where the keyboard

essentially, a mechanical typewriter arid “light board” are visible. The front

˜

panel consists of cables plugged into what appears to be an old-fashioned

telephone switchboard. This switchboard (or plugboard) is known by its

German name, stecker. There are also three rotors visible near the top of the

machine.

2.2 ENIGMA 27

Figure 2.1: Enigma cipher [46].

Before encrypting a message, the operator had to initialize the device. The

initial settings include various rotor settings and the stecker cable pluggings.

These initial settings constitute the key.

Once the machine had been initialized, the message was typed on the

keyboard, and the as each plaintext letter was typed, the corresponding ci-

phertext letter was illuminated on the lightboard. The ciphertext letters

were written down as they appeared on the lightboard, to be subsequently

transmitted, typically by radio.

To decrypt, the recipient™s Enigma had to be initialize in exactly the same

way as the sender™s. Then when the ciphertext was typed into the keyboard,

the corresponding plaintext letters would appear on the lightboard.

The cryptographically significant components of the Enigma are illus-

trated in Figure 2.2. These components and the way that they interact are

described below.

To encrypt, a plaintext letter is entered on the keyboard. This letter first

passes through the stecker, then, in turn, through each of the three rotors,

through the reflector, back through each of the three rotors, back through

the stecker, and, finally, the resulting ciphertext letter is illuminated on the

lightboard. Each rotor-as well as the reflector-consists of a hard-wired

permutation of the 26 letters. Rotors as cryptographic elements are discussed

in detail in Section 2.2.3.

In the example illustrated in Figure 2 . 2 , the plaintext letter C is typed on

the keyboard, which is mapped to S due to the st,ecker cable connecting C to S.

The letter S then passes through the rotors, the reflector, and back through

the rotors. The net effect of all the rotors and the reflector is a permutation

of the alphabet. In the example in Figure 2.2, S has been permuted to Z,

which then becomes L due to the stecker cable between L and Z. Finally, the

WOR,LDWARI 1 CIPHERS

28

rotors

J 4I

ref lector

Figure 2.2: Enigma diagram [142]

letter L is illuminated on the lightboard.

We use the following notation for the various permutations in the Enigma:

R, = rightrnost rotor

R,, = middle rotor

Re = leftmost rotor

T = reflector

S = stecker.

If plaintext letter encrypts to ciphertext letter y, from Figure 2.2, we have

LC

=S-˜R-IR-˜R-˜

e TRFR,RTS(X)

m

T

( R! R, R, s) T (R!R, R ˜ () .

s X) (2.1)

= -

If that is all there were to the Enigma, it would be nothing more than a

glorified siniple substitution (or mono-alphabetic substitution) cipher, with

the initial settings determining the permutation. However, each time a key-

board letter is typed, the rightmost rotor steps one position, and the other

rotors step in an odometer-like fashion --almost [26, 631 .l That is, the middle

˜The “alniost” is due to the mechanical system used to step the rotors, which causes the

iriiddle rotor to occasioriitlly step twice in succession. Whenever a rotor steps, it causes the

rot,or to its right to also step. Suppose that the rniddle rotor just stepped to the position

that engages the ratchet, rnech;tnisrn that will cause the leftniost rotor to step when the next

letter is typed. Then when the next, letter is typed, the left rotor will step, and this will also

2.2 ENIGMA 29

rotor steps once for each 26 steps of the right rotor and the left rotor steps

once for each 26 steps of the middle rotor. The reflector can be viewed as

a fixed rotor since it permutes the letters, but it does not rotate. The net

effect is that the overall permutation changes with each letter typed. Due to

the odometer effect, the permutations R,, R,, and Re vary with time, but T

and S do not.

Figure 2.3 illustrates the stepping of a single Engima rotor. This example

shows the direction that the rotors step. Note that to the operator, the letters

appear in alphabetical order.

a R

S

R step step,

T

S

U

T

v

U

-˜

Figure 2.3: Enigma rotor.

The Enigma is a substitution cipher where each letter is encrypted based

on a permutation of the alphabet. But the Enigma is far from simple since

whenever a letter is encrypted (or decrypted), the permutation changes. That

is, the Enigma is a poly-alphabetic substitution cipher, with an enormous

number of possible alphabets.

Enigma Keyspace

2.2.2

The cryptographically significant components of the Enigma cipher are the

stecker, the three rotors, and the reflector. The Enigma key consists of the

configuration of the cipher used to encrypt and decrypt a particular message.

The variable settings that comprise the key are the following:

1. The choice of rotors.

2. The position of a movable ring on each of the two rightmost rotors.

This ring allows the outer part of the rotor (labeled with the 26 letters)

to rotate with respect to the inner part of the ring (where the actual

permutation is wired).2 Rotating this ring shifts the permutation and

cause the middle rotor to step again. The middle rotor thereby steps twice in succession,

violating the odometer effect. Note that this same ratcheting mechanism causes the right

rotor to step whenever the middle rotor steps, but since the right rotor already steps for

each letter typed, there is no noticeable effect on the right rotor.

'This is analogous to rotating the position of a car tire relative to the rim.

WORLD WARI I CIPHERS

30

the point at which the odometer effect occurs relative to the letters on

the rotors.

3 . The initial position of each rotor

4. The number and plugging of the wires in the stecker.

5. The choice of reflector

As mentioned above, each rotor implements a permutation of the 26 letters

of the alphabet. The movable rings can be set t,o any of the 26 positions

corresponding to the letters.

Each rotor is initially set to one of the 26 positions on the rotor, which are

labeled with A through Z. The stecker is similar to an old-fashioned telephone

switchboard, with 26 holes, each labeled with a letter of the alphabet. The

stecker can have from 0 to 13 cables, where each cable connects a pair of

letters. The reflector implements a permutation of the 26 letters, with the

restriction that no letter can be permuted to itself, since this would cause a

short circuit. Consequently, the reflector is equivalent to a stecker with 13

cables.

Since there are three rotors, each containing a permutation of the 26

lettcrs, there are

26! . 26! . 26! M 2265

ways to select and place rotors in the machine. In addition, the number of

ways to set the two movable rings--which determine when the odometer-like

effects occurs-is 26 . 26 M 2™.*.

The initial position of each of these rotors can be set to any one of 26

positions. so there are 26.26.26 = 214.1ways to initialize the rotors. However,

this mimber should not be included in our count, since the different initial

positions are all equivalent to some other rotor in some standard position.

That is, if we assume that each rotor is initially set to, say, A then setting a

particular rotor to, say, B is equivalent to some other rotor initially set to A.

Consequently, the factor of 2265 obtained in the previous paragraph includes

all rotors in all possible init™ial positions.

Finally, we must consider the stecker. Let, F ( p ) be the number of ways to

plug p cables in the stecker. From Problem 2, we have

The values of F ( p ) are tabulated in Table 2.1.

™

Summing the entries in Table 2.1, we find that there arc more than 248

possible stecker configurations. Note that maximum occurs with 11 cables and

that F ( 1 0 ) 247 As mentioned above. the Enigma reflector is equivalent

2.2 ENIGMA 31

Table 2.1: Stecker Combinations

to a stecker with 13 cables. Consequently, there are F(13) = 242.8 different

reflectors.

Combining all of these results, we find that, in principle, the size of the

Enigma keyspace is about

. 29.4 , 248.9 , 242.8

2265

2366.

That is, the theoretical keyspace of the Enigma is equivalent to a 366 bit

key. Since modern ciphers seldom employ more than a 256 bit key, this

gives some indication as to why the Germans had such great-but ultimately

misplaced-confidence in the Enigma.

However, this astronomical number of keys is misleading. From Prob-

lem 3 , we see that under the practical limitations of actual use by the German

military, only about 277 Enigma keys were available. This is still an enormous

number and an exhaustive key search would have been out of the question

using 1940s technology. Fortunately for the civilized world, shortcut attacks

exist. But before we discuss an attack, we first take a brief detour to consider

rotors as cryptographic elements.

Rotors

2.2.3

Rotors were commonly employed in cipher machines during the first half of the

20th century. The Enigma may be the most fanlous rotor machine, but we will

see another when we discuss the Sigaba cipher. From a crypto-engineering

standpoint: the appeal of a rotor is that it is possible to generate a large

number of distinct permutations in a robust mariner from a relatively simple

electro-mechanical device. Such considerations were particularly important

in the pre-computer era. In fact, the Enigma was an extremely durable piece

of hardware, which was usable for tactical military communications.

The Japanese Purple cipher-discussed in Section 2.3-is a non-rotor

polyalphabetic cipher that was a contemporary of the Enigma. In contrast

to the Enigma, Purple was a bulky and fragile device that could never have

survived under battlefield conditions.

WORLDWARII CIPHERS

32

Hardware rotors are easy to understand, but it is slightly awkward to

rnathernatically specify the permutations that correspond to the various po-

sitions of the rotor. A good analysis of these issues can be found in [go]; here

we briefly discuss some of the main points.

For simplicity, consider a rotor with four letter, A through D. Assurning

the signa,l travels from left to right, the rotor illustrated in Figure 2.4 per-

mutes ABCD to CDBA, that is, A is permuted t o C, B is permuted to D, C is

permuted t o B and D is permuted to A. The inverse permutation, DCAB in

our notation, can be obtained by simply passing a signal through the rotors

from right-to-left instead of left-to-right. This is a useful feature, since we

can decrypt with the same hardware used to encrypt. The Enigma takes this

one step further-it is its own inverse, so that the same machine with exactly

the same settings can be used to encrypt and decrypt (see Problem 6).

Figure 2.4: Rotor.

Now suppose that the rotor in Figure 2.4 steps once. Note that only the

rotor itself-represented by the rectangle-rotates, not the electrical contacts

at the edge of t,he rotor. We assume that the rotor steps “up,” that is, the

contact that was at B is now at A and so on, with the contact that was at A

wrapping around to D. The shift of the rotor in Figure 2.4 is illustrated in

Figure 2.5. The resulting shifted permutation is CADB, which is, perhaps, not

an obvious shift of the original permutation, CDBA.

Figure 2.5: Stepped rotor.

In general, i t is not difficult to determine the rotor shift of a permutation.

The crucial point is that it is the offsets, or displacements, that shift. For

cxample, in the permutation CDBA, the letter A is permuted to C, which is an

offset of 2 positions, the letter B is permuted to D, which is an offset of 2, the

2.2 ENIGMA 33

letter C is permuted to B which is an offset of 3 (around the rotor) and D is

permuted to A which is an offset of 1, so the sequence of offsets for the per-

mutation CDBA is (2,2,3,1). Cyclically shifting this sequence yields (2,3,1,2)

which corresponds to the permutation CADB, which is the rotor shift that

appears in Figure 2.5. Problem 1 provides more details on rotor shifting.

As mentioned above, one of the primary advantages of rotors is that they

provide a simple electro-mechanical means to generate a large number of dif-

ferent permutations. Combining multiple rotors in series increases the num-

ber of permutations exponentially. For example, in Figure 2.6, C is permuted

to A, while a shift of rotor L , denoted by a ( L ) and illustrated in Figure 2.7,

causes C to be permuted to B. That is, stepping any single rotor changes the

overall permutation.

A -+

B

C

D

L M R

Figure 2.6: Three rotors.

A

B-

C

D

Figure 2.7: Rotor L steps.

With this simple three rotor scheme, we can generate a cycle of 64 permu-

tations of ABCD by stepping through the 64 settings for the three rotors. Of

course, not all of these permutations will be unique, since there are only 24

distinct permutations of the four letters ABCD. But the sequence of permu-

tations is at least as significant as the actual generated permutations. Also,

selecting different initial settings for the rotors, we can generate a dfferent

sequence of permutations, and by selecting a different set of rotors, we can

generate different sequences of permutations. As with a single rotor, it is easy

to obtain the inverse permutations from a series of rotors by simply passing

WORLD WARI I CIPHERS

34

the signal through the rotors in the opposite direction. Of course, the inverse

permutations are needed for decryption.

Enigma Attack

2.2.4

Polish cryptanalysts led by Marian Rejewski, Henryk Zygalski, and Jerzy

R6iycki were the first to successfully attack the Engima; see [148] for a good

discussion of the details of their attack. Their challenge was greatly compli-

cated by the fact that they did not know the rotors in use. Through some

clever mathematics, and a small, but crucial, piece of espionage [a],they were

able to recover the rotor permutation from ciphertext. This certainly ranks

as one of the greatest cryptanalytic successes of the entire war.

When Poland fell to the Nazis in 1939, Rejewski, Zygalski and R6zycki

fled to France. After France fell under the Nazi onslaught the Poles auda-

ciously continued their cryptanalytic work from unoccupied Vichy France.

The brilliant cryptanalytic work of Rejewski™s team eventually made its way

to Britain, where the British were rightly amazed. A group of British crypt-

analysts that included Gordon Welchman and computing pioneer Ala,n Turing

took up the Enigma challenge.

The Enigma attack that we describe here is similar to one developed by

Turing, but much simplified. Our attack--which relies on known plaintext--is

easily implemerited on a modern computer, but would have been impractical

using WWII technology. The essential idea is that, initially, we can ignore

the stecker and make a guess for the remainder of the key. From Problem 3,

there are less than 230 such guesses. For each of these, we use information

derived from known plaintext (a “crib” in WWII terminology) to eliminate

incorrect guesses. In the process, the stecker is only a minor nuisa.nce and,

in fact? when we complete the attack, we will have recovered most-if riot

all--of the stecker scttings as well.

Suppose that for a given ciphertext, we know the plaintext arid corre-

sponding ciphertext in Table 2.2. We make use of this data in the attack

described below.

i 0 1 2 3 4 5 6 7 8 9 1011121314151617181920212223

Plaintext 0 B E R K 0 M M A N D 0 D E R W E H R M A C H T

Ciphertext Z M G E R F E W M L K M T A W X T S W V U I N Z

Let S(z) be the effect of the stecker when a letter J™ passes through tjhe

stecker from the keyboard. Then Spl(ll:) the effect of the stecker when 11:

is

passes through the stecker in the other direction. For a given initial setting,

2.2 ENIGMA 35

let Pi be the permutation at step i, that is, Pi is the permutation determined

by the composition of the three rotors, followed by the reflector, followed by

the three rotors-in the opposite direction--at step i. Using the notation

in (2.1), we obtain

s-˜R,˜R,˜R˜˜TR˜R,R,s,

F, =

where, to simplify the notation, we ignore the dependence of Re, R,, and R,r

on i.

Pcl

Since Pi is a permutation, its inverse, exists. Due to the rotation of

the rotors, the permutation varies with each letter typed. Consequently, Pi

does indeed depend on i.

The Enigma attack we present here exploit,s “cycles“ that occur in the

known plaintext and corresponding ciphertext. Consider, for example, the

column labeled “8” in Table 2.2. The plaintext letter A passes through the

stecker, then through P and, finally, through S-™ to yield the ciphertext M,

g

that is, S - l P g s ( A ) = M which we can rewrite as P g S ( A ) = S(M). Then from

the known plaintext in Table 2.2, we have

which can be combined to yield the cycle

Suppose that we select one of the possible initial settings for the machine,

neglecting the stecker. Then all P and PtF1 that correspond to this setting

i

are known. Now suppose that we guess, say, S(E) = G , that is, we guess that E

and G are connected by a cable in the stecker plugboard. If it is actually the

case that the stecker has a wire connecting E and G, and if our guess for the

initial settings of the machine is correct, then from (2.2) we must have

If we try all 26 choices for S ( E ) and (2.2) is never satisfied, then we

know that our guess for the rotor settings is incorrect and we can eliminate

this choice. We would like to use this observation to reduce the number or

rotor settings, ideally, to just one. However, if we find any guess for S(E)

for which (2.2) holds, then we cannot rule out the current rotor settings.

Unfortunately, there are 26 possible guesses for S ( E ) and for each, there

is a 1/26 chance that (2.2) holds at random. Consequently, we obtain no

reduction in the number of possible keys from this one cycle.

WORLD WAR I I CIPHER.S

36

Fortunately, all is not lost. We can easily find an additional cycle in-

volving S ( E ) , which can then be used in combination with (2.2) to reduce

the number of possible rotor settings. For example, we can combine the four

equations

S ( E ) = P3S(R)

s(w) P 1 4 S ( R )

=

s ( W ) = P7S(M)

S ( E ) = P6;S(M)

to obtain

S ( E ) = P&'P7PC1S(E).

Now if we guess, say, S ( E ) = G, we have two equations that must hold if

this guess is correct. There are still 26 choices for S ( E ) , but with two cycles,

there is only a (1/26)2 charice that they both hold at random. Therefore,

with two cycles in S ( E ) , we can reduce the number of viable machine settings

(that is, keys) by a factor of 26. We can easily develop an attack based on

this observation. Using only two cycles, the attack is outlined in Table 2.3.

However, several additional cycles would be required to uniquely determine

the key.

Table 2.3: Enigma Attack

// Given: Cycles Co and C1 for S ( E )

// (Lo,L I , . . . , L25)= (A, B, . . . , Z)

f o r each rotor setting

Conipute required permutations to test Co and C1

f o r j = 0 to 25

S ( E ) = L,

i f Co and CI hold then

save putative rotor settings arid S ( E ) value L,

end i f

next j

next rotor setting -

To reiterate, the crucial observation here is that once we specify the rotor

settings, all permutations Po, P I ,Pl,. . . and P i 1 ,P;', P;', . . . are known.

Then if we substitute a putative value for S ( E ) , we can imniediately check the

validity of both cycle equations. For an incorrect guess of S ( E ) (or incorrect

rotor settings) there is a 1/26 chance any given cycle will hold true. But with

two cycles, there is only a ( 1/26)2 chance that both cycle equations will hold

true. Consequently, with two cycles involving S ( E ) , we can reduce the number

2.2 ENIGMA 37

of possible initial rotor settings by a factor of 26. Since there are about 230

rotor settings, after completing the “attack” in Table 2.3, we expect to have

about 230/26 M 225.3 putative rotor settings remaining.

The attack in Table 2.3 can be extended to more than two cycles, in which

case we obtain a proportionally greater reduction in the number of surviving

keys. With a sufficient number of cycles, we can uniquely identify the initial

rotor settings. In fact, with n pairs of cycles we expect to reduce the number

of possible keys by a factor of 26”. Therefore, with a sufficient number of

cycles, we can recover the key.

Amazingly, by recovering the initial rotor settings in this manner, stecker

values are also recovered-essentially for free. However, any stecker values

that do not contribute to a cycle will remain unknown, but once the rotor

settings have been determined, the remaining unknown stecker settings are

easy to determine; see Problem 9. It is interesting to note that in spite of

an enormous number of possible settings, the stecker contributes little to the

security of the Enigma.

More Secure Enigma?

2.2.5

Several of the design features of the Enigma conspired to create weaknesses

that were exploited by the Allies. For example, the fact that the right rotor

is the “fast” rotor (i.e., the right rotor steps with each letter typed) was said

to be crucial in one particular attack. If instead, the left rotor had stepped

with each letter-and the designers of the Enigma could just as easily have

chosen any of the rotors as the fast rotor--this particular attack would not

have succeeded [23].

The attack described in this section would still work, regardless of which

rotors are fast, medium, and slow. However, in spite of it being extremely

efficient by modern standards, the attack presented here would have been

impractical using 1940s technology. The practical attacks of World War I1

required that the cryptanalyst reduce the number of cases to be tested to a

small number. Many clever techniques were developed to squeeze as much

information as possible from the messages before attempting an attack. In

addition, much effort was expended finding suitable cribs (known plaintext)

since all of the practical attacks required known plaintext.

Is there any relatively simple modification to the Enigma that would pre-

vent the attack discussed in this section? We leave this as an exercise (Prob-

lem 13). It is important to note that our attack exploits the fact that the

rotors can, in a sense, be isolated from the stecker. Any modifications de-

signed to prevent this attack must take this fact into account.

WORLDWAR, 1 CIPHERS

38 1

Purple

2.3

The .Japanese Government regrets to have to

notify hereby the American Government that in view of the attitude

of the Arnerican Government it cannot hut consider that it is impossible

to reach ari agreement through further negotiations.

- From the “14-part message” [72]

The World War I1 era Japanese cipher machine Angooki Tuipu B was known

to Allied cryptanalysts as Purple--due to the color of the binders used to

hold information on the cipher. The Japanese used Purple to encrypt diplo-

matic traffic and it was in use from the late 1930s until the end of the war.

Contrary to some reports, Purple was not used to encrypt tactical Naval

commuriications-that was the role of the JN-25 cipher [ 2 3 ] . In particular, it

was JN-25 decrypts (not Purple decrypts, as is sometimes claimed [75]) that

provided the information enabling American pilots to shoot down Admiral

Yamamoto™s airplane in 1943.

Purple Cipher Machine

2.3.1

No intact Purple cipher machine was ever captured by the Allies. Figure 2.8

shows a fragment of a Purple machine that was discovered in Berlin at the

end of WWII.

Figure 2.8: Fragment of a Purple cipher machine [117]

The most, famous Purple ciphetext was the so-called 1Qpart mcssage, sent

from Tokyo to Washington on December 6, 1941, in which Japan broke off ne-

gotiations with the United States. The .Japanese ambassador was instructed

to present the message to U.S. officials at 1:OOpm (Washington time) on De-

cember 7, 1941, but due to difficulties with the decryption and translation

2.3 PURPLE 39

to English, the message was not delivered to Secretary of State Cordell Hull

until 2:30 pm. By the time Hull was handed the message, he knew of the

attack on Pearl Harbor, which had begun an hour earlier. Hull™s blistering

response to the Japanese ambassador included the following [71]:

In all my 50 years of public service I have never seen a document

that was more crowded with infamous falsehoods and distortions

. . . on a scale so huge that I never imagined until today that any

Government on this planet was capable of uttering them.

American cryptanalysts led by Frank Rowlett had previously broken Pur-

ple3 and the Americans actually decrypted the 14-part message before the

Japanese diplomats in Washington had done so. Although the message con-

tained no specific threat, it clearly represented a serious change in the status

quo. The codebreakers™ report reached General George Marshall who sent

a warning to Hawaii on the morning of December 7. However, due to vari-

ous delays, the warning did not reach the commanders in Hawaii until after

the Japanese attack was over. These events have fueled endless conspiracy

theories to the effect that political leaders in Washington knowingly let the at-

tack occur as a way to obtain public backing for war. What these conspiracy

theorists lack in fact, they more than compensate for in paranoia.

Purple is inherently weaker than Enigma. Nevertheless, the successful

cryptanalysis of Purple is sometimes regarded as the greatest cryptanalytic

triumph of World War 11. The reason for this apparent contradiction is that

while the Enigma machine was known to the Allies, the Purple machine was

not-in fact, no intact Purple cipher machine was ever recovered, before,

during, or after the war. In comparison, even the Polish cryptanalysts who

recovered the Enigma rotors by analyzing ciphertext knew the inner workings

of the device. Before Purple could be attacked, its operation first had to be

diagnosed based primarily on observed ciphertext. This remarkable diagnos-

tic effort is what people are referring to (implicitly, in many cases) when they

discuss the great cryptanalytic success in breaking Purple.

Here, we provide a complete description of the cryptographic functions

of the Purple cipher, but we do not attempt to give precise details on the

mechanical operation of the actual cipher machine that was used by the

Japanese. From the fragments of Purple machines that were found after

the war, most of the details of the machine are known. It was a complex and

intricate piece of engineering, with a “rat™s nest” of nearly 2000 wires used to

implement its various permutations. For details on the mechanical operation

of the Purple machine, see the article [52].

The Purple cipher (in encryption mode) is illustrated in Figure 2.9. When

a plaintext letter is typed on the input keyboard, it passes through a plug-

31™he intelligence garnered from Purple decrypts was given the cover name MAGIC,

which

is an indicator of its perceived value.

WORLD WARI I CIPHERS

40

board which permutes the letters. The permuted letters are then split into a

group of six letters-the “sixes”--and a group of 20 letters-the “twenties.”

Internally, the sixes consist of the vowels

(2.4)

AEIOUY,

while the twenties are the consonants

(2.5)

BCDFGHJKLMNPQRSTVWXZ.

We refer to this unusual feature of Purple as the “6-20 split.”

The input plugboard permutation enables any six letters to be connected

to the internal sixes in (2.4). If, after passing through the input plugboard,

the resulting letter is permuted to one of the sixes, it then passes through

a permutation, denoted by S in Figure 2.9, before being permuted by the

output plugboard. The resulting letter is then sent to the output device. If,

on the other hand, the plugboard permutation yields a twenties letter, the

letter passes through three permutations, denoted L , M , and R in Figure 2.9,

before being permuted by the output plugboard. Again, the resulting letter

is then sent to the output device.

As used by the Japanese, the output plugboard and input plugboard per-

mutations were always the same. In fact, the Purple simulators built by the

Allies used only a single physical plugboard, which could not have accurately

modeled Purple if the input and output permutations were different.

As can be seen in Figure 2.9, internally the sixes are permuted to sixes

and the twenties are permuted to twenties. This was a major flaw that was

carried over from a predecessor of Purple, a cipher known as Red. Why it

was carried over is not clear, since there was no inherent limitation of Purple

that necessitated such a split. In fact, two variants of Purple were used

by the Japanese (Coral and Jade) that did not employ the 6-20 split. As

discussed below, the 6-20 split was a crucial weakness that was exploited by

the cryptanalysts who broke Purple.

Each of S , L , M , and R cycle thorough a series of 25 fixed permutations,

with S stepping once for each letter typed, and exactly one of L , M , or R

stepping for each letter-which of these steps is determined by S as will be

described shortly. Each of the S permutations is a permutation of the six

vowels in (2.4), while each of t.he L , M , and R permutations is a permutation

of the twenty consonants in (2.5).

Like Enigma, Purple is a poly-alphabetic substitution cipher. However,

the mechanisms employed by the two ciphers are completely different. Re-

call that Enigma is a rotor machine, where each rotor has a single hardwired

permutation, and as a result of the rotor motion, the overall Enigma per-

mutation changes with each letter. In contrast, Purple uses switches, where

each step of a switch changes to a different permutation. That is, instead

2.3 PURPLE 41

output keyboard

input keyboard

Figure 2.9: Purple encryption.

of using permutations wired to rotors-which only requires one permutation

per rotor-each step of Purple™s S , L , M , and R “switches” t o a different,

unrelated, hardwired permutation. Consequently, we refer to S , L , M , and R

as switches and Purple as a stepping switch machine.

While the distinction between rotors and switches might seem relatively

minor, it is actually a major difference. For one thing, a stepping switch

machine like Purple is inherently more complex and difficult to engineer than

a rotor machine. From a cryptanlytic point of view, a rotor machine pro-

vides an elegant way to generate a large number of permutations, while a

comparable stepping switch machine must be far more complex. There are

also significant differences between the types of permutations that can be

generated by Purple and Enigma, as discussed below and in Problem 16.

The Purple encryption formula depending on whether the letter being

encrypted corresponds to a “six” or “twenty”. Let x be the given input

letter and let y be the corresponding output letter. Then we can denote the

encryption by

where PI is the input plugboard permutation (when going from the input

keyboard to the switches), PO is the output plugboard permutation (from

WORLD WARI I CIPHERS

42

the output keyboard to the plugboard). Note that PI and PG1 follow the

direction of the arrows in Figure 2.9. Also, PL, P ˜ Iand PR are the left,

,

middle, and right twenties permutations, respectively, and Ps is the sixes

permutation. As mentioned above, the Japanese always selected PI = PO.

A major practical difference between Purple and Enigma is that Purple

is not its own inverse (Problem 6 asks you to show that Enigma is its own

inverse). This means that decryption with Purple is more complicated than

with Enigma. Since decryption requires the inverse permutations, Purple

can be decrypted by reversing the flow through the diagram in Figure 2.9, as

illustrated in Figure 2.10. This implies that the output plugboard is used for

input and the input plugboard for output. Of course, if the plugboards have

identical permutations (as, apparently, was always the case with Purple),

then it does not matter which plugboard is used for input and which is used

for output.

output keyboard input keyboard

Figure 2.10: Purple decryption.

The decryption formula corresponding to (2.6) is

if P o ( y ) is one of the twenties

P;lPo(y)

nI

if P o ( y ) is one of the sixes.

p; p i P (Y)

O

Since the decryption formula works for any choice of PI and PO, why did

the Japanese always select PI = PO? If PI = PO, then a single plugboard

2.3 PURPLE 43

can be used. Assuming there were two physical plugboards present in Pur-

ple, perhaps it was the case that it was easy t o swap the input and output

keyboards, but not the plugboards. If so, then it would still be possible t o

decrypt when PI # Po, but the plugboards would have t o be wired with the

inverse permutations t o do so. This would have necessitated different encryp-

tion and decryption settings and, in particular, would have made it difficult

t o do trial encryptions and decryptions, which could be used t o verify the key

settings.

In contrast t o the Enigma, Purple plugboards are not necessarily their

own inverse, since the plugboards do not connect pairs of letters, as is the

case with Enigma. Instead, the Purple plugboards connect 26 letters t o 26

letters so they can implement any permutation.

Since there are 25 steps on each of the switches S, L , M , and R, each

switch has a cycle length of 25. Since exactly one of the switches L , M , or R

steps with each letter, overall, the twenties have a cycle length of 25˜25.25 =

15,625, while the sixes have a cycle length of 25. As mentioned above, the S

switch determines which of L , M , or R steps. When setting the Purple cipher,

it is necessary t o specify which of L , M and R are “fast,” “medium,” and

“slow” switches. The fact that only one of the twenties switches steps with

each letter leads t o a somewhat complicated stepping process, which we now

describe.

The specification of fast, medium, and slow switches is part of the keying

process and does not change during the encryption of a message. The sixes

switch, S , simply steps once for each letter encrypted, cycling through its 25

permutations. Exactly one of L , M , and R steps with each encryption, with

the stepping determined as follows. Number the permutations on each of the

switches 0 through 24. The fast twenties switch steps each time, except for

the following two cases:

If the sixes switch S is in position 24, then the medium switch steps.

0

If the S switch is in position 23 and the medium switch is in position 24,

0

then the slow switch steps.

The result is that the S switch and exactly one of the twenties switches step

for each letter typed, and both the S switch and the selected twenties switch

step simultaneously.

Two examples of switch stepping appear in Table 2.4, where L is the fast

twenties switch, M is the medium twenties switch, and R is the slow twenties

switch. The left-hand example in Table 2.4 illustrates the case where the

medium switch steps: while the right-hand example illustrates the stepping

of the slow switch.

Purple stepping is more complicated than the simple odometer effect em-

ployed by the Engima rotors. But the ever-so-slight advantage of the Pur-

W O R L D WARI I CIPHERS

44

Table 2.4: Medium Switch Steps and Slow Switch Steps

__ __

S

__ L M R L M R

˜ ˜

S

__

20 0 7 0

10 24 4

20

7

21 10

1 21 24 4

1

7

22 2 10 22 2 24 4

7

3 10 3

23 24 4

23

7

24 4 10 24 3 24 5

7

11

0 4 0 3 0 5

7

11

1 5 1 4 0 5

2 7

6 11 2 5 0 5

3 7 7 3

11 6 0 5

__ ˜

˜ ˜

ple stepping method is t h a t the period length of the twenties is maximized,

whereas in Enigma, the period length is reduced slightly, since more than one

rotor steps a t the rollover points. However, the additional complexity of the

Purple stepping more t h a n offsets any possible advantage due to the greater

period length.

Purple Keyspace

2.3.2

Now we consider the size of the Purple keyspace. Suppose for a moment that

the permutations on the switches were selectable. Then the Purple keyspace

would be enormous-just the selection of the S, L , M , and R permutations

would give

2237. 26628 = 26865

( 6 ! ) 2 5 . (26!)7˜5

possihlc kcys.

However, givcn the design of Purple, it was not possible t o change the

hardwired Permutations, so we compute the keyspace assuming that the per-

mutations are fixed. Under this restriction, the Purple key consists of the

following:

1. Initial settings of the switches S. L , M , and R: There are 254 2lX6

E

ways t o initialize thesc switches.

2. Choose fast, medium and slow switches from L , M , and R: Since these

can tie selected in any order, there are 6 = 22.6 combinations.

3 . Select input and output plugboard permutations: If the input and outj-

put plugboards can be chosen independently, there arc (26!)™ = 21763.8

combinations.

2.3 PURPLE 45

Therefore, the theoret,ical keyspace for Purple is approximately of size 21g8,

equivalent to a 198-bit key. However, all but a factor of 221.2 of this comes

from the plugboard settings. In fact, the Japanese always used the same

plugboard for both input and output, which immediately reduces the keyspace

to 2109.6

The Purple plugboard is a very weak cryptographic element and, conse-

quently, the effective keyspace is little more than 221. However, this presup-

poses that the switch permutations are known to the cryptanalyst, which was

not the case when Rowlett and his team began their analysis of Purple. Con-

sequently, the real cryptanalytic challenge for the Allies was to understand

the inner workings of Purple and to recover the internal permutations-all

without ever having seen the machine. Once this was accomplished, the ac-

tual decryption would not be difficult.

In fact, the Japanese only used a very small fraction of the (already small)

effective keyspace. Once the machine had been diagnosed, and a relatively

simple message indicator (MI) system had been broken, the Allies could de-

crypt messages as quickly as-and sometimes faster than-the Japanese. In

effect, maintaining the secret design of Purple was essential to maintain its

security. It is hard to imagine a more striking violation of Kerckhoffs™ Prin-

ciple. The fact that the Allies were able to break Purple without ever laying

hands on an actual machine argues strongly for the wisdom of Kerckhoffs.

In the next section we consider the diagnosis of Purple. This was the

crucial cryptanalytic challenge in breaking Purple.

Purple Diagnosis

2.3.3

No Purple cipher machine was available to Frank Rowlett, the American

cryptanalyst most closely associated with the cryptanalysis of Purple. This

meant that he first had to diagnose the machine before he could hope to break

it. That is, he had to reconstruct the inner workings of the machine using

the only available information, namely, intercepted ciphertext and knowledge

of prior Japanese cryptosystems. In some cases, known plaintext was also

available, and this would prove crucial to the diagnostic effort.

Recall that ciphertext messages are said to be in depth if they are en-

crypted using the same key. If n, messages are all encrypted with the same

key, then we refer to this as a depth of n legs. It is also possible to have

an offset depth, where the messages do not begin on the same key, but from

some point onward the messages go into depth.

Suppose that the matched plaintext and ciphertext message snippets in

Table 2.5 were generated by a cipher that uses a time-varying permutation of

the alphabet. The Enigma cipher, for example, works in this manner. Purple

is slightly more complicated due to the 6-20 split, but we ignore this issue for

now.

WORLD WARII CIPHERS

46

Table 2.5: Matched Plaintext and Ciphertext

3 4 5 6 7 8 91011

i 012

RLHA RB0RX

Plaintext P E A

Ciphertext J K F HNVPGPGPY

AT0RA T0RA

Plaintext T 0 R

Ciphertext K P L THDWV J L0P

WAYISLAND

Plaintext M I D

ESA GNK0LI

Ciphertext X H T

Furthermore, suppose the messages in Table 2.5 form a 3-legged depth.

Then the permutation at each position of the three messages is the same.

Let Pi be the ith permutation generated by this cipher for this particular

key. Then we have some information on the first several permutations. For

example, we know that Po maps plaintext P to ciphertext J , plaintext T to

ciphertext K and plaintext M to ciphertext X. Also, PI maps E to K and 0 to P,

and I to H, and so on. In this way, we can partially reconstruct the permu-

tations, and the more legs of depth that are available, the more information

on each permutation we obtain.

While it was clear to Rowlett and his team that Purple was a substi-

tution cipher, it was unclear how the permutations were generated. The

cryptanalysts had knowledge of previous Japanese cipher machines, as well

as knowledge of other cryptographic devices of the time, including rotor ma-

chines. The knowledge of an earlier Japanese cipher known as Red proved

most valuable.

The Red cipher employed an unusual split of the alphabet into sixes and

twenties, which was carried over into Purple. Initially, the Red cipher split

the alphabet into the six vowels, AEIOUY, and the remaining twenty conso-

nant. Substituting vowels for vowels and consonants for consonants was also

used in some other ciphers of the time. This split reduced the cost of ca-

bling the ciphertext messages, since the resulting messages were considered

“pronounceable”---even though the ciphertext was gibberish--and therefore

were charged a lower rate than messages consisting of random letters [52].

But encrypting vowels to vowels is a serious weakness, since some niessages

can be inferred simply based on the placement of vowels within the cipher-

text. The Japa,nese apparently realized this was a weakness and usage of the

Red cipher was modified so that any six letters could act as the sixes. This

is precisely the same situation as with Purple.

The ciphertext sixes would be expected to each occur with the average

probability of the corresponding plaintext sixes, and similarly, each cipher-

text twenties let,ter would occur with t,he average probability of the plaintext

2.3 PURPLE 47

twenties. For most random selections of six letters from the alphabet, the

selected letters will occur at either a higher or lower average frequency than

the remaining letters (see Problems 14 and 15). For example, if the plain-

text letter E is among the sixes, and the other sixes are all letters of average

frequency, then the expected frequency of each of the ciphertext sixes will be

higher than the expected frequency of each of the ciphertext twenties. There-

fore, the ciphertext sixes can usually be determined simply from a frequency

count of individual ciphertext letters. That is, the six highest-frequency or

six lowest-frequency letters are most likely the sixes. Once the sixes have

been isolated, it is relatively easy to determine the sixes permutations from

a small amount of known plaintext, since in Purple there are only 25 sixes

permutations.

Using their knowledge of the Red cipher, Rowlett™s team was quick to

realize that Purple also employed a 6-20 split. They were then able to recon-

struct the sixes permutations. But the twenties proved far more difficult to

crack.

The output permutations generated by a switch-based cipher, such as

Purple, have certain identifiable characteristics. For example, consider the

permutations in Table 2.6, which were generated by a process analogous to

that used by Purple to generate its twenties permutation. In this example,

there are three banks of permutations, as with the twenties permutations in