initial keys are weak keys [721,427]. Remember that the initial value is split into two halves, and each

half is shifted independently. If all the bits in each half are either 0 or 1, then the key used for any

cycle of the algorithm is the same for all the cycles of the algorithm. This can occur if the key is

entirely 1s, entirely 0s, or if one half of the key is entirely 1s and the other half is entirely 0s. Also, two

of the weak keys have other properties that make them less secure [427].

The four weak keys are shown in hexadecimal notation in Table 12.11. (Remember that every eighth

bit is a parity bit.)

Additionally, some pairs of keys encrypt plaintext to the identical ciphertext. In other words, one key

in the pair can decrypt messages encrypted with the other key in the pair. This is due to the way in

which DES generates subkeys; instead of generating 16 different subkeys, these keys generate only

two different subkeys. Each of these subkeys is used eight times in the algorithm. These keys are

called semiweak keys, and are shown in hexadecimal notation in Table 12.12.

Page 235 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Table 12.11

DES Weak Keys

Weak Key Value (with parity bits) Actual Key

0101 0101 0101 0101 0000000 0000000

1F1F 1F1F 0E0E 0E0E 0000000 FFFFFFF

E0E0 E0E0 F1F1 F1F1 FFFFFFF 0000000

FEFE FEFE FEFE FEFE FFFFFFF FFFFFFF

Some keys produce only four subkeys, each used four times in the algorithm. These possibly weak

keys are listed in Table 12.13.

Before condemning DES for having weak keys, consider that this list of 64 keys is minuscule

compared to the total set of 72,057,594,037,927,936 possible keys. If you select a random key, the odds

of picking one of these keys is negligible. If you are truly paranoid, you could always check for weak

keys during key generation. Some people don™t think it™s worth the bother. Others say that it™s so easy

to check, there™s no reason not to.

There is further analysis on weak and semiweak keys in [1116], and additional key patterns have been

investigated for weaknesses. None have been found.

Complement Keys

Take the bit-wise complement of a key; that is, replace all the 0s with 1s and the 1s with 0s. Now, if the

original key encrypts a block of plaintext, then the complement of the key will encrypt the

complement of the plaintext block into the complement of the ciphertext block.

If x™ is the complement of x, then the identity is as follows:

EK(P) = C

EK™(P™) = C™

This isn™t anything mysterious. The subkeys are XORed with the right half after the expansion

permutation in every round. This complementation property is a direct result of that fact.

Table 12.12

DES Semiweak Key Pairs

01FE 01FE 01FE 01FE and FE01 FE01 FE01 FE01

1FE0 1FE0 0EF1 0EF1 and E01F E01F F10E F10E

01E0 01E0 01F1 01F1 and E001 E001 F101 F101

1FFE 1FFE 0EFE 0EFE and FE1F FE1F FE0E FE0E

011F 011F 010E 010E and 1F01 1F01 0E01 0E01

E0FE E0FE F1FE F1FE and FEE0 FEE0 FEF1 FEF1

Page 236 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Table 12.13

DES Possibly Weak Keys

1F 1F 01 01 0E 0E 01 01 E0 01 01 E0 F1 01 01 F1

01 1F 1F 01 01 0E 0E 01 FE 1F 01 E0 FE 0E 01 F1

1F 01 01 1F 0E 01 01 0E FE 01 1F E0 FE 01 0E F1

01 01 1F 1F 01 01 0E 0E E0 1F 1F E0 F1 0E 0E F1

E0 E0 01 01 F1 F1 01 01 FE 01 01 FE FE 01 01 FE

FE FE 01 01 FE FE 01 01 E0 1F 01 FE F1 0E 01 FE

FE E0 1F 01 FE F1 0E 01 E0 01 1F FE F1 01 0E FE

E0 FE 1F 01 F1 FE 0E 01 FE 1F 1F FE FE 0E 0E FE

FE E0 01 1F FE F1 01 0E 1F FE 01 E0 0E FE 01 F1

E0 FE 01 1F F1 FE 01 0E 01 FE 1F E0 01 FE 0E F1

E0 E0 1F 1F F1 F1 0E 0E 1F E0 01 FE 0E F1 01 FE

FE FE 1F 1F FE FE 0E 0E 01 E0 1F FE 01 F1 0E FE

FE 1F E0 01 FE 0E F1 01 01 01 E0 E0 01 01 F1 F1

E0 1F FE 01 F1 0E FE 01 1F 1F E0 E0 0E 0E F1 F1

FE 01 E0 1F FE 01 F1 0E 1F 01 FE E0 0E 01 FE F1

E0 01 FE 1F F1 01 FE 0E 01 1F FE E0 01 0E FE F1

01 E0 E0 01 01 F1 F1 01 1F 01 E0 FE 0E 01 F1 FE

1F FE E0 01 0E FE F0 01 01 1F E0 FE 01 0E F1 FE

1F E0 FE 01 0E F1 FE 01 01 01 FE FE 01 01 FE FE

01 FE FE 01 01 FE FE 01 1F 1F FE FE 0E 0E FE FE

1F E0 E0 1F 0E F1 F1 0E FE FE E0 E0 FE FE F1 F1

01 FE E0 1F 01 FE F1 0E E0 FE FE E0 F1 FE FE F1

01 E0 FE 1F 01 F1 FE 0E FE E0 E0 FE FE F1 F1 FE

1F FE FE 1F 0E FE FE 0E E0 E0 FE FE F1 F1 FE FE

What this means is that a chosen-plaintext attack against DES only has to test half the possible keys:

255 keys instead of 256 [1080]. Eli Biham and Adi Shamir showed [172] that there is a known-plaintext

attack of the same complexity, requiring at least 233 known plaintexts.

It is questionable whether this is a weakness, since most messages don™t have complement blocks of

plaintext (in random plaintext, the odds against it are extremely high) and users can be warned not to

use complement keys.

Algebraic Structure

All possible 64-bit plaintext blocks can be mapped onto all possible 64-bit ciphertext blocks in 264!

different ways. The DES algorithm, with its 56-bit key, gives us 256 (approximately 1017) of these

mappings. Using multiple encryption, it seems possible to reach a larger portion of those possible

mappings. However, this is only true if the DES operation does not have certain algebraic structures.

Page 237 of 666

Applied Cryptography: Second Edition - Bruce Schneier

If DES were closed, then for any K1 and K2 there would always be a K3 such that

EK2(EK1(P)) = EK3(P)

In other words, the DES encryption operation would form a group, and encrypting a set of plaintext

blocks with K1 followed by K2 would be identical to encrypting the blocks with K3. Even worse, DES

would be vulnerable to a meet-in-the-middle known-plaintext attack that runs in only 228 steps [807].

If DES were pure, then for any K1 K2 and K3 there would always be a K4 such that

EK3(EK2(EK1(P))) = EK4(P)

Triple encryption would be useless. (Note that a closed cipher is necessarily pure but a pure cipher is

not necessarily closed.)

An early theoretical paper by Don Coppersmith gave some hints, but it wasn™t enough [377]. Various

cryptographers wrestled with this question [588,427,431,527,723,789]. Cycling experiments gathered

“overwhelming evidence” that DES is not a group [807,371,808,1116,809], but it wasn™t until 1992 that

cryptographers proved that DES is not a group [293]. Coppersmith said that the IBM team knew it all

along.

Key Length

IBM™s original submission to NBS had a 112-bit key. By the time the DES became a standard, that

was reduced to a 56-bit key. Many cryptographers argued for the longer key. Their arguments

centered on the possibility of a brute-force attack (see Section 7.1).

In 1976 and 1977, Diffie and Hellman argued that a special-purpose DES-cracking parallel computer

could recover the key in a day and cost $20 million. In 1981, Diffie upped this to a two-day search

time and a cost of $50 million [491]. Diffie and Hellman argued then that this was out of reach for

everybody except organizations like the NSA, but that by 1990 DES would be totally insecure [714].

Hellman [716] presented another argument against the small key size: By trading memory space for

time, it would be possible to speed up the searching process. He suggested the possibility of computing

and storing 256 possible results of encrypting a single plaintext block under every possible key. Then,

to break an unknown key, all that would be required would be for the cryptanalyst to insert the

plaintext block into the encryption stream, recover the resulting ciphertext, and look the key up.

Hellman pegged the cost of this cracking machine at $5 million.

Arguments for and against the existence of a DES-cracker lurking in some government basement

somewhere have continued. Several people pointed out that the mean time between failures for the

DES chips would never be high enough to ensure that the machine would work. This objection was

shown to be superfluous in [1278]. Others suggested ways to speed the process even further and to

reduce the effects of chip failures.

Meanwhile, hardware implementations of DES slowly approached the million-encryptions-per-second

requirement of Diffie and Hellman™s special-purpose machine. In 1984 DES chips capable of

performing 256,000 encryptions per second had been produced [533,534]. By 1987 chips performing

512,000 encryptions per second were being developed, and a version capable of checking over a

million keys per second was feasible [738,1573]. And in 1993 Michael Wiener designed a $1 million

Page 238 of 666

Applied Cryptography: Second Edition - Bruce Schneier

machine that could complete a brute-force attack against DES in an average of 3.5 hours (see Section

7.1).

No one has publicly admitted building this machine, although it is a reasonable assumption that

someone has. A million dollars is not a lot of money to a large”or even a medium-sized”country.

It was not until 1990 that two Israeli mathematicians, Biham and Shamir, discovered differential

cryptanalysis, a technique that put to rest the question of key length. Before we discuss that

technique, let™s turn to some other design criticisms of DES.

Number of Rounds

Why 16 rounds? Why not 32? After five rounds every ciphertext bit is a function of every plaintext bit

and every key bit [1078,1080], and after eight rounds the ciphertext was essentially a random function

of every plaintext bit and every key bit [880]. (This is called the avalanche effect.) So why not stop

after eight rounds?

Over the years, variants of DES with a reduced number of rounds have been successfully attacked.

DES with three or four rounds was easily broken in 1982 [49]. DES with six rounds fell some years

later [336]. Biham and Shamir™s differential cryptanalysis explained this as well: DES with any

number of rounds fewer than 16 could be broken with a known-plaintext attack more efficiently than

by a brute-force attack. Certainly brute-force is a much more likely attack, but it is interesting that

the algorithm has exactly 16 rounds.

Design of the S-Boxes

In addition to being accused of reducing the key length, NSA was also accused of modifying the

contents of the S-boxes. When pressed for design justification for the S-boxes, the NSA indicated that

elements of the algorithm™s design were “sensitive” and would not be made public. Many

cryptographers were concerned that the NSA-designed S-boxes hid a trapdoor, making it possible for

them to easily cryptanalyze the algorithm.

Since then, considerable effort has gone into analyzing the design and operation of the S-boxes. In the

mid-1970s, Lexar Corporation [961,721] and Bell Laboratories [1120] examined the operation of the

S-boxes. Neither analysis revealed any weaknesses, although both found inexplicable features. The S-

boxes had more features in common with a linear transformation than one would expect if they were

chosen at random. The Bell Laboratories team stated that the S-boxes may have hidden trapdoors,

and the Lexar report concluded with:

Structures have been found in DES that were undoubtedly inserted to strengthen the

system against certain types of attack. Structures have also been found that appear to

weaken the system.

On the other hand, this report also warned:

...the problem [of the search for structure in the S-boxes] is complicated by the ability of

the human mind to find apparent structure in random data, which is really not structure

at all.

At the second workshop on DES, the National Security Agency revealed several design criteria behind

the S-boxes [229]. This did nothing to quell people™s suspicions, and the debate continued

[228,422,714,1506,1551].

Page 239 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Various oddities about the S-boxes appeared in the literature. The last three output bits of the fourth

S-box can be derived in the same way as the first by complementing some of the input bits [436,438].

Two different, but carefully chosen, inputs to S-boxes can produce the same output [436]. It is

possible to obtain the same output of a single DES round by changing bits in only three neighboring

S-boxes [487]. Shamir noticed that the S-boxes entries appeared to be somewhat imbalanced, but

wasn™t about to turn that imbalance into an attack [1423]. (He mentioned a feature of the fifth S-box,

but it took another eight years before linear cryptanalysis exploited that feature.) Other researchers

showed that publicly known design principles could be used to generate S-boxes with the observed

characteristics [266].

Additional Results

There were other attempts to cryptanalyze DES. One cryptographer looked at nonrandomness based

on spectral tests [559]. Others analyzed sequences of linear factors, but their attack failed after eight

rounds [1297,336,531]. A 1987 unpublished attack by Donald Davies exploited the way the expansion

permutation repeats bits into adjacent S-boxes; this attack is also impractical after eight rounds

[172,429].

12.4 Differential and Linear Cryptanalysis

Differential Cryptanalysis

In 1990, Eli Biham and Adi Shamir introduced differential cryptanalysis [167,168,171,172]. This is a

new method of cryptanalysis, heretofore unknown to the public. Using this method, Biham and

Shamir found a chosen-plaintext attack against DES that was more efficient than brute force.

Differential cryptanalysis looks specifically at ciphertext pairs: pairs of ciphertexts whose plaintexts

have particular differences. It analyzes the evolution of these differences as the plaintexts propagate

through the rounds of DES when they are encrypted with the same key.

Simply, choose pairs of plaintexts with a fixed difference. The two plaintexts can be chosen at

random, as long as they satisfy particular difference conditions; the cryptanalyst does not even have

to know their values. (For DES, the term “difference” is defined using XOR. This can be different for

different algorithms.) Then, using the differences in the resulting ciphertexts, assign different

probabilities to different keys. As you analyze more and more ciphertext pairs, one key will emerge as

the most probable. This is the correct key.

The details are more complicated. Figure 12.5 is the DES round function. Imagine a pair of inputs, X

and X™, that have the difference DX. The outputs, Y and Y™ are known, and therefore so is the

difference, Y. Both the expansion permutation and the P-box are known, so ∆A and ∆C are known. B

and B™ are not known, but their difference ∆B is known and equal to ∆A. (When looking at the

difference, the XORing of Ki with A and A™ cancels out.) So far, so good. Here™s the trick: For any

given ∆A, not all values of ∆C are equally likely. The combination of ∆A and ∆C suggests values for

bits of A XOR Ki and A™ XOR Ki. Since A and A™ are known, this gives us information about Ki.

Look at the last round of DES. (Differential cryptanalysis ignores the initial and final permutation.

They have no effect on the attack, except to make it harder to explain.) If we can identify K16 then we

have 48 bits of the key. (Remember, the subkey in each round consists of 48 bits of the 56-bit key.)

The other 8 bits we can get by brute force. Differential cryptanalysis will get us K16.

Page 240 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Certain differences in plaintext pairs have a high probability of causing certain differences in the

resulting ciphertext pairs. These are called characteristics. Characteristics extend over a number of

rounds and essentially define a path through these rounds. There is an input difference, a difference

at each round, and an output difference”with a specific probability.

You can find these characteristics by generating a table where the rows represent the possible input

XORs (the XOR of two different sets of input bits), the columns represent the possible output XORs,

and the entries represent the number of times a particular output XOR occurs for a given input XOR.

You can generate such a table for each of DES™s eight S-boxes.

Figure 12.5 DES round function.

For example, Figure 12.6a is a one-round characteristic. They input difference of the left side is L; it

could be anything. The input difference of the right side is 0. (The two inputs have the same right-

hand side, so their difference is 0.) Since there is no difference going in to the round function, then

there is no difference coming out of the round function. Therefore, the output difference of the left

side is L 0 = L, and the output difference of the right side is 0. This is a trivial characteristic, and is

true with probability 1.

Figure 12.6b is a less obvious characteristic. Again, the input difference to the left side is arbitrary: L.

The input difference to the right side is 0x60000000; the two inputs differ in only the second and third

bits. With a probability of 14/64, the output difference of the round function is L 0x00808200. This

means that the output difference of the left side is L 0x00808200 and the output difference of the

right side is 0x60000000”with probability 14/64.

Different characteristics can be joined. And, assuming the rounds are independent, the probabilities

can be multiplied. Figure 12.7 joins the two characteristics previously described. The input difference

to the left side is 0x00808200 and the input difference to the right side is 0x60000000. At the end of the

first round the input difference and the output of the round function cancel out, leaving an output

difference of 0. This feeds into the second round; the final output difference of the left side is

0x60000000 and the final output difference of the right side is 0. This two-round characteristic has a

probability of 14/64.

A plaintext pair that satisfies the characteristic is a right pair. A plaintext pair which does not is a

wrong pair. A right pair will suggest the correct round key (for the last round of the characteristic); a

wrong pair will suggest a random round key.

Page 241 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Figure 12.6 DES characteristics.

Figure 12.7 A two-round DES characteristic.

To find the correct round key, simply collect enough guesses so that one subkey is suggested more

often than all the others. In effect, the correct subkey will rise out of all the random alternatives.

So, the basic differential attack on n-round DES will recover the 48-bit subkey used in round n, and

the remaining 8 key bits are obtained by brute-force guessing.

There are still considerable problems. First, there is a negligible chance of success until you reach

some threshold. That is, until you accumulate sufficient data you can™t tell the correct subkey from all

the noise. And the attack isn™t practical: You have to use counters to assign different probabilities to

248 possible subkeys, and too much data is required to make this work.

At this point, Biham and Shamir tweaked their attack. Instead of a using a 15-round characteristic on

16-round DES, they used a 13-round characteristic and some tricks to get the last few rounds. A

shorter characteristic with a higher probability worked better. And they used some clever

mathematics to obtain 56-bit key candidates which could be tested immediately, eliminating the need

for counters. This attack succeeds as soon as a right pair is found; this avoids the threshold and gives

a linear success probability. If you have 1000 times fewer pairs, then you have 1000 times smaller

chance of success. This sounds terrible, but it is a lot better than the threshold. There is always some

chance of immediate success.

The results are most interesting. Table 12.14 is a summary of the best differential attack against DES

with varying numbers of rounds [172]. The first column is the number of rounds. The next two

columns are the numbers of chosen plaintexts or known plaintexts that must be examined for the

attack, and the fourth column is the number of those plaintexts actually analyzed. The last column is

the complexity of analysis, after the required plaintexts are found.

Page 242 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Table 12.14

Differential Cryptanalysis Attacks against DES

No. of Rounds Chosen Plaintexts Known Plaintexts Analyzed Plaintexts Complexity of Analysis

214 238 29

8 4

224 244 232†

9 2

224 243 214 215

10

231 247 232†

11 2

231 247 221 221

12

239 252 232†

13 2

239 251 229 229

14

247 256 27 237

15

247 255 236 237

16

†The complexity of the analysis can be greatly reduced for these variants by using about four times as many

plaintexts with the clique method.

The best attack against full 16-round DES requires 247 chosen plaintexts. This can be converted to a

known plaintext attack, but that requires 255 known plaintexts. And 237 DES operations are required

during analysis.

Differential cryptanalysis works against DES and other similar algorithms with constant S-boxes. The

attack is heavily dependent on the structure of the S-boxes; the ones in DES just happen to be

optimized against differential cryptanalysis. And the attack works against DES in any of its operating

modes”ECB, CBC, CFB, and OFB”with the same complexity [172].

DES™s resistance can be improved by increasing the number of rounds. Chosen-plaintext differential

cryptanalysis DES with 17 or 18 rounds takes about the same time as a brute-force search [160]. At 19

rounds or more, differential cryptanalysis becomes impossible because it requires more than 264

chosen plaintexts: Remember, DES has a 64-bit block size, so it only has 264 possible plaintext blocks.

(In general, you can prove that an algorithm is resistant to differential cryptanalysis by showing that

the amount of plaintext required to mount such an attack is greater than the amount of plaintext

possible.)

Here are a few important points. First, this attack is largely theoretical. The enormous time and data

requirements to mount a differential cryptanalytic attack put it beyond the reach of almost everyone.

To get the requisite data for this attack against a full DES, you have to encrypt a 1.5 megabits-per-

second data stream of chosen plaintext for almost three years. Second, this is primarily a chosen-

plaintext attack. It can be converted to a known-plaintext attack, but you have to sift through all of

the plaintext-ciphertext pairs looking for the useful ones. For full 16-round DES, this makes the

attack slightly less efficient than brute force (the differential cryptanalytic attack requires 255.1

operations, and brute force requires 255). The consensus is that DES, when implemented properly, is

still secure against differential cryptanalysis.

Why is DES so resistant to differential cryptanalysis? Why are the S-boxes optimized to make this

Page 243 of 666

Applied Cryptography: Second Edition - Bruce Schneier

attack as difficult as possible? Why are there as many rounds as required, but no more? Because the

designers knew about it. IBM™s Don Coppersmith recently wrote [373,374]:

The design took advantage of certain cryptanalytic techniques, most prominently the

technique of “differential cryptanalysis,” which were not known in the published

literature. After discussions with NSA, it was decided that disclosure of the design

consideration would reveal the technique of differential cryptanalysis, a powerful

technique that can be used against many ciphers. This in turn would weaken the

competitive advantage the United States enjoyed over other countries in the field of

cryptography.

Adi Shamir responded to this, challenging Coppersmith to say that he hadn™t found any stronger

attacks against DES since then. Coppersmith has chosen to remain silent on that question [1426].

Related-Key Cryptanalysis

Table 12.3 showed the number of bits the DES key is rotated after each round: 2 bits after each

round, except for 1 bit after rounds 1, 2, 9, and 16. Why?

Related-key cryptanalysis is similar to differential cryptanalysis, but it examines the difference

between keys. The attack is different from any previously discussed: The cryptanalyst chooses a

relationship between a pair of keys, but does not know the keys themselves. Data is encrypted with

both keys. In the known-plaintext version, the cryptanalyst knows the plaintext and ciphertext of data

encrypted with the two keys. In the chosen-plaintext version, the cryptanalyst gets to choose the

plaintext encrypted with the two keys.

A modified DES, where the key is rotated two bits after every round, is less secure. Related-key

cryptanalysis can break that variant using 217 chosen-key chosen plaintexts or 233 chosen-key known

plaintexts [158,163].

This attack is not at all practical, but it is interesting for three reasons. One, it is the first

cryptanalytic attack against DES™s subkey-generation algorithm. Two, this attack is independent of

the number of rounds of the cryptographic algorithm; it™s just as effective against DES with 16

rounds, 32 rounds, or 1000 rounds. And three, DES is impervious to this attack. The variability in the

rotation thwarts related-key cryptanalysis.

Linear Cryptanalysis

Linear cryptanalysis is another type of cryptanalytic attack, invented by Mitsuru Matsui

[1016,1015,1017]. This attack uses linear approximations to describe the action of a block cipher (in

this case, DES.)

This means that if you XOR some of the plaintext bits together, XOR some ciphertext bits together,

and then XOR the result, you will get a single bit that is the XOR of some of the key bits. This is a

GÃ,

linear approximation and will hold with some probability p. If p GÃ then this bias can be exploited.

Use collected plaintexts and associated ciphertexts to guess the values of the key bits. The more data

you have, the more reliable the guess. The greater the bias, the greater the success rate with the same

amount of data.

How do you identify good linear approximations for DES? Find good 1-round linear approximations

and join them together. (Again, ignore the initial and final permutations; they don™t affect the attack.)

Page 244 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Look at the S-boxes. There are 6 input bits and 4 output bits. The input bits can be combined using

XOR in 63 useful ways (26 - 1), and the output bits can be combined in 15 useful ways. Now, for each

S-box you can evaluate the probability that for a randomly chosen input, an input XOR combination

equals some output XOR combination. If there is a combination with a high enough bias, then linear

cryptanalysis may work.

If the linear approximations are unbiased, then they would hold for 32 of the 64 possible inputs. I™ll

spare you the pages of tables, but the most biased S-box is S-box 5. In fact, the second input bit is

equal to the XOR of all 4 output bits for only 12 inputs. This translates to a probability of 3/16, or a bias

of 5/16, and is the most extreme bias in all the S-boxes. (Shamir noted this in [1423], but could not find a

way to exploit it.)

Figure 12.8 shows how to turn this into an attack against the DES round function. The input bit into

S-box 5 is b26. (I am numbering the bits from left to right and from 1 to 64. Matsui ignores this

convention with DES and numbers his bits from right to left and from 0 to 63. It™s enough to drive

you mad.) The 4 output bits from S-box 5 are c17 c18 c19 and c20. We can trace b26 backwards from

the input to the S-box. The bit a26 is XORed with a bit from the subkey Ki,26 to obtain b26. And bit

X17 goes through the expansion permutation to become a26. After the S-box, the 4 output bits go

through the P-box to become 4 output bits of the round function: Y3 Y8 Y14 and Y25. This means that

with probability ½ - 5/16 :

Figure 12.8 A 1-round linear approximation for DES.

X17 Y3 Y8 Y14 Y25 = Ki,26

Linear approximations for different rounds can be joined in a manner similar to that discussed under

differential cryptanalysis. Figure 12.9 is a 3-round approximation with a probability of ½ + .0061. The

individual approximations are of varying quality: The last is very good, the first is pretty good, and

the middle is bad. But together the three 1-round approximations give a very good three-round

approximation.

The basic attack is to use the best linear approximation for 16-round DES. It requires 247 known

plaintext blocks, and will result in 1 key bit. That™s not very useful. If you interchange the role of

plaintext and ciphertext and use decryption as well as encryption, you can get 2 key bits. That™s still

not very useful.

Page 245 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Figure 12.9 A 3-round linear approximation for DES.

There are refinements. Use a 14-round linear approximation for rounds 2 through 15. Guess the 6

subkey bits relevant to S-box 5 for the first and last rounds (12 key bits in all). Effectively you are

doing 212 linear cryptanalyses in parallel and picking the correct one based on probabilities. This

recovers the 12 bits plus the b26 and reversing plaintext and ciphertext recovers another 13 bits. To

get the remaining 30 bits, use exhaustive search. There are other tricks, but that™s basically it.

Against full 16-round DES, this attack can recover the key with an average of 243 known plaintexts. A

software implementation of this attack recovered a DES key in 50 days using 12 HP9000/735

workstations [1019]. That is the most effective attack against DES at the time of this writing.

Linear cryptanalysis is heavily dependent on the structure of the S-boxes and the S-boxes in DES are

not optimized against this attack. In fact, the ordering of the S-boxes chosen for DES lies among the 9

percent to 16 percent that offer the least protection against linear cryptanalysis [1018]. According to

Don Coppersmith [373,374], resistance to linear cryptanalysis “was not part of the design criteria of

DES.” Either they didn™t know about linear cryptanalysis or they knew about something else even

more powerful whose resistance criteria took precedence.

Linear cryptanalysis is newer than differential cryptanalysis, and there may be more performance

improvements in the coming years. Some ideas are proposed in [1270,811], but it is not clear that they

can be used effectively against full DES. They work very well against reduced round variants,

however.

Future Directions

Some work has been done to try to extend the concept of differential cryptanalysis to higher-order

differentials [702,161,927,858,860]. Lars Knudsen uses something called partial differentials to attack

6-round DES; it requires 32 chosen plaintexts and 20,000 encryptions [860]. It is still too new to know

if these extensions will make it easier to attack full 16-round DES.

Another avenue of attack is differential-linear cryptanalysis: combining differential and linear

cryptanalysis. Susan Langford and Hellman have an attack on 8-round DES that recovers 10 key bits

with an 80 percent probability of success with 512 chosen plaintexts and a 95 percent probability of

success with 768 chosen plaintexts [938]. After the attack, a brute-force search of the remaining

keyspace (246 possible keys) is required. While this attack is comparable in time to previous attacks, it

Page 246 of 666

Applied Cryptography: Second Edition - Bruce Schneier

requires far less plaintext. However, it doesn™t seem to extend easily to more rounds.

But this attack is still new and work continues. It is possible that there may be a breakthrough some

time during the next few years. Maybe there are benefits in combining this attack with higher-order

differential cryptanalysis. Who knows?

12.5 The Real Design Criteria

After differential cryptanalysis became public, IBM published the design criteria for the S-boxes and

the P-box [373,374]. The criteria for the S-boxes are:

” Each S-box has 6 input bits and 4 output bits. (This was the largest size that could be

accommodated in a single chip with 1974 technology.)

” No output bit of an S-box should be too close to a linear function of the input bits.

” If you fix the left-most and right-most bits of an S-box and vary the 4 middle bits, each

possible 4-bit output is attained exactly once.

” If two inputs to an S-box differ in exactly 1 bit, the outputs must differ in at least 2 bits.

” If two inputs to an S-box differ in the 2 middle bits exactly, the outputs must differ in

at least 2 bits.

” If two inputs to an S-box differ in their first 2 bits and are identical in their last 2 bits,

the two outputs must not be the same.

” For any nonzero 6-bit difference between inputs, no more than 8 of the 32 pairs of

inputs exhibiting that difference may result in the same output difference.

” A criterion similar to the previous one, but for the case of three active S-boxes.

The criteria for the P-box are:

” The 4 output bits from each S-box in round i are distributed so that 2 of them affect the

middle-bits of S-boxes at roundi + 1 and the other 2 affect end bits.

” The 4 output bits from each S-box affect six different S-boxes; no 2 affect the same S-

box.

” If the output bit from one S-box affects a middle bit of another S-box, then an output

bit from that other S-box cannot affect a middle bit of the first S-box.

The paper goes on to discuss the criteria. Generating S-boxes is pretty easy today, but was a

complicated task in the early 1970s. Tuchman has been quoted as saying that they ran computer

programs for months cooking up the S-boxes.

12.6 DES Variants

Multiple DES

Some DES implementations use triple-DES (see Figure 12.10) [55]. Since DES is not a group, then the

resultant ciphertext is much harder to break using exhaustive search: 2112 attempts instead of 256

attempts. See Section 15.2 for more details.

Page 247 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Figure 12.10 Triple-DES.

DES with Independent Subkeys

Another variation is to use a different subkey for each round, instead of generating them from a

single 56-bit key [851]. Since 48 key bits are used in each of 16 rounds, this means that the key length

for this variant is 768 bits. This variant would drastically increase the difficulty of a brute-force

attack against the algorithm; that attack would have a complexity of 2768.

However, a meet-in-the-middle attack (see Section 15.1) would be possible. This would reduce the

complexity of attack to 2384; still long enough for any conceivable security needs.

Although independent subkeys foil linear cryptanalysis, this variant is susceptible to differential

cryptanalysis and can be broken with 261 chosen plaintexts (see Table 12.15) [167,172]. It would seem

that any modification of the key schedule cannot make DES much stronger.

DESX

DESX is a DES variant from RSA Data Security, Inc. that has been included in the MailSafe

electronic mail security program since 1986 and the BSAFE toolkit since 1987. DESX uses a technique

called whitening (see Section 15.6) to obscure the inputs and outputs to DES. In addition to a 56-bit

DES key, DESX has an additional 64-bit whitening key. These 64 bits are XORed to the plaintext

before the first round of DES. An additional 64 bits, computed as a one-way function of the entire

120-bit DES key, is XORed to the ciphertext after the last round [155]. Whitening makes DESX much

stronger than DES against a brute-force attack; the attack requires (2120)/n operations with n known

plaintexts. It also improves security against differential and linear cryptanalysis; the attacks require

261 chosen plaintexts and 260 known plaintexts, respectively [1338].

CRYPT(3)

CRYPT(3) is a DES variant found on UNIX systems. It is primarily used as a one-way function for

passwords, but sometimes can also be used for encryption. The difference between CRYPT(3) and

DES is that CRYPT(3) has a key-dependent expansion permutation with 212 possible permutations.

This was done primarily so that off-the-shelf DES chips could not be used to construct a hardware

password-cracker.

Generalized DES

Generalized DES (GDES) was designed both to speed up DES and to strengthen the algorithm

[1381,1382]. The overall block size increases while the amount of computation remains constant.

Figure 12.11 is a block diagram of GDES. GDES operates on variable-sized blocks of plaintext.

Encryption blocks are divided up into q 32-bit sub-blocks; the exact number depends on the total

Page 248 of 666

Applied Cryptography: Second Edition - Bruce Schneier

block size (this was variable in the design, but must be fixed for each implementation). In general, q

equals the block size divided by 32.

Function f is calculated once per round on the right-most block. The result is XORed with all the

other parts, which are then rotated to the right. GDES has a variable number of rounds, n. There is a

slight modification to the last round, so that the encryption and decryption processes differ only in the

order of the subkeys (just like DES). In fact, if q = 2 and n = 16, this is DES.

Biham and Shamir [167,168] showed that, using differential cryptanalysis, GDES with q = 8 and n =

16 is breakable with only six chosen plaintexts. If independent subkeys are also used, 16 chosen

plaintexts are required. GDES with q = 8 and n = 22 is breakable with 48 chosen plaintexts, and

GDES with q = 8 and n = 31 requires only 500,000 chosen plaintexts to break. Even GDES with q = 8

and n = 64 is weaker than DES; 249 chosen plaintexts are required to break it. In fact, any GDES

scheme that is faster than DES is also less secure (see Table 12.15).

A variant of this scheme recently appeared [1591]. It is probably no more secure than the original

GDES. In general, any large block DES variant that is faster than DES is probably also less secure

than DES.

DES with Alternate S-Boxes

Other DES modifications centered around the S-boxes. Some designs made the order of the S-boxes

variable. Other designers varied the contents of the S-boxes themselves. Biham and Shamir showed

[170,172] that the design of the S-boxes, and even the order of the S-boxes themselves, were optimized

against differential cryptanalysis:

The replacement of the order of the eight DES S-boxes (without changing their value) also

makes DES much weaker: DES with 16 rounds of a particular replaced order is breakable

in about 238 steps.... DES with random S-boxes is shown to be very easy to break. Even a

minimal change of one entry of one of the DES S-boxes can make DES easier to break.

The DES S-boxes were not optimized against linear cryptanalysis. There are better S-boxes than the

ones that come with DES, but blindly choosing new S-boxes isn™t a good idea.

Figure 12.11 GDES.

Table 12.15 [167,169] lists some modifications to DES and the number of chosen plaintexts required

Page 249 of 666

Applied Cryptography: Second Edition - Bruce Schneier

for differential cryptanalysis. One change not listed, combining the left and right halves using

addition mod 24 instead of XOR, is 217 times harder to break than DES [689].

RDES

RDES is a variant that replaces swapping the left and right halves at the end of each round with a

key-dependent swap [893]. The swappings are fixed, depending solely on the key. This means that the

15 key-dependent swaps occur with 215 possible instances, and that the variant is not resistant to

differential cryptanalysis [816,894,112]. RDES has a large number of weak keys. In fact, almost every

key is weaker than a typical DES key. This variant should not be used.

A better idea is to swap only within the right half, at the beginning of each round. Another better idea

is to make the swapping dependent on the input data and not a static function of the key. There are a

number of possible variants [813,815]. In RDES-1, there is a data-dependent swap of the 16-bit words

at the beginning of each round. In RDES-2, there is a data-dependent swap of the bytes at the

beginning of each round after the 16-bit swappings as in RDES-1. And so on through RDES-4. RDES-

1 is secure against both differential cryptanalysis [815] and linear cryptanalysis [1136]. Presumably

RDES-2 and greater are as well.

Table 12.15

Differential Cryptanalysis Attacks against DES Variants

Modified Operation Chosen Plaintexts

247

Full DES (no modification)

P permutation Cannot strengthen

219

Identity permutation

238

Order of S-boxes

239, 231

Replace XORs by additions

S-boxes:

218“220

Random

233“241

Random permutations

233

One entry

226

Uniform tables

226

Elimination of the E Expansion

244

Order of E and subkey XOR

GDES (width q = 8):

16 rounds 6, 16

249 (independent key)

64 rounds

sn DES

A group of Korean researchers, led by Kwangjo Kim, has attempted to find a set of S-boxes that are

optimally secure against both linear and differential cryptanalysis. Their first attempt, known as

s2DES, was presented in [834] and shown to be worse than DES against differential cryptanalysis in

Page 250 of 666

Applied Cryptography: Second Edition - Bruce Schneier

[855,858]. Their next attempt, s3DES, was presented in [839] and shown to be worse than DES against

linear cryptanalysis [856,1491,1527,858,838]. Biham suggested a minor change to make s3DES secure

against both linear and differential cryptanalysis [165]. The group went back to their computers and

developed better techniques for S-box design [835,837]. They proposed s4DES [836] and then s5DES

[838,944].

Table 12.16 gives the s3DES S-boxes with S-box 1 and S-box 2 reversed, which are secure against both

differential and linear cryptanalysis. Sticking this variant in a triple-DES mix is sure to irritate

cryptanalysts.

DES with Key-Dependent S-Boxes

Linear and differential cryptanalysis work only if the analyst knows the composition of the S-boxes. If

the S-boxes are key-dependent and chosen by a cryptographically strong method, then linear and

differential cryptanalysis are much more difficult. Remember though, that randomly generated S-

boxes have very poor differential and linear characteristics; even if they are secret.

Table 12.16

s3DES S-Boxes (with S-box 1 and S-box 2 reversed)

S-box 1:

13 14 0 3 10 4 7 9 11 8 12 6 1 15 2 5

8 2 11 13 4 1 14 7 5 15 0 3 10 6 9 12

14 9 3 10 0 7 13 4 8 5 6 15 11 12 1 2

1 4 14 7 11 13 8 2 6 3 5 10 12 0 15 9

S-box 2:

15 8 3 14 4 2 9 5 0 11 10 1 13 7 6 12

6 15 9 5 3 12 10 0 13 8 4 11 14 2 1 7

9 14 5 8 2 4 15 3 10 7 6 13 1 11 12 0

10 5 3 15 12 9 0 6 1 2 8 4 11 14 7 13

S-box 3:

13 3 11 5 14 8 0 6 4 15 1 12 7 2 10 9

4 13 1 8 7 2 14 11 15 10 12 3 9 5 0 6

6 5 8 11 13 14 3 0 9 2 4 1 10 7 15 12

1 11 7 2 8 13 4 14 6 12 10 15 3 0 9 5

S-box 4:

9 0 7 11 12 5 10 6 15 3 1 14 2 8 4 13

5 10 12 6 0 15 3 9 8 13 11 1 7 2 14 4

10 7 9 12 5 0 6 11 3 14 4 2 8 13 15 1

3 9 15 0 6 10 5 12 14 2 1 7 13 4 8 11

S-box 5:

5 15 9 10 0 3 14 4 2 12 7 1 13 6 8 11

6 9 3 15 5 12 0 10 8 7 13 4 2 11 14 1

15 0 10 9 3 5 4 14 8 11 1 7 6 12 13 2

12 5 0 6 15 10 9 3 7 2 14 11 8 1 4 13

S-box 6:

Page 251 of 666

Applied Cryptography: Second Edition - Bruce Schneier

4 3 7 10 9 0 14 13 15 5 12 6 2 11 1 8

14 13 11 4 2 7 1 8 9 10 5 3 15 0 12 6

13 0 10 9 4 3 7 14 1 15 6 12 8 5 11 2

1 7 4 14 11 8 13 2 10 12 3 5 6 15 0 9

S-box 7:

4 10 15 12 2 9 1 6 11 5 0 3 7 14 13 8

10 15 6 0 5 3 12 9 1 8 11 13 14 4 7 2

2 12 9 6 15 10 4 1 5 11 3 0 8 7 14 13

12 6 3 9 0 5 10 15 2 13 4 14 7 11 1 8

S-box 8:

13 10 0 7 3 9 14 4 2 15 12 1 5 6 11 8

2 7 13 1 4 14 11 8 15 12 6 10 9 5 0 3

4 13 14 0 9 3 7 10 1 8 2 11 15 5 12 6

8 11 7 14 2 4 13 1 6 5 9 0 12 15 3 10

Here is a method to use 48 additional key bits to generate S-boxes that are resistant to both linear and

differential cryptanalysis [165].

(1) Rearrange the DES S-boxes: 24673158.

(2) Select 16 of the remaining key bits. If the first bit is 1, swap the first two rows of S-box

1 with the last two rows of S-box 1. If the second bit is a 1, swap the first eight columns of S-box

1 with the second eight columns of S-box 1. Do the same to S-box 2 with the third and fourth

key bits. Do the same with S-boxes 3 through 8.

(3) Take the remaining 32 key bits. XOR the first four with every entry of S-box 1, the

second four with every entry of S-box 2 and so on.

The complexity of a differential cryptanalysis attack against this system is 251; the complexity of a

linear cryptanalysis attack is 253. The complexity of exhaustive search is 2102.

What is neat about this DES variant is that it can be implemented in existing hardware. Several DES

chip vendors sell DES chips with loadable S-boxes. This S-box generation method can be done outside

the chip and then loaded in. Differential and linear cryptanalysis require so much known or chosen

plaintext as to be unworkable, and a brute-force attack is inconceivable”with no speed penalties.

12.7 How Secure Is DES Today?

The answer is both easy and hard. The easy answer just looks at key length (see Section 7.1). A brute-

force DES-cracking machine that can find a key in an average of 3.5 hours cost only $1 million in

1993 [1597,1598]. DES is so widespread that it is na•ve to pretend that the NSA and its counterparts

haven™t built such a machine. And remember that cost will drop by a factor of 5 every 10 years. DES

will only become less secure as time goes on.

The hard answer tries to estimate cryptanalytic techniques. Differential cryptanalysis was known by

the NSA long before the mid-1970s, when DES first became a standard. It is na•ve to pretend that the

NSA theoreticians have been idle since then; almost certainly they have developed newer

cryptanalytic techniques that can be applied against DES. But there are no facts, only rumors.

Winn Schwartau writes that the NSA had built a massively parallel DES-cracking machine as early as

Page 252 of 666

Applied Cryptography: Second Edition - Bruce Schneier

the mid-1980s [1404]. At least one such machine was built by Harris Corp. with a Cray Y-MP as a

front end. Supposedly there are a series of algorithms that can reduce the complexity of a DES brute-

force search by several orders of magnitude. Contextual algorithms, based on the inner workings of

DES, can scrap sets of possible keys based on partial solutions. Statistical algorithms reduce the

effective key size even further. And other algorithms choose likely keys”words, printable ASCII, and

so on (see Section 8.1)”to test. The rumor is that the NSA can crack DES in 3 to 15 minutes,

depending on how much preprocessing they can do. And these machines cost only $50,000 each, in

quantity.

A different rumor is that if the NSA has a large amount of plaintext and ciphertext, its experts can

perform some kind of statistical calculation and then go out to an array of optical disks and retrieve

the key.

These are just rumors, but they don™t give me a warm, fuzzy feeling about DES. It has just been too

big a target for too long. Almost any change to DES will be more annoying; maybe the resultant

cipher will be easier to break, but the NSA might not have the resources to devote to the problem.

My recommendation is to use Biham™s construction for key-dependent S-boxes. It is easy to

implement in software and in hardware chips that have loadable S-boxes, and has no performance

penalty over DES. It increases the algorithm™s resistance to a brute-force attack, makes differential

and linear cryptanalysis harder, and gives the NSA something at least as strong as DES”but

different”to worry about.

Chapter 13

Other Block Ciphers

13.1 Lucifer

In the late 1960s, led by Horst Feistel and later by Walt Tuchman, IBM initiated a research program

in computer cryptography called Lucifer. Lucifer is also the name of a block algorithm that came out

of that program in the early 1970s [1482, 1484]. In fact, there are at least two different algorithms

with that name [552,1492]. And [552] leaves some gaps in the specification of the algorithm. All this

has led to more than a little confusion.

Lucifer is a substitution-permutation network, with building blocks similar to DES. In DES, the

output of the function f is XORed with the input of the previous round to form the input of the next

round. Lucifer™s S-boxes have 4-bit inputs and 4-bit outputs; the input of the S-boxes is the bit-

permuted output of the S-boxes of the previous round; the input of the S-boxes of the first round is

the plaintext. A key bit is used to choose the actual S-box from two possible S-boxes. (Lucifer

represents this as a single T-box with 9 bits in and 8 bits out.) Unlike DES, there is no swapping

between rounds and no block halves are used. Lucifer has 16 rounds, 128-bit blocks, and a key

schedule simpler than DES.

Using differential cryptanalysis against the first incarnation of Lucifer, Biham and Shamir [170, 172]

showed that Lucifer, with 32-bit blocks and 8 rounds, can be broken with 40 chosen plaintexts and

229 steps; the same attack can break Lucifer with 128-bit blocks and 8 rounds with 60 chosen

plaintexts and 253 steps. Another differential cryptanalytic attack breaks 18-round, 128-bit Lucifer

with 24 chosen plaintexts in 221 steps. All of these attacks used the strong DES S-boxes. Using

differential cryptanalysis against the second incarnation, they found the S-boxes to be much weaker

than DES. Further analysis showed that over half the possible keys are insecure [112]. Related-key

Page 253 of 666

Applied Cryptography: Second Edition - Bruce Schneier

cryptanalysis can break 128-bit Lucifer, with any number of rounds, with 2 33 chosen-key chosen

plaintexts, or with 265 chosen-key known plaintexts [158]. The second incarnation of Lucifer is even

weaker [170, 172, 112].

Some people feel that Lucifer is more secure than DES because of the longer key length and lack of

published results. This is clearly not the case.

Lucifer is the subject of several U.S. patents: [553, 554, 555, 1483]. They have all expired.

13.2 Madryga

W. E. Madryga proposed this block algorithm in 1984 [999]. It is efficient for software: It has no

irritating permutations and all its operations work on bytes.

His design objectives are worth repeating:

1. The plaintext cannot be derived from the ciphertext without using the key. (This just

means that the algorithm is secure.)

2. The number of operations required to determine the key from a sample of plaintext

and ciphertext should be statistically equal to the product of the operations in an encryption

times the number of possible keys. (This means that no plaintext attack should be better than

brute force.)

3. Knowledge of the algorithm should not defeat the strength of the cipher. (All the

security should rest in the key.)

4. A one-bit change of the key should produce a radical change in the ciphertext using the

same plaintext, and a 1-bit change of the plaintext should produce a radical change in the

ciphertext using the same key. (This is the avalanche effect.)

5. The algorithm should contain a noncommutative combination of substitution and

permutation.

6. The algorithm should include substitutions and permutations under the control of both

the input data and the key.

7. Redundant bit groups in the plaintext should be totally obscured in the ciphertext.

8. The length of the ciphertext should be the same length as the plaintext.

9. There should be no simple relationships between any possible keys and ciphertext

effects.

10. Any possible key should produce a strong cipher. (There should be no weak keys.)

11. The length of the key and the text should be adjustable to meet varying security

requirements.

12. The algorithm should be efficiently implementable in software on large mainframes,

minicomputers, and microcomputers, and in discrete logic. (In fact, the functions used in the

algorithm are limited to XOR and bit-shifting.)

DES had already met objectives one through nine, but the next three were new. Assuming that the

best way to break the algorithm was through brute force, a variable-length key would surely silence

those who thought 56 bits was too low. They could implement this algorithm with any key length they

desired. And, for anyone who has ever attempted to implement DES in software, an algorithm that

took software implementations into account would be welcomed.

Description of Madryga

Madryga consists of two nested cycles. The outer cycle repeats eight times (although this could be

increased if security warrants) and consists of an application of the inner cycle to the plaintext. The

Page 254 of 666

Applied Cryptography: Second Edition - Bruce Schneier

inner cycle transforms plaintext to ciphertext and repeats once for each 8-bit block (byte) of the

plaintext. Thus, the algorithm passes through the entire plaintext eight successive times.

An iteration of the inner cycle operates on a 3-byte window of data, called the working frame (see

Figure 13.1). This window advances 1 byte for each iteration. (The data are considered circular when

dealing with the last 2 bytes.) The first 2 bytes of the working frame are together rotated a variable

number of positions, while the last byte is XORed with some key bits. As the working frame advances,

all bytes are successively rotated and XORed with key material. Successive rotations overlap the

results of a previous XOR and rotation, and data from the XOR is used to influence the rotation. This

makes the entire process reversible.

Because every byte of data influences the 2 bytes to its left and the 1 byte to its right, after eight passes

every byte of the ciphertext is dependent on 16 bytes to the left and 8 bytes to the right.

When encrypting, each iteration of the inner cycle starts the working frame at the next-to-last byte of

the plaintext and advances circularly through to the third-to-last byte of the plaintext. First, the entire

key is XORed with a random constant and then rotated to the left 3 bits. The low-order 3 bits of the

low-order byte of the working frame are saved; they will control the rotation of the other 2 bytes.

Then, the low-order byte of the working frame is XORed with the low-order byte of the key. Next, the

concatenation of the 2 high-order bytes are rotated to the left the variable number of bits (0 to 7).

Finally, the working frame is shifted to the right 1 byte and the whole process repeats.

Figure 13.1 One iteration of Madryga.

The point of the random constant is to turn the key into a pseudo-random sequence. The length of this

constant must be equal to the length of the key and must be the same for everyone who wishes to

communicate with one another. For a 64-bit key, Madryga recommends the constant

0x0f1e2d3c4b5a6978.

Decryption reverses this process. Each iteration of the inner cycle starts the working frame at the

third-to-last byte of the ciphertext and advances in the reverse direction circularly through to the

second-to-last byte of the ciphertext. Both the key and the 2 ciphertext bytes are shifted to the right.

And the XOR is done before the rotations.

Cryptanalysis of Madryga

Researchers at Queensland University of Technology [675] examined Madryga, along with several

other block ciphers. They observed that the algorithm didn™t exhibit the plaintext-ciphertext

avalanche effect. Additionally, many ciphertexts had a higher percentage of ones than zeros.

Although I know of no formal analysis of the algorithm, it doesn™t look terribly secure. A cursory

Page 255 of 666

Applied Cryptography: Second Edition - Bruce Schneier

review by Eli Biham led to the following observations [160]:

The algorithm consists only of linear operations (rotations and XOR), which are slightly

modified depending on the data.

There is nothing like the strength of DES™s S-boxes.

The parity of all the bits of the plaintext and the ciphertext is a constant, depending only

on the key. So, if you have one plaintext and its corresponding ciphertext, you can predict

the parity of the ciphertext for any plaintext.

None of this is damning in itself, but it doesn™t leave me with a good feeling about the algorithm. I do

not recommend Madryga.

13.3 NewDES

NewDES was designed in 1985 by Robert Scott as a possible DES replacement [1405, 364]. The

algorithm is not a DES variant, as its name might imply. It operates on 64-bit blocks of plaintext, but

it has a 120-bit key. NewDES is simpler than DES, with no initial or final permutations. All operations

are on entire bytes. (Actually, NewDES isn™t anything like a new version of DES; the name is

unfortunate.)

The plaintext block is divided into eight 1-byte sub-blocks: B0, B1,..., B6, B7. Then the sub-blocks go

through 17 rounds. Each round has eight steps. In each step, one of the sub-blocks is XORed with

some key material (there is one exception), substituted with another byte via an f function, and then

XORed with another sub-block to become that sub-block. The 120-bit key is divided into 15 key sub-

blocks: K0, K1,..., K13, K14. The process is easier to understand visually than to describe. Figure 13.2

shows the NewDES encryption algorithm.

The f-function is derived from the Declaration of Independence. See [1405] for details.

Scott showed that every bit of the plaintext block affects every bit of the ciphertext block after only 7

rounds. He also analyzed the f function and found no obvious problems. NewDES has the same

complementation property that DES has [364]: If EK(P) = C, then EK´(P´) = C´. This reduces the work

required for a brute-force attack from 2120 steps to 2119 steps. Biham noticed that any change of a full

byte, applied to all the key and data bytes, leads to another complementation property [160]. This

reduces a brute-force attack further to 2112 steps.

Page 256 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Figure 13.2 NewDES.

This is not damning, but Biham™s related-key cryptanalytic attack can break NewDES with 233

chosen-key chosen-plaintexts in 248 steps [160]. While this attack is time-consuming and largely

theoretical, it shows that NewDES is weaker than DES.

13.4 FEAL

FEAL was designed by Akihiro Shimizu and Shoji Miyaguchi from NTT Japan [1435]. It uses a 64-bit

block and a 64-bit key. The idea was to make a DES-like algorithm with a stronger round function.

Needing fewer rounds, the algorithm would run faster. Unfortunately, reality fell far short of the

design goals.

Description of FEAL

Figure 13.3 is a block diagram of one round of FEAL. The encryption process starts with a 64-bit

block of plaintext. First, the data block is XORed with 64 key bits. The data block is then split into a

left half and a right half. The left half is XORed with the right half to form a new right half. The left

and new right halves go through n rounds (four, initially). In each round the right half is combined

with 16 bits of key material (using function f) and XORed with the left half to form the new right half.

The original right half (before the round) forms the new left half. After n rounds (remember not to

switch the left and right halves after the nth round) the left half is again XORed with the right half to

form a new right half, and then the left and right halves are concatenated together to form a 64-bit

whole. The data block is XORed with another 64 bits of key material, and the algorithm terminates.

Figure 13.3 One round of FEAL.

Function f takes the 32 bits of data and 16 bits of key material and mixes them together. First the data

block is broken up into 8-bit chunks, then the chunks are XORed and substituted with each other.

Figure 13.4 is a block diagram of function f. The two functions S0 and S1, are defined as:

Page 257 of 666

Applied Cryptography: Second Edition - Bruce Schneier

S0(a,b) = rotate left two bits ((a + b) mod 256)

S1(a,b) = rotate left two bits ((a + b + 1) mod 256)

The same algorithm can be used for decryption. The only difference is: When decrypting, the key

material must be used in the reverse order.

Figure 13.5 is a block diagram of the key-generating function. First the 64-bit key is divided into two

halves. The halves are XORed and operated on by function fk, as indicated in the diagram. Figure

13.6 is a block diagram of function fk. The two 32-bit inputs are broken up into 8-bit blocks and

combined and substituted as shown. S0 and S1 are defined as just shown. The 16-bit key blocks are

then used in the encryption/decryption algorithm.

On a 10 megahertz 80286 microprocessor, an assembly-language implementation of FEAL-32 can

encrypt data at a speed of 220 kilobits per second. FEAL-64 can encrypt data at a speed of 120

kilobits per second [1104].

Figure 13.4 Function f.

Figure 13.5 Key processing part of FEAL.

Page 258 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Figure 13.6 Function fK.

Cryptanalysis of FEAL

FEAL-4, FEAL with four rounds, was successfully cryptanalyzed with a chosen-plaintext attack in

[201] and later demolished [1132]. This later attack, by Sean Murphy, was the first published

differential-cryptanalysis attack and required only 20 chosen plaintexts. The designers retaliated with

8-round FEAL [1436,1437,1108] which Biham and Shamir cryptanalyzed at the SECURICOM ™89

conference[1427]. Another chosen-plaintext attack, using only 10,000 blocks, against FEAL-8 [610]

forced the designers to throw up their hands and define FEAL-N [1102,1104], with a variable number

of rounds (greater than 8, of course).

Biham and Shamir used differential cryptanalysis against FEAL-N; they could break it more quickly

than by brute force (with fever than 264 chosen plaintext encryptions) for N less than 32 [169]. FEAL-

16 required 228 chosen plaintexts or 246.5 known plaintexts to break. FEAL-8 required 2000 chosen

plaintexts or 237.5 known plaintexts to break. FEAL-4 could be broken with just eight carefully

selected chosen plaintexts.

The FEAL designers also defined FEAL-NX, a modification of FEAL, that accepts 128-bit keys (see

Figure 13.7)[1103,1104]. Biham and Shamir showed that FEAL-NX with a 128-bit key is just as easy

to break as FEAL-N with a 64-bit key, for any value of N [169]. Recently FEAL-N(X)S has been

proposed, which strengthens FEAL with a dynamic swapping function [1525].

There™s more. Another attack against FEAL-4, requiring only 1000 known plaintexts, and against

FEAºL-8, requiring only 20,000 known plaintexts, was published in [1520]. Other attacks are in

[1549,1550]. The best attack is by Mitsuru Matsui and Atshuiro Yamagishi [1020]. This is the first use

of linear cryptanalysis, and can break FEAL-4 with 5 known plaintexts, FEAL-6 with 100 known

plaintexts and FEAL-8 with 215 known plaintexts. Further refinements are in [64]. Differential-linear

cryptanalysis can break FEAL-8 with only 12 chosen plaintexts [62]. Whenever someone discovers a

new cryptanalytic attack, he always seems to try it out on FEAL first.

Patents

FEAL is patented in the United States [1438] and has patents pending in England, France, and

Germany. Anyone wishing to license the algorithm should contact the Intellectual Property

Department, NTT, 1-6 Uchisaiwai-cho, 1-chome, Chiyoda-ku, 100 Japan.

13.5 REDOC

REDOC II is another block algorithm, designed by Michael Wood for Cryptech, Inc. [1613,400]. It

has a 20-byte (160-bit) key and an 80-bit block.

REDOC II performs all of its manipulations”permutations, substitutions, and key XORs”on bytes;

the algorithm is efficient in software. REDOC II uses variable function tables. Unlike DES, which has

a fixed (albeit optimized for security) set of permutation and substitution tables, REDOC II uses a

key-dependent and plaintext-dependent set of tables (S-boxes, actually). REDOC II has 10 rounds;

each round is a complicated series of manipulations on the block.

Page 259 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Figure 13.7 FEAL-NX key schedule.

Another unique feature in the design is the use of masks. These are numbers derived from the key

table that are used to select the tables in a given function within a given round. Both the value of the

data and the masks are used together to select the function tables.

Assuming that brute force is the most efficient means of attack, REDOC II is very secure: 2160

operations are required to recover the key. Thomas Cusick cryptanalyzed 1 round of REDOC II, but

he was unable to extend the attack to multiple rounds [400]. Using differential cryptanalysis, Biham

and Shamir were able to successfully cryptanalyze 1 round of REDOC II with 2300 chosen-plaintexts

[170]. This attack cannot be extended to multiple rounds, but they were able to obtain three mask

values after 4 rounds. I know of no other cryptanalysis.

REDOC III

REDOC III is a streamlined version of REDOC II, also designed by Michael Wood [1615]. It operates

on an 80-bit block. The key length is variable and can be as large as 2560 bytes (20, 480 bits). The

algorithm consists solely of XORing key bytes with message bytes; there are no permutations or

substitutions.

(1) Create a key table of 256 10-byte keys, using the secret key.

(2) Create two 10-byte mask blocks, M1 and M2. M1 is the XOR of the first 128 10-byte

keys; M2 is the XOR of the second 128 10-byte keys.

(3) To encrypt a 10-byte block:

(a) XOR the first byte of the data block with the first byte of M1. Select a key from

the key table computed in step (1). Use the computed XOR as the index into the table.

XOR each byte in the data block with the corresponding byte in the chosen key, except for

the first data byte.

(b) XOR the second byte of the data block with the second byte of M1. Select a key

Page 260 of 666

Applied Cryptography: Second Edition - Bruce Schneier

from the key table computed in step (1). Use the computed XOR as the index into the

table. XOR each byte in the data block with the corresponding byte in the chosen key,

except for the second data byte.

(c) Continue with the entire block (bytes 3 through 10), until each byte has been

used to select a key from the key table after XORing it with the corresponding M1 value.

Then XOR each byte with the key except for the byte used to select the key.

(d) Repeat steps (a) through (c) with M2.

The algorithm is easy and fast. On a 33 megahertz 80386, the algorithm encrypts data at 2.75

megabits per second. Wood estimates that a VLSI-pipelined design, with a 64-bit data path, woud

encrypt data at over 1.28 gigabits per second with a 20 megahertz clock.

REDOC III is not secure [1440]. It is vulnerable to differential cryptanalysis. Only about 223 chosen

plaintexts are required to reconstruct both masks.

Patents and Licenses

Both REDOC versions are patented in the United States [1614]. Foreign patents are pending. Anyone

interested in licensing either REDOC II or REDOC III should contact Michael C. Wood, Delta

Computec, Inc., 6647 Old Thompson Rd., Syracuse, NY 13211.

13.6 LOKI

LOKI is Australian and was first presented in 1990 as a potential alternative to DES [273]. It uses a

64-bit block and a 64-bit key. The general structure of the algorithm and key schedule were based on

[274, 275], and the design of the S-boxes was based on [1247].

Using differential cryptanalysis, Biham and Shamir were able to break LOKI with 11 or fewer rounds

faster than by brute force [170]. Furthermore, there is an 8-bit complementation property, which

reduces the complexity of a brute-force attack by a factor of 256 [170, 916, 917].

Lars Knudsen showed that LOKI, with 14 rounds or fewer, is vulnerable to differential cryptanalysis

[852, 853]. Additionally, if LOKI is implemented with alternate S-boxes, the resulting cipher will

probably be vulnerable to differential cryptanalysis.

LOKI91

In response to these attacks, LOKI™s designers went back to the drawing board and revised their

algorithm. The result is LOKI91 [272]. (The previous version of LOKI was renamed LOKI89.)

To make the algorithm more resistant to differential cryptanalysis and to remove the

complementation property, the following changes were made to the original design:

1. The subkey generation algorithm was changed so that the halves were swapped every

second round, not every round.

2. The subkey generation algorithm was changed so that the rotation of the left subkey

alternated between 12 and 13 bits to the left.

3. The initial and final XOR of the block with the key were eliminated.

4. The S-box function was altered to flatten out their XOR profile (to improve their

resistance to differential cryptanalysis), and to eliminate any value of x such that f(x) = 0, where

f is the combination of the E-, S-, and P-boxes.