<<

. 11
( 29)



>>

Because of the way the initial key is modified to get a subkey for each round of the algorithm, certain
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.


<<

. 11
( 29)



>>