<<

. 2
( 16)



>>

matrices whose columns are formed by the plaintext p i and ciphertext ci,
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

<<

. 2
( 16)



>>