4 29

238

8 214

2

244

9 224 232t

214 215

243

10 224

11 231 2

247 232t

221 221

247

12 231

2

252

13 239 232t

229

14 229

251

239

27 237

256

15 247

236 237

255

16 247

+Thecomplexity of the analysis can be greatly reduced for these variants by

using about four times as many plaintexts with the clique method.

the number of those plaintexts actually analyzed. The last column is the complex-

ity of analysis, after the required plaintexts are found.

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

be converted to a known plaintext attack, but that requires 255known plaintexts.

And 237DES 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 [ 1721.

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 264chosen plaintexts: Remem-

ber, DES has a 64-bit block size, so it only has 264possible plaintext blocks. (In gen-

eral, 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 enor-

mous 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 crypt-

Page 290

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12.4 Differential and Linear Cryptanalysis

XOR of some of the key bits. This is a linear approximation and will hold with some

probability p. If p # %, 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 l-round lin-

ear approximations and join them together. (Again, ignore the initial and final per-

mutations; they don™t affect the attack.) 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- l), 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 %, or a bias of %, 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

X

E(X) 4

K1,26

a26

S-Boxes

c17˜c18˜c19.c20

Figure 12.8 A 1-round linear ap-

proximation for DES.

Page 291

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER12 Data Encryption Standard (DES)

operations, and brute force requires 255).The consensus

analytic attack requires 255.1

is that DES, when implemented properly, is still secure against differential crypt-

analysis.

Why is DES so resistant to differential cryptanalysis? Why are the S-boxes opti-

mized to make this 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 Copper-

smith recently wrote [373,374]:

The design took advantageof certain cryptanalytic techniques, most prominently

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

lished 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 advantagethe United Statesenjoyed 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 [ 14261.

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 exam-

ines the difference between keys. The attack is different from any previously dis-

cussed: 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 2” chosen-key chosen plain-

texts or 233chosen-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

Page 292

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

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 212linear cryptanalyses in parallel and picking

the correct one based on probabilities. This recovers the 12 bits plus the bz6, 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 [ 10181. 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 some-

thing 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,8 111,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 cryptanaly-

sis 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 differen-

tial 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

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

attacks, it 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:

Page 293

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER12 Data Encryption Standard (DES)

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 czo.We can trace b16backwards from the input to the S-box. The

bit az6 is XORed with a bit from the subkey Ki,26 to obtain bz6. And bit Xi7 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, Ys, Yi4, and

Yz5.This means that with probability % - %6:

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

discussed under differential cryptanalysis. Figure 12.9 is a &round approximation

with a probability of !4 + .006 1. 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 l-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 247known plaintext blocks, and will result in 1 key bit. That™s not very use-

ful. 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.

17

B

Ki-1.26

11

G= B

2

4+ I. 26

17

A

[8, 14, 251

A = [3, 8, 14, 251 B=

With Probability & + 6.1 x 10e3

Figure 12.9 A 3-round linear approximation for DES.

Page 294

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Encipher

Decipher

Figure 12.10 Triple-DES.

DES with Independent Subkeys

Another variation is to use a different subkey for each round, instead of generat-

ing them from a single 56-bit key (8511. 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 algo-

rithm; 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 suscepti-

ble to differential cryptanalysis and can be broken with 261chosen plaintexts (see

Table 12.15) [ 167,172]. It would seem that any modification of the key schedule can-

not 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

(21z0)/noperations with n known plaintexts. It also improves security against differ-

ential and linear cryptanalysis; the attacks require 261 chosen plaintexts and 260

known plaintexts, respectively [ 13381.

Page 295

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER12 Data Encryption Standard (DES)

- 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 technol-

w.Y.1

- 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 dif-

fer in at least 2 bits.

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

puts 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 round i + 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) [.%I. Since DES is

not a group, then the resultant ciphertext is much harder to break using exhaustive

search: 211™ attempts instead of 256attempts. See Section 15.2 for more details.

Page 296

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12.6 DES Variants

Plaintext J

K2

4

I J 1 I 1.. I I I

J 1

1

1 Ciphertext]

Figure 12.11 GDES.

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

plaintexts required for differential cryptanalysis. One change not listed, combining

the left and right halves using addition mod 24 instead of XOR, is 217times 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 215pos-

sible instances, and that the variant is not resistant to differential cryptanalysis

[8 16,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

Page 297

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12 Data Encryption Standard (DES)

CHAPTER

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 dif-

ference between CRYPT(3) and DES is that CRYPT(3) has a key-dependent expansion

permutation with 2” 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 LJ32-bit sub-blocks; the exact

number depends on the total block size (this was variable in the design, but must be

fixed for each implementation). In general, 4 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 vari-

able 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 LJ= 2 and n = 16, this is DES.

Biham and Shamir [ 167,168] showed that, using differential cryptanalysis, GDES

with 4 = 8 and n = 16 is breakable with only six chosen plaintexts. If independent

subkeys are also used, 16 chosen plaintexts are required. GDES with 4 = 8 and n =

22 is breakable with 48 chosen plaintexts, and GDES with 4 = 8 and n = 31 requires

only 500,000 chosen plaintexts to break. Even GDES with 4 = 8 and n = 64 is weaker

than DES; 249chosen 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 them-

selves. 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 23*steps. . . . DES with random S-boxesis shown to be

very easy to break. Even a minimal changeof 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 bet-

ter S-boxes than the ones that come with DES, but blindly choosing new S-boxes

isn™t a good idea.

Page 298

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12.6 DES Variants

Table 12.16

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

S-box 1:

8 12 6 1 15 2 5

13 14 0 3 10 4 7 9 11

3 10 6

8 2 11 13 4 1 5 15 0 9 12

14 7

6 15 11 12 1 2

14 9 3 10 0 7 13 4 8 5

5 10 12 0 15 9

1 4 14 7 11 13 8 2 6 3

S-box 2:

15 8 3 1 13 7

14 4 2 9 5 0 11 10 6 12

6 15 9 4 11 14 2 1 7

5 3 12 10 0 13 8

9 14 5 6 13 1 11 12 0

8 2 4 15 3 10 7

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 06 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 7 15 12

13 14 30 9 2 4 1 10

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 4 13

10 6 15 3 1 14 2 8

5 10 12 6 0 15 39 2 14 4

8 13 11 1 7

10 79 12 5 0 8 13 15 1

6 11 3 14 4 2

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 93 15 5 12 010 8 7 13 4 2 11 14 1

15 0 10 4 14 6 12 13 2

9 3 5 8 11 1 7

12 50 2 14 11 8 1

6 15 10 93 7 4 13

S-box 6:

4 3 7 10 9 5 12 6

0 14 13 15 2 11 1 8

14 13 11 0 12 6

4 2 7 18 9 10 5 3 15

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

14 11

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

S-box 7:

4 10 15 12 2 9 16 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 41 7 14 13

5 11 3 0 8

12 6 3 10 15

9 0 5 4 14 7 11 1 8

2 13

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 710 1 8 2 11 15 5 12 6

8 11 7 14 2 0 12 15

4 13 1 6 5 9 3 10

Page 299

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12 Data Encryption Standard (DES)

CHAPTER

Table 12.15

Differential Cryptanalysis Attacks against DES Variants

Modified Operation Chosen Plaintexts

Full DES (no modification) 247

Cannot strengthen

P permutation

219

Identity permutation

Order of S-boxes 238

239 231

Replace XORs by additions t

S-boxes:

2™8-220

Random

233-241

Random permutations

233

One entry

226

Uniform tables

Elimination of the E Expansion 226

Order of E and subkey XOR 244

GDES (width q = 8):

6, 16

16 rounds

64 rounds 249(independent key)

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 cryptanaly-

sis [ 11361. Presumably RDES-2 and greater are as well.

s”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 [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 [ 1651.The group went back to their

computers and developed better techniques for S-box design [835,837]. They pro-

posed 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 composi-

tion of the S-boxes. If the S-boxes are key-dependent and chosen by a cryptographi-

cally strong method, then linear and differential cryptanalysis are much more

difficult. Remember though, that randomly generated S-boxes have very poor differ-

ential and linear characteristics; even if they are secret.

Page 300

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12.6 DES Variants

A different rumor is that if the NSA has a large amount of plaintext and cipher-

text, 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.

Page 301

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12 Data Encryption Standard (DES)

CHAPTER

Here is a method to use 48 additional key bits to generate S-boxes that are resis-

tant to both linear and differential cryptanalysis [ 16.51.

(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 21°2.

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. Differen-

tial 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.

How Is DES

12.7 SECURE TODAY?

The answer is both easy and hard. The easy answer just looks at key length (see Sec-

tion 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

naive 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 crypt-

analysis was known by the NSA long before the mid-1970s when DES first became

a standard. It is naive 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 the mid-1980s [ 14041. 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 algo-

rithms 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.