opposed to 25 for Purple), giving a cycle length of 33 = 27.

Table 2.6: Successive Permutations

5 0 6 1 3 2 4

i

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

p9

5 O w641 2

P0

l

2 1 3460 5

Pl 1

Consider permutations P and Ps in Table 2.6. The element in position 0

4

of P 4 is 4, while the 4 is in position 2 of P5. That is, the first element

WORLD WAR I1 CIPHERS

48

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

4

generated by consecutive shifts of a single rotor.

Now if we compute the difference sequence for permutations P and PCJ,

8

we see that it is the same as for P and Ps. This is not coincidental. In

4

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

4

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

4

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

example.

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

2.3.4

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.

WORLD WARI I CIPHERS

50

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

r

as Jade and Coral, but precise details on these machines are somewhat sketchy.

2.3 PURPLE 51

t

I

1

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.

WORLD WARII CIPHER,S

52

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.

Sigaba

2.4

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

2.4.1

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

WORLD WARI I CIPHERS

54

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

Q V RV SV T

17 = P V

Id=FVGVH

B

11 =

c Is= I V J V K (2.7)

I,=uvvvwvxvYvz

12 =

Ig=A

1;3=DVE I6=LVMVNVO

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

decryption.

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

Q

P 0 step

0

c N c

M

N

M L

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

WORLDWARII CIPHERS

56

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

N

.

0 d

U

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.

c

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

ZEROuONEuTWOuTHREEuFOURuFIVEuSIX

encrypts as

IEQDEMOKGJEYGOKWBXAIPKRHWARZODWG

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

O

c =0 7 V 0s

1

c =0 5 v 0s

,

C3 = 0 3 v 0 4

v0

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

2.4.2

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.

WORLD WARI I CIPHERS

58

cipher rotors

;stepping:

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

2884

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)

248.4

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

available.

Sigaba Attack

2.4.3

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.

WORLD WAR I1 ClPHER,S

60

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

WORLD WARI I CIPHERS

62

AAAAA 1st plaintext letter

2nd Dlaintext letter

BBABA ABABA

3rd plaintext letter

BBBBA BBBBA ACBBA

v

T T

Figure 2.20: Example of consistent paths.

1st plaintext letter

AAAAA

A

Y

BBABA ABABA 2nd plaintext letter

3rd plaintext letter

BBBBA ACBBA

i

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,

z

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

Steps

763

27 100,000

6.5

10

100,000 516

11.8 56

20

427

84 100,000

16.5

30

100,000 324

105

40 20.8

290

100,000

28.4 194

50

275

163 100,000

38.8

60

100,000 269

47.1 415

70

212

524 100,000

71.3

80

100,000 216

486

77.6

90

203

100.000

100.5 1005

100

Table 2.8: Causal Case

Tests

Maximum Minimum

Average

Steps

10,000

51

10.2 1

10

10,000

94 1

19.6

20

151 10,000

29.6 1

30

10,000

237 1

40.1

40

404 1 10,000

54.1

50

566 10,000

69.2

60 1

689 5,000

70 85.0 1

5,000

829 2

105.0

80

1152 3,000

130.4

90 1

1926 3,000

161.1 1

100

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

WORLD WARII CIPHERS

64

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

key.

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

phase.

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

problem.

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.

F

G

H

I

Control

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

(246)

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

WORLD W A RI 1 CIPHERS

66

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.

4

Table 2.9: Index Permutation 5479381026

Cipher Rotor

c

o

c

z

c

3 c

1

c

4

index rotor outputs (5,6) (7,8) (9,O)

(1,2) (3,4)

I (O,9) (2,5) (3,7)

(6,8)

index rotor inputs (4,l)

I

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

(0?1)

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

244

..

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

WORLD WAR I1 CIPHERS

68

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

2.6 PROBLEMS 69

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.

Problems

2.6

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)

and

s(E) = P6Pi1q p & ˜s( .

E)

Find two more independent cycles involving S ( E ) that can be obtained

from the matched plaintext and ciphertext in Table 2.2.

WORLD WARI1 CIPHERS

70

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

Sigaba)?

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

R = EKMFLGDQVZNTOWYHXUSPAIBRCJ

e

R, = BDFHJLCPRTXVZNYEIWGAKMUSQO

R, = ESOVPZJAYQUIRHXLNFTGKDCMWB

T = YRUHQSLDPXNGOKMIEBFZCWVJAT

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.

2.6 PROBLEMS 71

0 1 2 3 4 5 6 7 8 9 101112131415161718192021

i

ADH0CADL0C9UIDPR09U0S0

Plaintext

SWZ S0FCJMDCVU GELHSM BGG

Ciphertext

i 22 23 242526 27 28 293031 32 333435 36 3738394041 42 43

Plaintext LITTLETIMES0MUCHT0KN0W

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.

ERLORYROGGPBIMYNPRMHOUqYqETRqXTWGGEZVBFPRIJGXRSSCJTXJBMW

JRRPKRHXYMVVYGNGYMHZURYEYYXTTHCNIRYTPVHABJLBLNUZATWXEMKRI

WWEZIZNBEOqDDDCJRZZTLRLGPIFYPHUSMBCAMNODVYSJWKTZEJCKP4YYN

ZqKKJRQqHXLFCHHFRKDHHRTYILGGXXVBLTMPGCTUWPAIXOZOPKMNRXPMO

AMSUTIFOWDFBNDNLWWLNRWMPWWGEZKJNH

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

WORLDWARII CIPHERS

72

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

y

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

5

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.

2.6 PROBLEMS 73

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.

WORLD WARI I CIPHERS

74

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

2

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

Permutation