. 3
( 16)


Purple, but here each of the switches contains just three permutations (as
opposed to 25 for Purple), giving a cycle length of 33 = 27.

Table 2.6: Successive Permutations

5 0 6 1 3 2 4

0452 3
m2 1650 3
6 O m125 3
6 1 5230 4
6 2 1503 4
2 601 4
5 3
0 4 A510 2
5 O w641 2
2 1 3460 5
Pl 1

Consider permutations P and Ps in Table 2.6. The element in position 0
of P 4 is 4, while the 4 is in position 2 of P5. That is, the first element

of P is offset by 2 in Ps. The element in position 1 of P is a 2 and the 2
4 4
appears in position 4 of Ps, so these have an offset of 3. Continuing in this
manner, we see that. the offsets, or differences, between the elements of P 4
and the corresponding elements of Ps are ( 2 , 3 , 1 , 4 , 1 ,3,O). As explained
in Section 2.2.3, consecutive permutations from a rotor all share the same
difference sequence. The difference sequence for Ps and Ps: is different than
between P and P5, so we can be sure that these three permutations were not
generated by consecutive shifts of a single rotor.
Now if we compute the difference sequence for permutations P and PCJ,
we see that it is the same as for P and Ps. This is not coincidental. In
fact, it is consistent with these two pairs being compositions of (non-rotor)
permutations; see Problem 17. It was precisely this sort of observation that
was the crucial breakthrough in the diagnosis of Purple.
Once we realize that the permutations in Table 2.6 are conipositions of
permutations, we can solve for the individual permutations (or an equivalent
set) as follows. Most. likely, P and Ps are consecutive “fast.” permutations
with the same settings for the medium and slow permutations. Suppose the L
switch is the fast switch arid let LO be the fast permutation in P and L1
be the fast permutation in Ps. Then RiMjLo(0) = RihfjL1(2),for some i
and j , which implies that Lo(O) = L l ( 2 ) . Continuing, we can determine the
permutation L1 in terms of Lo. Using the appropriate rows from Table 2.6, we
can also determine L2 in terms of LO.Then we are free to arbitrarily select Lo,
thereby fixing L1 and L2. With the L permutations determined, we can
similarly determine the A!! permutations. Finally, when determining the R
permutations, there will be no freedom to specify one of the permutations;
see Problem 18 at the end of this chapter for more details on this particular
Is it feasible to obtain data analogous t o that in Table 2.6 for the Purple
cipher? If there happens to he a large number of messages in depth with
known plaintext, then the encryption permutations are at least partially ex-
posed by the various legs of depth, and the more legs of depth available, the
more information there is on the underlying permut,ation at each position. In
fact, this is essentially what occurred and this is what enabled Rowlctt and
his team to diagnose Purple. The American cryptanalysts had deduced the
gencral structure of Purple, but it took a large volume of messages in depth,
with known plaintext, before they could recover the actual permutations [23].
The American cryptanalysts were then able to construct machines that were
functionally equivalent to Purple--one such Purple “analog” is pictured in
Figure 2.11.
R.ecal1 thatj Polish cryptanalysts were able t o recover the Enigma rotor
wirings from ciphertext analysis. But the Poles knew how the Enigma worked,
whereas in the case of Purple, the cryptanalysts did not know the inner
workings of the machine. However! Purple is, from a cryptanalytic point
2.3 PURPLE 49

Figure 2.11: Purple analog [105].

of view, a simpler device than Enigma. We have more to say about the
comparison between Purple and Enigma in Section 2.3.5, below.

Decrypting Purple

Once Purple had been diagnosed, reading messages was relatively easy. The
Japanese restricted the number of initial switch settings to a very small num-
ber (originally, 120 and later 240), presumably, t o avoid offset depths. In
addition, only about 1000 plugboard settings were ever used. Consequently,
analysts could build a dictionary of possible settings from a relatively small
number of broken messages. However, not even this much work was required,
since the switch settings were transmitted in a message indicator (MI) that
was sent with the ciphertext. The indicators were obfuscated, but this system
was relatively easy to break. Given the extremely limited keyspace used in
practice, after a small number of successful decryptions, the Allies were able
to decrypt received messages as quickly as the Japanese. In fact, the 14-part
message was decrypted by American cryptanalysts before the Japanese had
done so.
Even if the full keyspace had been used, the Purple machine would have
been extremely weak once it had been diagnosed. There are only 6.254 M 221.2
initial switch settings. The number of plugboards, at 26! = 288.4, appears to
be daunting, but, as with the Enigma stecker, tjhis is highly misleading. As
a cryptographic element, the Purple plugboard is fundamentally flawed. As-
suming that the switch settings are correct, putative plugboard settings that
are close to the actual plugboard setting yield putative plaintext that is close
to the actual plaintext. For a well-designed modern cipher, we require that
any change to the key--no matter how minor-yields a putative decryption
that is statistically indistinguishable from that generated by a randomly se-
lected key.
In [52] a straightforward “hill climbing” attack is given that exploits the
weakness of the Purple plugboard. This attack recovers the plugboard set-
tings with a relatively small amount of work.

2.3.5 Purple versus Enigma
It is interesting to compare Enigma and Purple. Although Enigma had a
large theoretical keyspace of some 380 bits, practical issues cut this number
dmstically. In particular, due to the fact that only a small number of rotors
were available in practice, and the fact that the stecker adds little to the
security, the number of keys that a World War I1 cryptanalyst had to be
concerned with was about, 22y. However, if we implement a modern version
of the Enigma in software, then any rotor is readily available and the number
of effective keys rises to somewhere near 2'".
In contrast, the Purple design is fundamentally flawed due to the 6-20
split. Given a fair amount of known plaintext, the sixes are easily recovered,
and some messages can be read simply from knowledge of the sixes. As we
observed above, with sufficient messages in depth, it is possible to diagnose
Purple. If the switch settings were selected at random, without varying the
plugboard settings, the limited number of such settings would result in many
messages in offset depth.
It is also interesting that both the Enigma and Purple plugboards are of
virtually no cryptographic value. In spite of the huge numbers of possible
plugboard settings for each, they effectively add little to the keyspace.
The Purple permutations were not designed to be changed, and if we
maintain that restriction, this is another major weakness of the design. But
in it software version of Purple, we could easily allow the permutations to
change based on the key. This would increase the keyspace by some 265 bits,
which would put Purple roughly on par with the Enigma. However, the sixes
could still be easily recovered, which is a serious weakness.
Consider a new cipher, M a r o o ˜ iwhich eliminates the obvious weaknesses

of Purple but retains the basic design. Like Purple, Maroon is a stepping
switch cipher, with four switches, which we denote S , L , M , and R. But
unlike Purple, Maroon does not use the 6-20 alphabet split. Instead, each of
t,he permutations in the switches L , M , and R is a permutation on 26 letters.
We have also increased the number of permutations per switch from 25 to 26.
As with Purple, the S switch of Maroon steps once for each input letter,
but, since there are no sixes, the S switch is only used to determine the
stepping of the other switches. The switch stepping follows the same pattern
as in Purple. The Maroon cipher is illustrated in Figure 2.12.
Maroon was designed to be comparable to Enigma, with the essential
difference being that Maroon employs switched permutations instead of rotors
to determine the permutation. Some comparisons of Enigma and Maroon are
explored in the homework problems.
The bottom line is that, in spite of its flaws, Enigma was a much superior
4 0 ˜ Maroon cipher appears to be similar to the Japanese World War I1 ciphers known
as Jade and Coral, but precise details on these machines are somewhat sketchy.
2.3 PURPLE 51


output plugboard

input keyboard output keyboard

Figure 2.12: Maroon encryption.

design in comparison to Purple. The inherent flaw of the 6-20 alphabet split is
a major shortcoming of Purple. Also worth noting is that Enigma machines
are virtually indestructible, whereas the complexity and fragility of Purple
greatly limited its potential uses.
The diagnosis problem makes the story of Purple cryptanalytically in-
teresting. Since the cryptanlysts did not have access to a Purple machine,
they were forced to reconstruct the inner workings of the device based on
intercepted ciphertext. Certainly this ranks as a phenomenal cryptanalytic
success. Of course, the successful attacks on Enigma-first by the Poles and
then the British-also rank as amazing cryptanalytic success stories.
Comparing the diagnosis of Purple and the cryptanalysis of Enigma is
somewhat ridiculous s i n c e they are entirely different problems-but that
will not prevent us from doing so. Purple was clearly the weaker machine.
However, the internals of the machine were unknown to the American crypt-
analysts, making it extremely challenging to diagnose, even taking into ac-
count the prior knowledge of Japanese ciphers such as Red.5 On the other

˜The 6-20 alphabet split, which was carried over from Red, was the most significant
hint that was gained from previous Japanese ciphers. However, the 6-20 split would have
been relatively easy to diagnose from Purple ciphertext, even without knowledge of previ-
ous Japanese ciphers. The fact that Purple uses a stepped switch design was the crucial
observation needed to break the cipher.

hand, the inner workings of Enigma were completely known (at least to the
British), but Enigma was inherently stronger than Purple, making any suc-
cessful attack a challenging and delicate affair. So which was the greater
challenge? Take your pick -you will have solid arguments in your favor no
matter which you choose.


Remove the Cipher Unit from the machine,
withdraw the Index Maze Spindle and remove the Index Wheels.
Destroy the Index Wheels by smashing them with a heavy hammer.
- Sigaba operating instructions [ l l l ]

Sigaba was developed by American cryptographers-including Friedman and
Rowlett--prior to World War II.6 As far as is known, no successful attack on
Sigaba was every conducted during its service lifetime. During WWII, the
Germans are said to have quit collecting Sigaba intercepts since they deemed
the problem hopeless [ 2 3 ] .
In this section we first give a detailed description of the cipher. Sigaba is a
rotor machine, but its inner workings are far more complex than thc Enigma.
Then we consider the size of the Sigaba keyspace in some detail, followed
by an outline of an attack on the machine. As we describe it, the attack is
impractical-and it would have been even more so using WWII technology.
Some of the problems at the end of this chapter point to improvements in
the attack, which make it far more practical, but still beyond the realm of a
realistic WWII-era attack. This attack highlights the crucial features of the
Sigaba that make it so much more secure than Enigma or Purple.

Sigaba Cipher Machine
There were several variants of the basic Sigaba design, and to further muddy
the water, different branches of the military used different names for the same
machine. The Sigaba machine in Figure 2.13 is thought to be equivalent to the
CSP-889 (used by the Navy) and the Converter M-134C or Sigaba (different
mines, but the same device, used by the Army). In addition, the name ECM
Mark I1 wa.s used during the development of the machine that would become
Sigaba. Here, we stick with the name Sigaba.
The Sigaba cipher includes a typewriter keyboard for entering the plain-
text (or ciphertext), and a.n output device for printing t.he corresponding
'Rowlett cited the design of Sigaba as his proudest accomplishment, not the breaking
of Purple as might have been expected "231.
2.4 SIGABA 53

Figure 2.13: A Sigaba machine [105].

ciphertext (or plaintext). Like the Enigma, Sigaba is a rotor machine, but
there arc several important differences between the two. Cryptographically,
the most significant differences are that whereas Enigma uses three rotors,
Sigaba employs five rotors to permute the letters, and whereas Enigma rotors
step like an odometer, the Sigaba cipher rotor motion is controlled by a set of
ten additional rotors, for a total of 15 rotors. In effect, it is as if the motion
of the Sigaba encryption rotors is controlled by another rotor cipher machine.
This causes the Sigaba rotors to step irregularly, which is a major improve-
ment over the Enigma and other regularly stepping rotor machines. Sigaba
also lacks the Enigma™s reflector and stecker. The use of irregularly step-
ping rotors and the lack of a reflector and Enigma-like stecker make Sigaba
a stronger cipher than Enigma (the attack in Section 2.2 points to some of
the weaknesses of the Enigma design). The Sigaba rotors are illustrated in
Figure 2.14.

Figure 2.14: Sigaba rotors [126].

The fifteen Sigaba rotors consist of five cipher rotors, five control rotors,
and five in,dez rotors, where the cipher rotors permute the input letters and
the othcr two banks of rotors drive the cipher rotors. The cipher and control
rotors are interchangeable, and these rotors are also designed so they can

be inserted backwards. The cipher and control rotors each permute the 26
letters. The five index rotors each permute the numbers 0 through 9 and, of
course, the index rotors are not interchangeable with the other rotors. Unlike
the cipher and control rotors, the index rotors cannot operate in the reverse
orientation. Figure 2.15 illustrates the cryptographic components of Sigaba
in encryption mode.

input keyboard output device

Figure 2.15: Sigaba cncryption.

After a. letter is encrypted or decrypted, from one to four of the cipher ro-
tors st.cp. The nuniber and selection of the stepping cipher rotors is controlled
by thc other two banks of rotors, that is, the control and index rotors.
For each letter typed, the rightmost control rotor receives four simultanc-
ous inputs, which we assume to be F, G, H, and I. These four letters are per-
niutetl xcording to the five control rotors and the resulting four permutation-
dcpcrident output letters are combined before being input to the index rotor
bank. Let I, denote t>heinput to element j of the leftmost index rotor and A
through Z the outputs of the control rotors. Then
17 = P V
11 =
c Is= I V J V K (2.7)
12 =

where (2.7) is interpreted to mean that, for example, input 3 of the leftmost
index rotor is active if output D or E (or both) results from the control rotors;
2.4 SIGABA 55

otherwise input 3 is inactive. Note that 10 is missing, which implies that
input 0 is always inactive. Since four values are input to the control rotors,
due to the “OR” of the outputs, anywhere from one to four of the inputs to
the index rotors are active at each step.
The middle three control rotors step in an odometer-like fashion-almost.
The fast, medium, and slow control rotors are indicated by F, hl, and S,
respectively, in Figure 2.15, where the fast rotor steps with each letter, the
mcdium rotor steps once for each 26 steps of the fast rotor, and the slow
rotor steps once for each 26 steps of the medium rotor. The stepping of these
three rotors differs from an odometer only in the order of the fast, medium
and slow rotors. The initial setting of all five control rotors is adjustable, but
the leftmost and rightmost control rotors do not step during encryption or
The output of the control rotor bank enters the index rotor bank. The
index rotors do not step, but their order and initial positions are adjustable.
For a particular message, the index rotors effectively implement a simple
substitution on 0 through 9 (i.e., a fixed permutation of 0 through 9). From
one to four (inclusive) of the inputs to the index rotor bank are active, and
the number of active outputs is equal to the number of active inputs.
As mentioned above, the cipher and control rotors are interchangeable. In
addition, each of these rotors can be inserted in either of two orientations--
forward or reverse. In the reverse orientation, the letters on the cipher wheel
will appear upside down to the operator.
When a rotor is in its forward orientation, the shifting is, for example,
from 0 to N to M and so on. Figure 2.16 illustrates successive shifts of a sin-
gle Sigaba cipher (or control) rotor in its forward orientation. Note that the
direction of rotation of the Sigaba rotors is the same as that of the Enigma ro-
tors. However, the labeling on the Sigaba rotors goes in the opposite direction
as the Enigma; compare Figure 2.16 to Figure 2.3.

P 0 step
c N c


Figure 2.16: Sigaba rotor in forward orientation.

In the reverse orientation the cipher (or control) rotor shifting is from 0
to P to Q, with the letters appearing upside down on the rotors. The stepping

of a rotor in reverse orientation is illustrated in Figure 2.17. As discussed
in Section 2.2.3, implementing rotors in software requires some care, and re-
versed rotors create an additional complication (see Problem 21). Also, from
Figure 2.15 we see that the signal passes through the control rotors from
right-to-left, while, in encrypt mode, it passes through the cipher rotors from
left-to-right, which creates yet another slight complication when implement-
ing Sigaba in software.

0 d
0 tl
tl S

Figure 2.17: Sigaba rotor in reverse orientation

Curiously, the Sigaba index rotors are labeled in the opposite direction of
the cipher and control rotors. That is, the numbers increase in the downward
direction as illustrated in Figure 2.18. Since the index rotors do not step
during operation of the cipher, this is not a significant issue.


Figure 2.18: Index rotor.

An interesting quirk of Sigaba is that the letter Z is changed to X before
encrypting, and a space is changed to a Z before encrypting. If the rcsult of
dccryption is a Z,a space is output. In this way, messages can be encrypted
and decrypted with word spaces included, which makes parsing the decrypted
message easicr. The only drawback is that both plaintext X and Z will be
decrypted a.s X. For example, for some setting of Sigaba, the plaintext message


encrypts as
2.4 SIGABA 57

and this ciphertext decrypts as

where “ul™ is a word space.
We assume that the odometer effect of the middle three control rotors oc-
curs when a rotor steps from 0 to the next letter, regardless of the orientation
of the rotor. For example, if the fast rotor is at 0, then the fast and medium
rotors will both step when the next letter is typed on the k e y b ˜ a r d . ˜
The output value (or values) of the index rotors determines which of the
cipher rotors step. Let
C =00v0 9
c =0 7 V 0s

c =0 5 v 0s
C3 = 0 3 v 0 4
c =01
4 2

where Oi is the output from contact i of the index rotor bank. Then the
leftmost cipher rotor steps if Co is active, the second (from left) cipher rotor
steps if C1 is active and so on. Since there are from one to four active outputs
of the index rotors, anywhere from one to four of the cipher rotors will step
with each letter typed.
To decrypt with Sigaba, all of the rotors are initialized and stepped pre-
cisely as in encryption mode, as described above. However, the inverse cipher
rotor permutation must be used. This can be accomplished by feeding the
ciphertext letters through the cipher rotors in the opposite direction, as illus-
trated in Figure 2.19.

Sigaba Keyspace
The Sigaba key is specified by the choice of rotors and their initial positions. If
we assume that all possible rotors are available, then a different initial position
simply corresponds to a different rotor. Consequently, for the calculation of
the theoretical size of the Sigaba keyspace, we can assume that the rotors are
all set to some standard position. Then the number of keys depends only on

1. The choice of the five cipher rotors.

2. The choice of the five control rotors.

3. The choice of the five index rotors.
7Some of the details mentioned in this section were derived from studying Sigaba software
simulators, so it is possible that there are minor discrepancies with the way that an actual
Sigaba machine operates. However, none of these details appear t o have any significant
effect on the analysis or attack discussed here.

cipher rotors

index rotors

input keyboard output device

Figure 2.19: Sigaba decryption.

As with the Enigma rotors, there are 26! choices for each of the cipher and
control rotors. Similarly, there are lo! choices for each of the index rotors.
This gives a total keyspace of about
(261910. (10!)5 . 2109 2993

However, as is the case with the Enigma and Purple ciphers, the size
of the practical Sigaba keyspace is far less than this astronomical riurnber
woiild indicate. In practice, only ten rotors were available for the ten cipher
and control rotor slots. Each of these rotors can be inserted forwards or
backwards. The order of thesc ten rot,ors and their orientations (forward or
rcvcrse) must be included in the practical keyspace calculation. In addition,
each of the five index rotors can be set to any of 10 positions, and each of the
control rotors can be set to any of 26 positions.
In principle, each of the five cipher rotors could also be set to any of 26 po-
sitions. However, the usual Sigaba keying procedure set these rotors to a de-
fault value, then stepped the rotors in a nonstandard manner-- simultaneously
stepping the control rotors to their actual starting positions. In addition, the
indcx rotors generally were inserted in one fixed order, in which case only
their initial settings were variable. Ta,king these restrictions into account, it
would appear that for Sigaba, as used in WWII, the keyspace was of size
2.4 SIGABA 59

as claimed in [go].
However, a careful reading of the Sigaba manual [113] reveals that the
setting of the control rotors was sent in the clear as a message indicator
or MI. Therefore, assuming the MI was intercepted and its meaning was
known to the attacker, the actual keyspace for Sigaba-as it was generally
used in WWII-was of size

lo! . 210 . 105 (2.8)

as (correctly) stated in the article [lag]. But, on the POTUS-PRIME' link
between Roosevelt and Churchill, the control and cipher rotor settings were
set independently, and neither was sent in the clear, which implies a keyspace
in excess of 95 bits [l28]. In the next section we provide a precise calculation
of the keyspace for this particular case.
A keyspace of size 248.4is small enough that today it is susceptible to
an exhaustive key ˜ e a r c h . But a keyspace of this magnitude would have
been unassailable using 1940s technology, provided no shortcut attack was

Sigaba Attack
For this attack, we assume that all three banks of rotors are set independently.
We also assume that there is only one set of index rotors, and that these five
rotors can be placed in any order, and that a total of ten rotors are available
for use as cipher and control rotors. The control and cipher rotors can be
inserted in any order and there are two orientations for each of these rotors.
Under these assumptions, the keyspace is apparently of size

However, due to the fact that pairs of index rotor outputs are ORed together
to determine the cipher rotor stepping, effectively only

10!/32 = 113,400 x 216.8

distinct index permutations can occur. This reduces the feasible keyspace
size to
lo! . 210 . 2G10 . 216.8 M 295.6

or less.
This full keyspace of size 295.6 was used on the POTUS-PRIME link be-
tween Roosevelt and Churchill, but not on other links. Again, this represents
8President Qf The United States PRIME Minister.
- ˜

'The Data Encryption Standard (DES) has a 56-bit key and it has been successfully
attacked by an exhaustive key search.

the largest Sigaba keyspace that was available in WWII. That is, it repre-
sents the largest practical keyspace, given the hardware that was typically
available with a Sigaba machine in WWII. Increasing the number of available
rotors would increase the keyspace, but we limit ourselves to the number of
rotors that will fit in the device at one time, since this is typically all that
was available with the cipher. Finally, we assume that all of the rotors and
the inner workings of the device are known to the cryptanalyst.
Our attack requires some amount of known plaintext. This attack occurs
in two phases--a primary phase and a secondary phase. In the primary phase,
we try all cipher rotor settings, retaining those that are consistent with the
known plaintext. Then in the secondary phase, we guess the control and
index rotor settings, and again use the known plaintext, this time to whittle
down the number of possible keys to a very small number of candidates.
Suppose that we have a Sigaba-encrypted ciphertext message, where the
first several letters of the corresponding plaintext are known. Our goal in
the primary phase is to recover the cipher rotors, their order, orientations
and initial settings. Collectively, we refer to these cipher rotor initializations
as the cipher rotor settings. In the primary phase, we strive to reduce the
number of cipher rotor settings to a small number--ideally just one. We refer
to an incorrect choice of cipher rotor settings as a random setting, while the
correct setting is said to be causal.
For each cipher rotor setting that survives the primary phase, a secondary
phase is required. This secondary phase consists of trying all possible control
and index rotor settings to determine which are consistent with the known
plaintext. In this way, the random primary survivors are eliminated and, in
the causal case, we determine the key.

Primary Phase
We are assuming that ten different cipher rotors are available. Also, each
cipher rotor has two possible orientations and 26 possible initial positions.
Therefore. the number of ways to select and initialize the five cipher rotors is

For each of these choices, we determine whether the setting is consistent with
t,he known plaintext as follows.
Recall that for each letter typed, from one to four of the cipher rotor
rotates. This implies that once we specify the cipher rotors, their orientations
and their initial settings, the number of possible new permutations at any
2.4 SIGABA 61

Now suppose that we correctly guess the cipher rotor settings at some point in
time. We can then generate each of the 30 possible subsequent permutations
and determine which are consistent with the next known plaintext letter.
That is, we can test each of these 30 subsequent permutations t o see which (if
any) encrypt the next known plaintext letter to the corresponding ciphertext
letter. For each surviving permutation, we can repeat this process using the
next known plaintext letter and so on.
Modeling the encryption permutations as uniformly random, the matches
follow a binomial distribution with p = 1/26 and n = 30, yielding an expected
number of matches of 30/26 x 1.154 per step. This can be viewed as a
branching phenomenon, where the number of possible paths tends to increase
with each known plaintext letter analyzed. That is, at each step, the number
of possible paths increases, which seems to be the opposite of what we would
like to see occur. Nevertheless, we can obtain useful information from this
process, as outlined below, but first we consider a simple example.
Suppose we have selected five of the ten available candidate rotors as
cipher rotors, and we have placed them in a specified order and selected their
orientations. This, together with the initial positions of the selected cipher
rotors constitutes a putative setting. Consider, for example, the case where
these cipher rotors are set to AAAAA, that is, each of the five cipher rotors is
initialized to A. Then we know the putative encryption pcrmutation and if it
does riot encrypt the first known plaintext to the first known ciphertext, this
cipher rotor setting is not causal and we can discard it. This immediately
reduces the number of candidates by a factor of 26, since there is only a 1/26
chance of a letter matching at random.
Suppose that the first letter does match. Then we must try all 30 possible
steps of the five cipher rotors arid save any of these that encrypt the second
plaintcxt letter to the second ciphertext letter. Since we make 30 comparisons,
The expected number of matches that occur at random is, as mentioned
above, 30/26 M 1.154. An example of this process is illustrated in Figure 2.20.
In this example, the first letter is consistent with the initial setting AAAAA,
and the first three letters are consistent with each of the given paths.
Note that at the third plaintext letter in Figure 2.20 we have two paths
ending at BBBBA. Since the next step depends only on the current cipher rotor
settings, and since we are only interested in the initial setting (not the entire
path), we can merge these paths as illustrated in Figure 2.21. This merging
is useful since it effectively reduces the number of paths under consideration,
while riot degrading the success of this phase of the attack.
In the random case, the analysis above holds, so that at each step we
expect an increase by a factor of 1.154 (before merging). In contrast, the
causal case provides a slightly higher increase on average, since we are assured
one causal match, with the remaining elements matching as in the random
case; see Problem 31. This gives us a method to distinguish random from

AAAAA 1st plaintext letter

2nd Dlaintext letter

3rd plaintext letter


Figure 2.20: Example of consistent paths.

1st plaintext letter


BBABA ABABA 2nd plaintext letter

3rd plaintext letter


Figure 2.21: Merged paths

causal and thereby reduce the number of random cases. Note also that only 1
in 26 of the random paths survive the first test, and many more vanish at
later steps.
Suppose we are in a random case and the first plaintext letter happens
to encrypt to the first ciphertext letter. Then the probability that none of
the 30 possible steps yields a match for the second letter is (25/26)" z 0.31,
and this holds for each subsequent letter. While the total number of paths
increases, the number of distinct merged paths decreases; see Problems 31
and 32.
The results in Table 2.7 illustrate typical numbers for the random case,
while the results in Table 2.8 illustrate typical numbers for the causal case.
For both cases, we have merged paths, as discussed above (and illustrated
in Figures 2.20 and 2.21). Table 2.7 indicates that using 30 known plaintext
letters, we expect only a fraction of about 0.000427 of the random cases
to survive, and each of these survivors will have expanded to an average of
about 16.5 paths, with a maximum for the cases tested of 84. In contrast,
Table 2.8 shows that with 30 known plaintext letters, we expect the causal
path to have generated about 29.6 consistent branches, with, for the 10.000
cases tested, a maximum of 151 and a minimum of one consistent path.
2.4 SIGABA 63

Table 2.7: Random Case

Tests Nonzero
Average Maximum
27 100,000
100,000 516
11.8 56
84 100,000
100,000 324
40 20.8
28.4 194
163 100,000
100,000 269
47.1 415
524 100,000
100,000 216
100.5 1005

Table 2.8: Causal Case

Maximum Minimum
10.2 1
94 1
151 10,000
29.6 1
237 1
404 1 10,000
566 10,000
60 1
689 5,000
70 85.0 1
829 2
1152 3,000
90 1
1926 3,000
161.1 1

The results in Table 2.7 show that we can eliminate the vast majority
of random cases using a small amount of known plaintext. Combined with
the causal results in Table 2.8, we can further reduce the number of random
cases by saving only those cases that are, say, above the expected mean in
the corresponding causal case. Of course, this latter refinement implies that
we will sometimes discard the causal case, with the probability depending on
the selected threshold. This approach provides a method for further reducing
the number of primary phase survivors, at the expense of a lower probability
of success. Unfortunately, Tables 2.7 arid 2.8 indicate that the variance is
high, so a significant number of random cases will remain for any reasonable
probability of success.
The work for this part of the attack is on the order of 243.4, since most
random paths do not survive the first known plaintext test (see Problem 23

for a slightly more precise estimate). We would like to minimize the amount of
known plaintext required, but we need to reduce the number of primary phase
survivors as much as possible. Using the approach outlined here, it appears
impractical to reduce the number of primary phase survivors by more than
factor of about 220, which leaves a large number of survivors (more than 2”)
that must be tested in the secondary phase (set: Problem 3 2 ) . However,
Problem 33 gives a more effective method for reducing the number of primary
survivors. The paper [28] contains more information on this attack, including
several further refinements.

Secondary Phase
For each of the cipher rotor settings that survived the primary phase, a sec-
ondary test is required. This secondary test will determine whether the cipher
rotor sctting is consistent with any setting of the control and index rotors. In
the process, we eliminate random survivors from the primary phase and for
the causal survivor we determine the rotor settings and thereby recover the
For the secondary test, we choose the order and initial positions of the
index rotors and the order, orientation and initial positions of the control
rotors- -given the putative cipher rotor settings from the primary phase. The
number of settings for the index and control rotors appears to be

Howevcr, as noted above, there arc only about 21”.8 distinct index perniuta-
tions. which reduces the overall work factor to

That is, the work factor for the secondary part of the attack appears to he on
the order of 252.2 for each putative setting that survived the primary phase.
Fortunately, we can improve on this nai™ve implementation of the secondary

Secondary Phase Refinement
To reduce the secondary work factor requires some amount of known plain-
text. Here, we only outline the plan of attack, leaving the details as a challenge
Thv irit,eraction of the control rotors and the index rotors is illustrated
in Figure 2.22. where we have collapscd the five control rotors into a single
permutation (denoted as “control”) and, similarly, the five index rotors are
corisidcred as a single permutation (denoted as “index”). The four inputs
2.4 SIGABA 65

to the control permutation, F, G, H, and I, are activated at each step. This
results in four active outputs, which are combined as indicated before being
fed into the index permutation. At least one-and at most four-inputs to the
index permutation will be active. The outputs from the index permutation
are combined in pairs, as indicated, and these determine which of the cipher
rotors, COthrough C4, step. At least one cipher rotor will step, and at niost
four will step.



Figure 2.22: Control and index permutations.

In Figure 2.22, the control permutation changes with each letter typed,
but the index permutation is fixed for the entire message. Since the control
permutations are changing, we model their output as uniformly random, that
is, we assume that each of the combinations of output letters is equally
likely at each step. Then, due to the way that the control rotor outputs are
ORed together, the inputs to the index permutation are not uniform. For
example, input 8 will be active much more often than inputs 1, 2, or 9 and
input 0 is never active.
The outputs of the index rotors are ORed in pairs, and the results deter-
mine the cipher rotor stepping. Therefore, if we have sufficient information on
the frequency of the stepping of individual cipher rotors-which is available
from known plaintext using the putative cipher rotor settings obtained in the
primary phase of the attack-we can assign probabilities to the index per-
mutations. For example, suppose that the index permutation is 5479381026,
that is, input 0 is mapped to output 5, input 1 is mapped to output 4, and
so on. Then by considering the pairs of outputs that determine the cipher
rotor stepping, we can see that some cipher rotors will step more often than
others. The data in Table 2.9 makes this more precise. For example, cipher
rotor C d steps if either output 1 or 2 (or both) of the index permutation is
active. For the index permutation in Table 2.9, inputs 6 and 8 are mapped
to outputs 1 and 2, respectively. Inputs 6 and 8 of the index permutation
correspond to outputs 6 and 8 of the current control permutation, and at

least one of these outputs is active if one or more of the 10 letters L, M, N,
0, U, V, W, X, Y, or Z, which are connected t o these outputs, are active. On
the other hand, CZ steps only when output A of the control permutation is
active. As a result, C will step much more often than Cz.

Table 2.9: Index Permutation 5479381026

Cipher Rotor
3 c
index rotor outputs (5,6) (7,8) (9,O)
(1,2) (3,4)
I (O,9) (2,5) (3,7)
index rotor inputs (4,l)
control rotor count 10 4 1 4 7

Assuming the control rotors generate random permutations, the expected
number of steps for cipher rotor i depends solely on the number of control
rotor output letters that feed into C,, as illustrated in Figure 2.22. All of
the 45 possible input pairs and the corresponding number of control rotor
output letters are tabulated in Table 2.10.

Table 2.10: Index Permutation Input Pairs

Letters Count Pairs
1 3 (0?9)

If we have sufficimt known plaintext available, we obtain information on
the “count” column of Table 2.9 for each cipher rotor simply based on a
count of the number of times that cipher rotor i steps. Then from the “pairs”
column, we obtain putative restrictions on the index permutation. Other
restrictions apply which further reduce the number of cases that must be
considered; see Problem 27.
Using the available information, we can reduce the number of possible
index perniutations to a small fraction of the 10!/32 216 permutations that
2.4 SIGABA 67

we would otherwise need to consider. In fact, with sufficient known plaintext,
the average number of permutations that we need to check is about 27 (the
range is about 24 to 21°). However, there is significant variability in the
amount of known plaintext required to distinguish the control rotor counts,
depending on the actual underlying index permutation.
With this refinement, the average work factor for the secondary phase of
the attack is about
27 . 5 ! . 25 . 2G5 N 242.4

which is somewhat less than the primary phase of the attack. However, this
work factor applies to each survivors from the primary phase, and we expect
a large number of primary survivors. Consequently, we could improve the
attack by either reducing the number of primary survivors or making the
secondary phase more efficient (or both).
Note that in this secondary phase, the actual index rotor settings are
not-and in fact cannot be--recovered. Several details of this phase of the
attack are explored more fully in Problems 27 and 28.
Thc typical secondary work factor for each primary survivor is on the
order of 243, assuming sufficient known plaintext is available. This amount of
work is clearly feasible, although the attack is not trivial to implement. The
primary phase of this attack has a similar work factor and it is also feasible.
However, for the attack described in this chapter, the primary phase yields
a larger number of survivors, which makes the overall cost of the secondary
phase high. In any case, either phase of this attack would have been far
beyond the realm of 1940s technology. Nevertheless, the attack outlined above
offers a dramatic shortcut as compared to an exhaustive key search, which,
under the assumptions of this section, would have a work factor of about 295.
Problem 33 suggests one method for improving the attack described in
this chapter. For the definitive treatment of this attack-including several
improvements over the outline given in this chapter-see [28].

Sigaba Conclusion
Recall from (2.8), above, that Sigaba, as typically used in WWII, had a
keyspace of size 248.4,which implies that an exhaustive key search has a
work factor of 247.6. However, the Sigaba-encrypted POTUS-PRIME link
between Roosevelt and Churchill used the full keyspace of more than 95 bits.
It is ciirious that keyspaces of these sizes were chosen. From the designers™
perspective, there would be no incentive to have a keyspace that is larger than
a known shortcut attack, since a larger keyspace entails more secret settings
and consequently more chance for errors and miscommunication.
In WWII, a work factor of 247.6 would certainly have been untouchable,
particularly for tactical communications. Nevertheless, for the strategically
important communication between Allied leaders, it would be reasonable t o

use a larger key size, provided that the larger key actually yields additional
security. Based on this logic, it would seem likely that the designers of Sigaba
believed that the cipher provided a full 95 bits of security. However, in this
section, we have outlined an attack that requires much less than 95 bits of
work. and it is possible to improve on the attack presented here: see [as]. In
any case, it would be interesting to know more about the Sigaba attacks that
were considered by Rowlett and Friedman, and their reasons for choosing the
key sizes as they did.

2.5 Summary
In this chapter we considered three of the most famous pre-modern cipher
machines. It is striking that the vast majority of cipher machines of the World
War I 1 era (and earlier) proved to be insecure, and most were shockingly
weak, at least by modern standards. As mentioned in the introduction to
this chapter, this was due in part to a failure to appreciate the differences
between machine systems and their predecessors, which consisted largely of
codebooks. One important difference is that the amount of data that was
encrypted with a machine was typically far greater than that which could be
processed using a codebook. Although by modern standards, the quantity of
data generated by these machines was miniscule, it was far greater than was
possible using labor intensive manual systems. As a result, the cryptanalysts
had a. relatively large amount of data to analyze, which allowed statistical
weaknesses of a cipher to be exploited. Of course, there are statistical attacks
on codebook ciphers, and these were well understood. The protection of a
codebook relied first and foremost on ensuring the physical security of the
codebook itself. Secondarily, the use of additive sequences could extend the
useful life of the codebook.
Whereas the security of a codebook depended primarily on the physical
security of the book, the security of a machine system depends almost entirely
on its statistical security, that is, it depends on the lack of any useful statis-
tical information “leaking” to the attacker through the ciphertext. This was
not well understood during WWII and, in fact, much effort was expended
trying to maintain the physical security of cipher machines, and compara-
tively little was done to probe for potential statistical weaknesses. Even with
the relatively secure Sigaba, it, was considered absolutely essential that the
machine not fall into enemy hands.
For modern cipher design, Kerckhoffs™ Principle reigns suprenie--at least
in principle, if not always in practice. Consequently, any respectable cipher
must go through an open and cxtensive peer-review process before it can be
considered secure, with the theory being that ”more eyes” will lead to “more
security”, particularly if those eyes belong to skilled cryptanalysts. It is also

assumed that the crypto algorithm is known to the attacker. Furthermore, a
cipher must be resistant to a variety of attacks, including known plaintext,
chosen plaintext, adaptively chosen plaintext, and so on, even if these attacks
do not seem particularly realistic in a specific application. This is all in stark
contrast to the situation in WWII, where a secret design was considered
essential. The bottom line is that the machine ciphers of WWII were often
viewed as little more than glorified codebook ciphers, which obscured the
fundamental distinctions between manual and machine cryptanalysis.
In fairness to WWII cipher designers, cryptology was not entirely scientific
at the time, in part due to the lack of any solid foundation for the field.
That situation began to change during WWII, and with the publication of
Shannon™s classic 1949 paper [133], cryptography finally emerged from the
realm of “black art” into a genuine scientific discipline.

1. Consider a rotor with permutation P of { 0 , 1 , 2 , . . . , n - l}. Suppose
that P permutes i to pi. Let di be the displacement of p i , that is,
di = p i - i (mod n). Find a formula for the elements of permutation 4,
the kth rotor shift of P, where the shift is in the same direction as the
rotors described in Section 2.2.3. Your formula must be in terms of pi
and d i .

2. Let F ( p ) , for p = 0 , 1 , 2 , . . . ,13, be the number of ways to plug p cables
into the Enigma stecker. Show that

; . (2p - 1) . (2p - 3) . ™ . . . 1.
F(p) =

3. In World War 11, the German™s usually used 10 cables on the stecker,
only five different rotors were in general use, one reflector was in com-
mon use, and the reflector and five rotors were known to the Allies.
Under these restrictions, show that there are only about 277 possible
Enigma keys. Also show that if we ignore the stecker, under these
restrictions there are fewer than 230 settings.

4. In the Enigma attack described in the text, we give the cycles

S(E) = p6p8p13s(E)

s(E) = P6Pi1q p & ˜s( .
Find two more independent cycles involving S ( E ) that can be obtained
from the matched plaintext and ciphertext in Table 2.2.

5. How many pairs of cycles are required in order to uniquely determine
the Enigma rotor settings?

6. Prove that the Enigma is its own inverse. Hint: Suppose that the ith
plaintext letter is II:, and that the corresponding ith ciphertext letter
is y. This implies that when the ith letter typed into the keyboard is II:,
the letter y is illuminated on the lightboard. Show that, for the same
key settings, if the ith letter typed into the keyboard is y, then the
letter II: is illuminated on the lightboard.

7. What is the advantage of a cipher (such as the Enigma) that is its
own inverse, as compared to a cipher that is not (such as Purple and

8. For the Enigma cipher.

a. Show that a ciphertext letter cannot be the same as the corre-
sponding plaintext letter.
b. Explain how this restriction gives the cryptanalyst an advantage
when searching for a suitable crib.”

9. Consider the Enigma attack discussed in the text and suppose that
only cycles of S ( E ) are used to recover the correct rotor settings. Then,
after the attack is completed, only the stecker value of S ( E ) is known.
Using only the matched plaintext and ciphertext in Table 2.2, how many
additional stecker values can be recovered?

10. Write a program to simulate the Enigma cipher. Use your program to
answer the following questions, where the rotor and reflector perrnuta-
tions are known to be


where Re is the left rotor, R ,is the middle rotor, R, is the right rotor,
and T is the reflector. Thc “notch” that causes the odometer effect is
at position Q for Re, V for R,, and J for R,. For example, the middle
rotor steps when the right rotor steps from V to W.

a,. Recover the initial rotor settings given the following matched plain-
text and Ciphertext.
“™In rriodcrn parlance, a crib is kriown as known plaintext.

0 1 2 3 4 5 6 7 8 9 101112131415161718192021
i 22 23 242526 27 28 293031 32 333435 36 3738394041 42 43
Ciphertext N B S M q T 9 ZI Y D D X K Y N EW J K ZR

11. Suppose that the same Enigma rotors (in the same order) and reflector
are used as in Problem 10, and the stecker has no cables connected.
Solve for the initial rotor settings and recover the plaintext given the
following ciphertext.


Hint: The plaintext is English.
12. Develop a ciphertext only attack on the Enigma, assuming that all you
know about the plaintext is that it is English. Analyze the work factor
of your proposed attack and also estimate the minimum amount of
ciphertext necessary for your attack to succeed. Assume that Enigma
rotors, the rotor order, the movable ring positions, and the reflector
are all known. Then you need to solve for the initial settings of the
three rotors and the stecker. Hint: Since E is the most common letter
in English, guess that the plaintext is EEEEEE.. . and use this “noisy”
plaintext to solve for the rotor and stecker settings.

13. Suggest niodifications to the Enigma design that would make the attack
discussed in Section 2.2 infeasible. Your objective is to make minor
modifications to the design.
14. Suppose that the “sixes” in the Purple cipher consist of the vowels,
AEIOUY. What is the expected frequency of each of the sixes and what
is the expected frequency of each of the twenties? Suppose instead that
the sixes consist of JKQVXZ. What is the expected frequency of each of
the sixes and what is the expected frequency of each of the twenties?
To answer these questions, use the English letter frequency distribution
given in Table 1.3 in Chapter 1.
(y)= 217.8 choices for the
15. Consider the Purple cipher. For each of the
“sixes,” let E6 be the average frequency for each of the sixes letters and

the let Ezo be the average frequency for each of the corresponding twen-
- E 0 < 0.1?
ties letters. For how many of these 217.8 selections is 21
To answer this question, use the English letter frequency distribution
in Table 1.3 in Chapter 1.

16. Suppose that we have two ciphers, both of which encrypt elements
of { 0 , 1 , 2 , .. . ,7} using permutations, where the permutation varies
with each step. One of these, known as cipher A , is a rotor machine,
analogous to the Enigma, while the other, known as cipher B , is a

switch-based machine, analogous to Purple. Which of the permuta-
tions P,Q, . . . , W , below, could have been generated by the A cipher
and which could have been generated by the B cipher? In each case,
justify your answer.

0 1 2 3 4567
5 2 1 7 6043
3 4 7 0 1652
7 4 6 5 2013
1 3 0 6472
W 3 5 6 2 1074
2 5 0 6 7134
7 4 2 0 6531
6 2 1 5 7304

17. Define the permutations P 2031, A = 0213 and B
1203, Q 3021.
= = =

a. Compute P A , QA, P B and QB, where, for example. P A denotes
the permutation A followed by the permutation P. Find the dif-
fwence sequence (as discussed in Section 2.3.3) for the pair PA,
Q A and also for thc pair P B , Q B .
b. Explain the results in part a.
c. Why are these results relevant to the diagnosis of Purple?

18. The permutations in Table 2.6 were generated from switched permu-
tations using a niethod analogous to that used in the Purple cipher.
Recover the L , M and R permutations (or an equivalent set of per-
mutations). Hint: There are three permutations per switch. Use the
permutations in lines 3, 4 and 5 to solve for the L permutations, lines 4,
I; and 9 to solve for the M permutations, and lines 0, 10 and 11 to solve
for the R permutations.

19. Consider the putative matched plaintext and ciphertext pairs in Ta-
ble 2.5. Explain why these could not have resulted from a 3-legged
depth of either the Enigma or Purple ciphers.

20. Suppose that a permutation P is wired to a rotor. Define n ( P )to be the
resulting permutation when the rotor is shifted one step. For example,
if P maps 0123456 to 6504213, then a ( P ) maps 0123456 to 4061532,
n z ( P )maps 0123456 to 3510264, and so on (see Section 2.2.3 and Prob-
lem 1). Consider the Maroon cipher that we invented in Section 2.3.
Let PL, PM and PK be given permutations of the 26 letters. Suppose
that the permutations on switch L are selected to be

Similarly, let the rotor permutations of PM be the permutations on the
switch M and the rotor shifts of PR be the permutations on switch R.

a. With this choice of permutations, how is Maroon similar to-and
different from--Enigma?
b. Suppose we choose the switched permutations of Maroon to be the
“rotor shifts” of a given permutation, as described above. Then
Maroon generates permutations similar to those produced by a
rotor machine, such as Enigma. It might, therefore, be argued
that Maroon is, in some sense, more general than the Enigma, and
therefore it must be at least as secure. What is wrong with this
line of reasoning?

21. The Sigaba cipher rotors and control rotors can each be inserted in a
forward or reverse orientation. In this problem we consider the permu-
tation generated by a rotor inserted in a reverse orientation.

a. Suppose that we have a rotor analogous to a Sigaba cipher rotor,
except that it is labeled with 0 through 6 instead of A through Z. If
the permutation on this rotor in its forward orientation is 3164205,
show that the corresponding permutation when the rotor is in-
serted in its reverse orientation is 5263041.
b. Given the permutation of a rotor in its forward orientation, explain
how to derive the corresponding reverse rotor permutation.

22. This problem deals with the Sigaba cipher.

a. Let P ( n ) be the probability of exactly n active inputs to the index
rotors, assuming that the control rotors generate random permu-
tations. Find P ( n ) for n = 1,2,3,4.
b. If there are n active inputs to the index rotors, then there are (f)
possible distinct active outputs. For n = 1,2,3,4, determine the
number of these ):( outputs that result in 1, 2, 3, and 4 of the
cipher rotors stepping.

c. Let S ( n )be the probability that exactly n cipher rotors step. As-
suming that the outputs in part b are uniformly distributed, cal-
culate S ( n ) for n = l , 2 , 3 , 4 .

23. In the primary phase of the Sigaba attack, using n known plaintext
letters, the expected work factor is z. 243.4 for some z.Suppose

+ p + p2 + . . . + pn-l ,
n: zz 1

where p = (25/26)”, that is, p is the probability that no consistent
extension of a path exists (in the random case). Under this assumption,
show that the primary phase work factor is less than 245.1 for any choice
of n.

24. Write a program to generate empirical results analogous to those in
Tables 2.7 and 2.8.

25. Consider a three rotor version of Sigaba, that is, assume that there are
three cipher rotors, three control rotors, and three index rotors, where
the rotors are the same as the actual Sigaba rotors. Assume that the
stepping maze has been modified so that from one to three of the cipher
rotors step with each letter encrypted or decrypted.

a. What is the size of the theoretical keyspace for this Sigaba variant?
b. Under assumptions analogous to those in Section 2.4.3, what is the
size of the keyspace? That is, assume that only the six rotors in the
machine are available for use as cipher or control rotors, the cipher
and control rotors each have two orientations, only three index
rotors are available, an itnalogous keying procedure is followed,
the index rotors are inserted in a fixed order, and so on.

26. Consider a three rotor version of Sigaba, as described in Problem 25.
Assume that the control rotors step in the same way as the three middle
Sigaba rotors. Also, assume that the active inputs to the control rotors
are F, G and H (that is, three inputs are active, not four, as is the case for
Sigaba) and the output of the control rotors are combined as in (2.7).
Also, the output of the index rotor bank is combined according to

c,= 0 0 v 0 3 v 0 9 , c = 0 2 v 0 4 v 0 s v 0 8 ,
1 v0 5 v07.
c =01

With these settings, at least onc of the cipher rotors will step, and at
most, all three will step. Suppose that the following cipher and control
rotors are available.
2.6 PR.OBLE,ZIS 75



. 3
( 16)