<<

. 2
( 2)



Rounds Plaintexts
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.

<<

. 2
( 2)