ńňđ. 1 |

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 12 ............................................... 265

Data Encryption Standard (DES) .............. 265

BACKGROUND ....................................... 265

Development the Standard ........................... 265

Adoption the Standard .................................. 267

Validation and Certification of DES ................ 268

DESCRIPTION OF .................................. 270

Outline the Algorithm .................................... 270

Figure 12.1 DES ............................................ 271

The lnitiaf Permutation .................................. 271

The Key Transformation ............................... 272

Table 12.1 Initial Permutation ...................... 272

Table 12.2 Key Permutation ........................ 273

The Expansion Permutation .......................... 273

Table 12.3 Number of Key Bits Shifted ......... 273

Table 12.4 Compression Permutation ......... 274

The S-Box Substitution ................................. 274

Table 12.5 Expansion Permutation .............. 275

The P-Box Permutation ................................. 275

Table 12.6 S-Boxes ..................................... 276

Table 12.7 P-Box Permutation ..................... 277

The Final Permutation ................................... 277

Decrypting DES ............................................ 277

Modes DES ................................................... 277

Table 12.8 Final Permutation ....................... 277

Hardware and Software Implementations ...... 278

SECURITY OF DES ................................ 278

Table 12.9 Commercial DES Chips ............. 279

Table 12.10 DES Speeds on Different .......... 279

Weak Keys .................................................... 280

Table 12.11 DES Weak Kevs ...................... 281

Complement Keys ......................................... 281

Table 12.12 DES Semiweak Key Pairs ........ 281

Table 12.13 DES Possibly Weak Keys ........ 282

Algebraic Structure ....................................... 282

Key Length .................................................... 283

Design the S-Boxes ...................................... 284

Number of Rounds ......................................... 284

Additional Results ......................................... 285

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

DIFFERENTIAL AND CRYPTANALYSIS . 285

Differentiaf Cryptanalysis .............................. 285

Figure 12.5 DES rond function ....................... 286

Figure 12.6 DES Characteristics .................... 287

Figure 12.7 A two-round DES Character ....... 288

Table 12.14 Differential Cryptanalysis .......... 289

Related-Key Cryptanalysis ............................ 291

Linear Cryptanalysis ..................................... 291

Future Directions ........................................... 292

THE REAL DESIGN CRITERIA ............... 292

DES with Independent Subkeys ................... 294

DESX ............................................................ 294

DES VARIANTS ....................................... 295

Multiple DES ................................................. 295

CRYpT(3) ...................................................... 297

Generalized DES .......................................... 297

DES with Alternate S-Boxes ......................... 297

Table 12.16 s3DES S-Boxes (with S-box ..... 298

Table 12.15 Differential Cryptanalysis .......... 299

sDES ............................................................ 299

DES with Key-Dependent S-Boxes ............... 299

SECURE TODAY? ................................... 301

Page 265

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12

CHAPTER

Data Encryption

Standard (DES)

12.1 BACKGROUND

The Data Encryption Standard (DES), known as the Data Encryption Algorithm

(DEA) by ANSI and the DEA-1 by the ISO, has been a worldwide standard for 20

years. Although it is showing signs of old age, it has held up remarkably well against

years of cryptanalysis and is still secure against all but possibly the most powerful

of adversaries.

of the Standard

Development

In the early 1970s nonmilitary cryptographic research was haphazard. Almost no

research papers were published in the field. Most people knew that the military used

special coding equipment to communicate, but few understood the science of cryp-

tography. The National Security Agency (NSA) had considerable knowledge, but

they did not even publicly admit their own existence.

Buyers didnâ€™t know what they were buying. Several small companies made and

sold cryptographic equipment, primarily to overseas governments. The equipment

was all different and couldnâ€™t interoperate. No one really knew if any of it was

secure; there was no independent body to certify the security. As one government

report said [441]:

The intricacies of relating key variations and working principles to the real

strength of the encryption/decryption equipment were, and are, virtually

unknown to almost all buyers, and informed decisions as to the right type of on-

line, off-line, key generation, etc., which will meet buyersâ€™ security needs, have

been most difficult to make.

In 1972, the National Bureau of Standards (NBS), now the National Institute of

Standards and Technology (NIST), initiated a program to protect computer and com-

munications data. As part of that program, they wanted to develop a single, standard

Page 266

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER12 Data Encryption Standard (DES)

cryptographic algorithm. A single algorithm could be tested and certified, and dif-

ferent cryptographic equipment using it could interoperate. It would also be cheaper

to implement and readily available.

In the May 15, 1973 Federal Register, the NBS issued a public request for propos-

als for a standard cryptographic algorithm. They specified a series of design criteria:

- The algorithm must provide a high level of security.

- The algorithm must be completely specified and easy to understand.

- The security of the algorithm must reside in the key; the security

should not depend on the secrecy of the algorithm.

- The algorithm must be available to all users.

- The algorithm must be adaptable for use in diverse applications.

- The algorithm must be economically implementable in electronic

devices.

- The algorithm must be efficient to use.

- The algorithm must be able to be validated.

- The algorithm must be exportable.

Public response indicated that there was considerable interest in a cryptographic

standard, but little public expertise in the field. None of the submissions came close

to meeting the requirements.

The NBS issued a second request in the August 27, 1974 Federal Register. Even-

tually they received a promising candidate: an algorithm based on one developed by

IBM during the early 1970s called Lucifer (see Section 13.1). IBM had a team work-

ing on cryptography at both Kingston and Yorktown Heights, including Roy Adler,

Don Coppersmith, Horst Feistel, Edna Grossman, Alan Konheim, Carl Meyer, Bill

Notz, Lynn Smith, Walt Tuchman, and Bryant Tuckerman.

The algorithm, although complicated, was straightforward. It used only simple

logical operations on small groups of bits and could be implemented fairly effi-

ciently in hardware.

The NBS requested the NSAâ€™s help in evaluating the algorithmâ€™s security and

determining its suitability as a federal standard. IBM had already filed for a patent

[5 141,but was willing to make its intellectual property available to others for man-

ufacture, implementation, and use. Eventually, the NBS worked out the terms of

agreement with IBM and received a nonexclusive, royalty-free license to make, use,

and sell equipment that implemented the algorithm.

Finally, in the March 17, 1975 Federal Register, the NBS published both the

details of the algorithm and IBMâ€™s statement granting a nonexclusive, royalty-free

license for the algorithm, and requested comment [536]. Another notice, in the

August 1, 1975 Federal Register, again requested comments from agencies and the

general public.

And there were comments [721,497,1120]. Many were wary of the NSAâ€™s â€śinvisi-

ble handâ€ť in the development of the algorithm. They were afraid that the NSA had

Page 267

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12.1 Background

modified the algorithm to install a trapdoor. They complained that the NSA reduced

the key size from the original 128-bits to 56-bits (see Section 13.1). They complained

about the inner workings of the algorithm. Much of NSAâ€™s reasoning became clear

in the early 1990s but in the 1970s this seemed mysterious and worrisome.

In 1976, the NBS held two workshops to evaluate the proposed standard. The

first workshop discussed the mathematics of the algorithm and the possibility of a

trapdoor [ 11391. The second workshop discussed the possibility of increasing the

algorithmâ€™s key length [229]. The algorithmâ€™s designers, evaluators, implementors,

vendors, users, and critics were invited. From all reports, the workshops were

lively [1118].

Despite criticism, the Data Encryption Standard was adopted as a federal standard

on November 23, 1976 [229] and authorized for use on all unclassified govern-

ment communications. The official description of the standard, FIPS PUB 46, â€śData

Encryption Standard,â€ť was published on January 1.5, 1977 and became effective six

months later [1140]. FIPS PUB 81, â€śDES Modes of Operation,â€ť was published in

1980 [1143]. FIPS PUB 74, â€śGuidelines for Implementing and Using the NBS Data

Encryption Standard,â€ť was published in 198 1 [ 11421. NBS also published FIPS PUB

112, specifying DES for password encryption [1144], and FIPS PUB 113, specifying

DES for computer data authentication [1145]. (FIPS stands for Federal Information

Processing Standard.)

These standards were unprecedented. Never before had an NSA-evaluated algo-

rithm been made public. This was probably the result of a misunderstanding

between NSA and NBS. The NSA thought DES was hardware-only. The standard

mandated a hardware implementation, but NBS published enough details so that

people could write DES software. Off the record, NSA has characterized DES as one

of their biggest mistakes. If they knew the details would be released so that people

could write software, they would never have agreed to it. DES did more to galvanize

the field of cryptanalysis than anything else. Now there was an algorithm to study:

one that the NSA said was secure. It is no accident that the next government stan-

dard algorithm, Skipjack (see Section 13.12), was classified.

of the Standard

Adoption

The American National Standards Institute (ANSI) approved DES as a private-

sector standard in 1981 (ANSI X3.92) [50]. They called it the Data Encryption Algo-

rithm (DEA). ANSI published a standard for DEA modes of operation (ANSI X3.106)

[52], similar to the NBS document, and a standard for network encryption that uses

DES (ANSI X3.105) [51].

Two other groups within ANSI, representing retail and wholesale banking, devel-

oped DES-based standards. Retail banking involves transactions between financial

institutions and private individuals, and wholesale banking involves transactions

between financial institutions.

ANSIâ€™s Financial Institution Retail Security Working Group developed a standard

for the management and security of PINS (ANSI X9.8) [53] and another DES-based

standard for the authentication of retail financial messages (ANSI X9.19) [56]. The

group has a draft standard for secure key distribution (ANSI X9.24) [58].

Page 268

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER12 Data Encryption Standard (DES)

ANSIâ€™s Financial Institution Wholesale Security Working Group developed its

own set of standards for message authentication (ANSI X9.9) [54], key management

(ANSI X9.17) [55,1151], encryption (ANSI X9.23) [57], and secure personal and node

authentication (ANSI X9.26) [59].

The American Bankers Association develops voluntary standards for the financial

industry. They published a standard recommending DES for encryption [l], and

another standard for managing cryptographic keys [2].

Before the Computer Security Act of 1987, the General Services Administration

(GSA) was responsible for developing federal telecommunications standards. Since

then, that responsibility transferred to NIST. The GSA published three standards

that used DES: two for general security and interoperability requirements (Federal

Standard 1026 [662] and Federal Standard 1027 [663]), and one for Group 3 facsimile

equipment (Federal Standard 1028) [664].

The Department of the Treasury wrote policy directives requiring that all

electronic-funds transfer messages be authenticated with DES [468,470]. They also

wrote DES-based criteria that all authentication devices must meet [469].

The IS0 first voted to approve DES-they called it the DEA-l-as an interna-

tional standard, then decided not to play a role in the standardization of cryptogra-

phy. However, in 1987 the International Wholesale Financial Standards group of IS0

used DES in an international authentication standard [758] and for key management

[761]. DES is also specified in an Australian banking standard [1497].

Validation and Certification of DES Equipment

As part of the DES standard, NIST validates implementations of DES. This vali-

dation confirms that the implementation follows the standard. Until 1994, NIST

only validated hardware and firmware implementations-until then the standard

prohibited software implementations. As of March 1995, 73 different implementa-

tions had been validated.

NIST also developed a program to certify that authentication equipment conformed

to ANSI X9.9 and FIPS 113. As of March, 1995, 33 products had been validated. The

Department of the Treasury has an additional certification procedure. NIST also has

a program to confirm that equipment conforms to ANSI X9.17 for wholesale key

management [ 115 11;four products have been validated as of March, 1995.

1987

The terms of the DES standard stipulate that it be reviewed every five years. In

1983 DES was recertified without a hitch. In the March 6, 1987 Federal Register,

NBS published a request for comments on the second five-year review. NBS offered

three alternatives for consideration [1480,1481]: reaffirm the standard for another

five years, withdraw the standard, or revise the applicability of the standard.

NBS and NSA reviewed the standard. NSA was more involved this time. Because

of an executive directive called NSDD-145, signed by Reagan, NSA had veto power

over the NBS in matters of cryptography. Initially, the NSA announced that it would

not recertify the standard. The problem was not that DES had been broken, or even

that it was suspected of having been broken. It was simply increasingly likely that

it would soon be broken.

Page 269

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

In its place, the NSA proposed the Commercial COMSEC Endorsement Program

(CCEP), which would eventually provide a series of algorithms to replace DES [SS].

These NSA-designed algorithms would not be made public, and would only be avail-

able in tamper-proof VLSI chips (see Section 25.1).

This announcement wasnâ€™t well received. People pointed out that business

(especially the financial industry) uses DES extensively, and that no adequate

alternative is available. Withdrawal of the standard would leave many organiza-

tions with no data protection. After much debate, DES was reaffirmed as a U.S.

government standard until 1992 [ 11411. According to the NBS, DES would not be

certified again [ 14801.

1993

Never say â€śnot.â€ť In 1992, there was still no alternative for DES. The NBS, now

called NIST, again solicited comments on DES in the Federal Register 15401:

The purpose of this notice is to announce the review to assess the continued ade-

quacy of the standard to protect computer data. Comments from industry and the

public are invited on the following alternatives for FIPS 46-l. The costs (impacts)

and benefits of these alternatives should be included in the comments:

-Reaffirm the standard for another five (5) years. The National Institute of

Standards and Technology would continue to validate equipment that imple-

ments the standard. FIPS 46- 1 would continue to be the only approved method

for protecting unclassified computer data.

-Withdraw the standard. The National Institute of Standards and Technology

would no longer continue to support the standard. Organizations could con-

tinue to utilize existing equipment that implements the standard. Other stan-

dards could be issued by NIST as a replacement for the DES.

-Revise the applicability and/or implementation statements for the standard.

Such revisions could include changing the standard to allow the use of imple-

mentations of the DES in software as well as hardware; to allow the iterative

use of the DES in specific applications; to allow the use of alternative algo-

rithms that are approved and registered by NIST.

The comment period closed on December 10, 1992. According to Raymond Kam-

mer, then the acting director of NIST [8 131:

Last year, NIST formally solicited comments on the recertification of DES. After

reviewing those comments, and the other technical inputs that I have received, I

plan to recommend to the Secretary of Commerce that he recertify DES for

another five years. I also plan to suggest to the Secretary that when we announce

the recertification we state our intention to consider alternatives to it over the

next five years. By putting that announcement on the table, we hope to give peo-

ple an opportunity to comment on orderly technological transitions. In the mean-

time, we need to consider the large installed base of systems that rely upon this

proven standard.

Even though the Office of Technology Assessment quoted NISTâ€™s Dennis

Branstead as saying that the useful lifetime of DES would end in the late 1990s

Page 270

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER12 Data Encryption Standard (DES)

[ 11911, the algorithm was recertified for another five years [ 11501. Software imple-

mentations of DES were finally allowed to be certified.

Anyone want to guess what will happen in 19982

12.2 DES

DESCRIPTION OF

DES is a block cipher; it encrypts data in 64-bit blocks. A 64-bit block of plaintext

goes in one end of the algorithm and a 64-bit block of ciphertext comes out the other

end. DES is a symmetric algorithm: The same algorithm and key are used for both

encryption and decryption (except for minor differences in the key schedule).

The key length is 56 bits. (The key is usually expressed as a 64-bit number, but

every eighth bit is used for parity checking and is ignored. These parity bits are the

least-significant bits of the key bytes.) The key can be any 56-bit number and can be

changed at any time. A handful of numbers are considered weak keys, but they can

easily be avoided. All security rests within the key.

At its simplest level, the algorithm is nothing more than a combination of the two

basic techniques of encryption: confusion and diffusion. The fundamental building

block of DES is a single combination of these techniques (a substitution followed by

a permutation) on the text, based on the key. This is known as a round. DES has 16

rounds; it applies the same combination of techniques on the plaintext block 16

times (see Figure 12.1).

The algorithm uses only standard arithmetic and logical operations on numbers of

64 bits at most, so it was easily implemented in late 1970s hardware technology.

The repetitive nature of the algorithm makes it ideal for use on a special-purpose

chip. Initial software implementations were clumsy, but current implementations

are better.

of the Algorithm

Outline

DES operates on a 64-bit block of plaintext. After an initial permutation, the

block is broken into a right half and a left half, each 32 bits long. Then there are 16

rounds of identical operations, called Function f, in which the data are combined

with the key. After the sixteenth round, the right and left halves are joined, and a

final permutation (the inverse of the initial permutation) finishes off the algorithm.

In each round (see Figure 12.2) the key bits are shifted, and then 48 bits are

selected from the 56 bits of the key. The right half of the data is expanded to 48 bits

via an expansion permutation, combined with 48 bits of a shifted and permuted key

via an XOR, sent through 8 S-boxes producing 32 new bits, and permuted again.

These four operations make up Function f. The output of Function f is then com-

bined with the left half via another XOR. The result of these operations becomes the

new right half; the old right half becomes the new left half. These operations are

repeated 16 times, making 16 rounds of DES.

If B, is the result of the ith iteration, Li and Ri are the left and right halves of Bi, K,

is the 48-bit key for round i, and f is the function that does all the substituting and

permuting and XORing with the key, then a round looks like:

Page 271

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

77

Plaintext

IP

+

RIFLM@JIRMJI˜)

L15=R14

& 1 K16

˜16=˜15@f7˜15.˜16

I

L16=R15

,

Figure 12.1 DES.

The lnitiaf Permutation

The initial permutation occurs before round 1; it transposes the input block as

described in Table 12.1. This table, like all the other tables in this chapter, should be

read left to right, top to bottom. For example, the initial permutation moves bit 58

of the plaintext to bit position 1, bit 50 to bit position 2, bit 42 to bit position 3, and

so forth.

The initial permutation and the corresponding final permutation do not affect

DESâ€™s security. (As near as anyone can tell, its primary purpose is to make it easier

to load plaintext and ciphertext data into a DES chip in byte-sized pieces. Remem-

ber that DES predates 16-bit or 32-bit microprocessor busses.) Since this bit-wise

permutation is difficult in software (although it is trivial in hardware), many soft-

ware implementations of DES leave out both the initial and final permutations.

While this new algorithm is no less secure than DES, it does not follow the DES

standard and should not be called DES.

Page 272

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12 Data Encryption Standard (DES)

CHAPTER

/ / Ex pansionrutation \ \Com pression,Permutation/

4

S-Box Substitution

1 P-Box Permutation

P-BoxPron 1

Figure 12.2 One round of DES.

The Key Transformation

Initially, the 64-bit DES key is reduced to a 56-bit key by ignoring every eighth bit.

This is described in Table 12.2. These bits can be used as parity check to ensure the

key is error-free. After the 56-bit key is extracted, a different 48-bit subkey is gener-

ated for each of the 16 rounds of DES. These subkeys, Ki, are determined in the fol-

lowing manner.

First, the 56-bit key is divided into two 28-bit halves. Then, the halves are circu-

larly shifted left by either one or two bits, depending on the round. This shift is

given in Table 12.3.

Table 12.1

Initial Permutation

58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,

62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,

57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,

61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7

Page 273

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12.2 Description of DES

Table 12.2

Key Permutation

57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,

10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,

63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,

14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4

After being shifted, 48 out of the 56 bits are selected. Because this operation per-

mutes the order of the bits as well as selects a subset of bits, it is called a compres-

sion permutation. This operation provides a subset of 48 bits. Table 12.4 defines the

compression permutation (also called the permuted choice). For example, the bit in

position 33 of the shifted key moves to position 35 of the output, and the bit in posi-

tion 18 of the shifted key is ignored.

Because of the shifting, a different subset of key bits is used in each subkey. Each

bit is used in approximately 14 of the 16 subkeys, although not all bits are used

exactly the same number of times.

The Expansion Permutation

This operation expands the right half of the data, Ri, from 32 bits to 48 bits.

Because this operation changes the order of the bits as well as repeating certain bits,

it is known as an expansion permutation. This operation has two purposes: It makes

the right half the same size as the key for the XOR operation and it provides a longer

result that can be compressed during the substitution operation. However, neither

of those is its main cryptographic purpose. By allowing one bit to affect two substi-

tutions, the dependency of the output bits on the input bits spreads faster. This is

called an avalanche effect. DES is designed to reach the condition of having every bit

of the ciphertext depend on every bit of the plaintext and every bit of the key as

quickly as possible.

Figure 12.3 defines the expansion permutation. This is sometimes called the E-

box. For each 4-bit input block, the first and fourth bits each represent two bits of

the output block, while the second and third bits each represent one bit of the out-

put block. Table 12.5 shows which output positions correspond to which input posi-

tions. For example, the bit in position 3 of the input block moves to position 4 of the

output block, and the bit in position 21 of the input block moves to positions 30 and

32 of the output block.

Although the output block is larger than the input block, each input block gener-

ates a unique output block.

Table 12.3

Number of Key Bits Shifted per Round

Round 1 234 5 6 7 8 9 10 11 12 13 14 15 16

Number 1 12222221 2 2 2 2 2 2 1

Page 274

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12 Data Encryption Standard (DES)

CHAPTER

Table 12.4

Compression Permutation

14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,

23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,

41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,

44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32

The S-Box Substitution

After the compressed key is XORed with the expanded block, the 48-bit result

moves to a substitution operation. The substitutions are performed by eight substi-

tution boxes, or S-boxes. Each S-box has a 6-bit input and a 4bit output, and there are

eight different S-boxes. (The total memory requirement for the eight DES S-boxes is

256 bytes.) The 48 bits are divided into eight 6-bit sub-blocks. Each separate block is

operated on by a separate S-box: The first block is operated on by S-box 1, the second

block is operated on by S-box 2, and so on. See Figure 12.4.

Each S-box is a table of 4 rows and 16 columns. Each entry in the box is a 4-bit

number. The 6 input bits of the S-box specify under which row and column number

to look for the output. Table 12.6 shows all eight S-boxes.

The input bits specify an entry in the S-box in a very particular manner. Consider

an S-box input of 6 bits, labeled bl, bz, bs, b4, bg, and b,. Bits bl and b, are combined

to form a 2-bit number, from 0 to 3, which corresponds to a row in the table. The

middle 4 bits, b, through b5, are combined to form a 4bit number, from 0 to 15,

which corresponds to a column in the table.

For example, assume that the input to the sixth S-box (i.e., bits 31 through 36 of

the XOR function) is 110011. The first and last bits combine to form 11, which cor-

1234 5 6 7 6 9 10 11 12 13 14 15 16

1 2 3 4 56 76 9 10 1112 1314 15 16 1716 1920 21 22 2324

Figure 12.3 Expansion permutation.

Page 275

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Table 12.5

Expansion Permutation

5, 6, 7, 8, 9,

32, 1, 2, 3, 4, 5, 4,

13, 14, 15, 16, 17,

8, 9, 10, 11, 12, 13, 12,

21, 22, 23, 24, 25,

16, 17, 18, 19, 20, 21, 20,

29, 30, 31, 32, 1

24, 25, 26, 27, 28, 29, 28,

responds to row 3 of the sixth S-box. The middle 4 bits combine to form 1001, which

corresponds to the column 9 of the same S-box. The entry under row 3, column 9 of

S-box 6 is 14. (Remember to count rows and columns from 0 and not from 1.) The

value 1110 is substituted for 110011.

It is, of course, far easier to implement the S-boxes in software as 64-entry arrays. It

takes some rearranging of the entries to do this, but thatâ€™s not hard. (Donâ€™t just change

the indexing without rearranging the entries. The S-boxes are designed very carefully.)

However, this way of describing the S-boxes helps visualize how they work. Each

S-box can be viewed as a substitution function on a 4-bit entry: bZ through bs go in,

and a 4-bit result comes out. Bits bl and b6 come from neighboring blocks; they select

one out of four substitution functions available in the particular S-box.

The S-box substitution is the critical step in DES. The algorithmâ€™s other opera-

tions are linear and easy to analyze. The S-boxes are nonlinear and, more than any-

thing else, give DES its security.

The result of this substitution phase is eight 4bit blocks which are recombined

into a single 32-bit block. This block moves to the next step: the P-box permutation.

The P-Box Permutation

The 32-bit output of the S-box substitution is permuted according to a P-box. This

permutation maps each input bit to an output position; no bits are used twice and

no bits are ignored. This is called a straight permutation or just a permutation. Table

12.7 shows the position to which each bit moves. For example, bit 21 moves to bit

4, while bit 4 moves to bit 3 1.

1

48-Bit Input

32-Bit Output

Figure 12.4 S-box substitution.

Page 276

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER12 Data Encryption Standard (DES)

Table 12.6

S-Boxes

S-box 1:

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

4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,

0, 15, 7,

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

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

S-box 2:

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

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

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

13, 8, 10, 1, 3, 15, 4, 7, 12, 0, 5, 14, 9,

2, 11, 6,

S-box 3:

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

10, 0,

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

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

2, 12,

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

S-box 4:

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

10,

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

0,

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

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

S-box 5:

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

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

14, 11, 2, 12,

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

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

S-box 6:

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

12,

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

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

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

S-box 7:

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

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

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

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

S-box 8:

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

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

6, 11,

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

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

2,

Page 277

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12.2 Description of DES

Table 12.7

P-Box Permutation

16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,

2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25

Finally, the result of the P-box permutation is XORed with the left half of the ini-

tial 64-bit block. Then the left and right halves are switched and another round

begins.

The Final Permutation

The final permutation is the inverse of the initial permutation and is described in

Table 12.8. Note that the left and right halves are not exchanged after the last round

of DES; instead the concatenated block R16L16 used as the input to the final per-

is

mutation. Thereâ€™s nothing going on here; exchanging the halves and shifting around

the permutation would yield exactly the same result. This is so that the algorithm

can be used to both encrypt and decrypt.

Decrypting DES

After all the substitutions, permutations, XORs, and shifting around, you might

think that the decryption algorithm is completely different and just as confusing as

the encryption algorithm. On the contrary, the various operations were chosen to

produce a very useful property: The same algorithm works for both encryption and

decryption.

With DES it is possible to use the same function to encrypt or decrypt a block.

The only difference is that the keys must be used in the reverse order. That is, if the

encryption keys for each round are KI, K,, K3, . . . , Ki6, then the decryption keys are

KM, Ka KM, . , . , K1. The algorithm that generates the key used for each round is

circular as well. The key shift is a right shift and the number of positions shifted is

0,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1.

of DES

Modes

FIPS PUB 81 specifies four modes of operation: ECB, CBC, OFB, and CFB (see

Chapter 9) [ 11431.The ANSI banking standards specify ECB and CBC for encryption,

and CBC and n-bit CFB for authentication [52].

In the software world, certification is usually not an issue. Because of its simplic-

ity, ECB is most often used in off-the-shelf commercial software products, although

Table 12.8

Final Permutation

40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31,

38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29,

36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27,

34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25

Page 278

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12 Data Encryption Standard (DES)

CHAPTER

it is the most vulnerable to attack. CBC is used occasionally, even though it is just

slightly more complicated than ECB and provides much more security.

Hardware and Software Implementations of DES

Much has been written on efficient hardware and software implementations of

the algorithm [997,81,533,534,437,738,1573,176,271,1572]. At this writing, the

recordholder for the fastest DES chip is a prototype developed at Digital Equipment

Corporation [512]. It supports ECB and CBC modes and is based on a GaAs gate

array of 50,000 transistors. Data can be encrypted and decrypted at a rate of 1 giga-

bit per second, which translates to 16.8 million blocks per second. This is impres-

sive. Table 12.9 gives the specifications for some commercial DES chips. Seeming

discrepancies between clock speed and data rate are due to pipelining within the

chip; a chip might have multiple DES engines working in parallel.

The most impressive DES chip is VLSIâ€™s 6868 (formerly called â€śGatekeeperâ€ť). Not

only can it perform DES encryption in only 8 clock cycles (prototypes in the lab can

do it in 4 clock cycles), but it can also do ECB triple-DES in 25 clock cycles, and OFB

or CBC triple-DES in 35 clock cycles. This sounds impossible to me, too, but I

assure you it works.

A software implementation of DES on an IBM 3090 mainframe can perform

32,000 DES encryptions per second. Most microcomputers are slower, but impres-

sive nonetheless. Table 12.10 [603,793] gives actual results and estimates for various

Intel and Motorola microprocessors.

12.3 DES

SECUFUTY OF

People have long questioned the security of DES [458]. There has been much spec-

ulation on the key length, number of iterations, and design of the S-boxes. The

S-boxes were particularly mysterious- all those constants, without any apparent

reason as to why or what theyâ€™re for. Although IBM claimed that the inner workings

were the result of 17 man-years of intensive cryptanalysis, some people feared that

the NSA embedded a trapdoor into the algorithm so they would have an easy means

of decrypting messages.

The U.S. Senate Select Committee on Intelligence, with full top-secret clear-

ances, investigated the matter in 1978. The findings of the committee are classified,

but an unclassified summary of those findings exonerated the NSA from any

improper involvement in the algorithmâ€™s design [1552]. â€śIt was said to have con-

vinced IBM that a shorter key was adequate, to have indirectly assisted in the devel-

opment of the S-box structures and to have certified that the final DES algorithm

was, to the best of their knowledge, free of any statistical or mathematical weak-

nessesâ€ť [435]. However, since the government never made the details of the inves-

tigation public, many people remained unconvinced.

Tuchman and Meyer, two of the IBM cryptographers who designed DES, said the

NSA did not alter the design [841]:

Their basic approach was to look for strong substitution, permutation, and key

scheduling functions. . . . IBM has classified the notes containing the selection

Page 279

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Table 12.9

Commercial DES Chips

Manufacturer Chin Year Clock Data Rate Availabilitv

1981 3 MHz

AMD Am9518 1.3 MByte/s N

AMD Am9568 3 4 MHz 1.5 MByte/s N

AMD AmZ8068 1982 4 MHz 1.7 MByte/s N

AT&T 1985 2

T7000A 1.9 MByte/s N

CE-Infosys 1992 20 MHz

SuperCrypt 12.5 MByte/s Y

CE99C003

CE-Infosys SuperCrypt 1994 30 MHz 20.0 MByte/s Y

CE99C003A

Cryptech Cry12C102 1989 20 MHz 2.8 MByte/s Y

Newbridge CA20C03A 1991 25 MHz 3.85 MByte/s Y

Newbridge 1992 8 MHz

CA20C03W 0.64 MByte/s Y

Newbridge CA95C68/18/09 14.67 MByte/s Y

1993 33 MHz

pijnenburg PCClOO 2 ! 2.5 MByte/s Y

Semaphore Roadrunner284 ! 40 MHz 35.5 MByte/s Y

Communications

VLSI Technology VM007 1993 32 MHz 200.0 MByte/s Y

1993 33 MHz

VLSI Technology VM009 14.0 MByte/s Y

VLSI Technology 6868 1995 32 MHz 64.0 MByte/s Y

Western Digital WD2001/2002 1984 3 MHz 0.23 MByte/s N

Table 12.10

DES Speeds on Different Microprocessors and Computers

DES Blocks (per second)

Processor Speed (in MHz)

8088 4.7 370

68000 7.6 900

80286 6 1,100

68020 16 3,500

68030 16 3,900

80386 25 5,000

68030 50 10,000

68040 25 16,000

68040 40 23,000

80486 66 43,000

Sun ELC 26,000

HyperSparc 32,000

RSbOOO-350 53,000

Spare 10152 84,000

DEC Alpha 4000/610 154,000

HP 9000/887 125 196,000

Page 280

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12 Data Encryption Standard (DES)

CHAPTER

criteria at the request of the NSA. . . . â€śThe NSA told us we had inadvertently

reinvented some of the deepsecretsit uses to make its own algorithms,â€ť explains

Tuchman.

Later in the article, Tuchman is quoted: â€śWe developed the DES algorithm

entirely within IBM using IBMers. The NSA did not dictate a single wire!â€ť Tuch-

man reaffirmed this when he spoke on the history of DES at the 1992 National

Computer Security Conference.

On the other hand, Coppersmith wrote [373,374]: â€śThe National Security Agency

(NSA) also provided technical advice to IBM.â€ť And Konheim has been quoted as say-

ing: â€śWe sent the S-boxes off to Washington. They came back and were all different.

We ran our tests and they passed.â€ť People have pointed to this as evidence that the

NSA put a trapdoor in DES.

NSA, when questioned regarding any imposed weakness in DES, said [363]:

Regarding the Data Encryption Standard (DES), we believe that the public record

from the Senate Committee for Intelligenceâ€™s investigation in 1978 into NSAâ€™s

role in the development of the DES is responsive to your question. That commit-

tee report indicated that NSA did not tamper with the design of the algorithm in

any way and that the security afforded by the DES was more than adequatefor at

least a 5-10 year time span for the unclassified data for which it was intended. In

short, NSA did not impose or attempt to impose any weakness on the DES.

Then why did they modify the S-boxes? Perhaps it was to ensure that IBM did not

put a trapdoor in DES. The NSA had no reason to trust IBMâ€™s researchers, and would

be lax in their duty if they did not make absolutely sure that DES was free of trap-

doors. Dictating the S-boxes is one way they could make sure.

Very recently some new cryptanalysis results have shed some light on this issue,

but for many years this has been the subject of much speculation.

Weak Keys

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 Is,

entirely OS,or if one half of the key is entirely 1s and the other half is entirely OS.

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. (Remem-

ber 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 gen-

erating 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 281

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Table 12.11

DES Weak Kevs

Actual Key

Weak Key Value (with parity bits)

0101 0101 0101 00000000000000

0101

OOOOOOOFFFFFFF

1FlF 1FlF OEOE OEOE

FFFFFFFOOOOOOO

EOEO EOEO FlFl FlFl

FEFE FEFE FFFFFFFFFFFFFF

FEFE FEFE

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 [ 11161,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 OSwith 1s and the

1s with OS.Now, if the original key encrypts a block of plaintext, then the comple-

ment of the key will encrypt the complement of the plaintext block into the com-

plement of the ciphertext block.

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

E,(P) = c

E&q = 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

OlFE OlFE OlFE OlFE and FE01 FE01 FE01 FE01

lFE0 lFE0 OEFl OEFl and EOlF EOlF FlOE FlOE

OlEO OlEO OlFl OlFl and EOOl EOOl FlOl FlOl

1FFE 1FFE OEFE OEFE and FElF FElF FEOE FEOE

OllF OllF OlOE OlOE and lFO1 lFO1 OEOl OEOl

EOFE EOFE FlFE FlFE FEE0 FEE0 FEFl FEFl

and

Page 282

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12 Data Encryption Standard (DES)

CHAPTER

Table 12.13

DES Possibly Weak Keys

EO 01 01 EO

1F 01 Fl 01 01 Fl

1F 01 OE OE 01 01

01 IF 1F EO FE OE 01 Fl

01 01 OE OE 01 FE 1F 01

01 01 01 OE 1F EO FE 01 OE Fl

1F 1F OE 01 FE 01

01 01 1F 1F EO Fl OE OE Fl

1F 01 01 OE OE EO 1F

FE 01 01 FE FE 01 01 FE

EO 01 01 Fl Fl 01 01

EO

1F 01 FE Fl OE 01 FE

EO

01

FE FE 01 FE FE 01 01

1F FE Fl 01 OE FE

EO 01

1F

FE EO 01 FE Fl OE 01

1F FE FE OE OE FE

FE 1F

1F

FE 01 Fl FE OE 01

EO

01 EO OE FE 01 Fl

FE EO 1F FE Fl 01 OE 1F FE 01

01 FE OE Fl

EO FE 1F Fl FE 01 OE FE 1F EO 01

01

1F FE OE Fl 01 FE

EO EO 1F Fl Fl OE OE 1F EO 01

IF

FE FE 1F FE FE OE OE 01 EO 1F FE 01 Fl OE FE

EO 01 FE

FE 1F Fl 01 01 01 EO EO

OE 01 01 Fl Fl

FE 01 Fl

EO 1F OE FE 01 1F 1F EO EO OE OE Fl Fl

EO 1F FE

FE 01 01 Fl OE FE Fl

1F 01 FE EO OE 01

FE 1F Fl

EO 01 01 FE OE 1F FE EO 01 OE FE Fl

01

1F 01 EO FE OE 01 Fl FE

01 EO EO 01 01 Fl Fl 01

01 1F EO FE 01 OE Fl FE

1F FE EO 01 OE FE FO 01

01 01 FE FE 01 01 FE FE

1F EO FE 01 OE Fl FE 01

1F 1F FE FE OE OE FE FE

01 FE FE 01 01 FE FE 01

1F EO EO 1F OE Fl Fl OE FE FE EO EO FE FE Fl Fl

01 FE EO 1F 01 FE Fl OE EO FE FE EO Fl FE FE Fl

01 EO FE 1F 01 Fl FE OE FE EO EO FE FE Fl Fl FE

1F FE FE 1F OE FE FE OE EO EO FE FE Fl Fl 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 [ 1721that there is a known-plaintext attack of the same complexity, requir-

ing at least 233known plaintexts.

It is questionable whether this is a weakness, since most messages donâ€™t have com-

plement 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 cipher-

text blocks in 264!different ways. The DES algorithm, with its 56-bit key, gives us

256(approximately 10â€ť) of these mappings. Using multiple encryption, it seems pos-

sible 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 283

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12.3 Security of DES

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

J%˜E@))

=CT,(P)

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

set of plaintext blocks with K1 followed by Kz 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 228steps (8071.

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

EK˜PK˜(EKJP))) Ev,Pl

=

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 256possible 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 gov-

ernment 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

112781.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 ma-

chine. In 1984 DES chips capable of performing 256,000 encryptions per second had

Page 284

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12 Data Encryption Standard (DES)

CHAPTER

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

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

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, discov-

ered 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 322 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 suc-

cessfully 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

[ 11201 examined the operation of the S-boxes. Neither analysis revealed any weak-

nesses, 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 trap-

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

Page 285

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12.4 Differential and Linear Cryptanalysis

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

cions, and the debate continued [228,422,714,1506,1551].

Various oddities about the S-boxes appeared in the literature. The last three out-

put bits of the fourth S-box can be derived in the same way as the first by comple-

menting 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 out-

put 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 [ 14231. (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 prin-

ciples 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 non-

randomness based on spectral tests [559]. Others analyzed sequences of linear fac-

tors, 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 LINEAR

DIFFERENTIAL AND CRYPTANALYSIS

Differentiaf 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 cipher-

texts 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 â€śdiffer-

enceâ€ť is defined using XOR. This can be different for different algorithms.) Then,

using the differences in the resulting ciphertexts, assign different probabilities to

Page 286

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 12 Data Encryption Standard (DES)

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 AX. The outputs, Y and Yâ€™ are

known, and therefore so is the difference, AY Both the expansion permutation and

the P-box are known, so AA and AC are known. B and Bâ€™ are not known, but their

difference AII is known and equal to AA. (When looking at the difference, the XOR-

ing of Ki with A and Aâ€™ cancels out.) So far, so good. Hereâ€™s the trick: For any given

AA, not all values of AC are equally likely. The combination of AA and AC 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 sub-

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

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

differences in the resulting ciphertext pairs. These are called characteristics. Char-

acteristics 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

X

E(X) Ki

AA

AB

S-Box

Figure 12.5 DES round function.

Page 287

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

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.

For example, Figure 12.6a is a one-round characteristic. The input difference of

the left side is 15;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 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 â€˜$44, output

the

difference of the round function is L 0 0x00808200. This means that the output dif-

ference of the left side is L 0 0x00808200 and the output difference of the right side

is 0x60000000-with probability %.

Different characteristics can be joined. And, assuming the rounds are indepen-

dent, 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 â€˜4/M.

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.

A=L A=0 A=L A=X

Ki

A=0

4

4

v v

A=0 A=X

A=LeO A=LeY

X=60000000

Y=OO808200

With Probability 1 With Probability i

(4 (W

Figure 12.6 DES characteristics.

Page 288

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 12 Data Encryption Standard (DES)

A=X

A=Y

A=X A=0

X = 60000000

Y=OO808200

Figure 12.7 A two-round DES character-

is tic.

With Probability g

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 24spossible 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 1.5

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

dates 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 [ 1721. 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

Page 289

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

12.4 Differential and Linear Cryptanalysis

Table 12.14

Differential Cryptanalysis Attacks against DES

Complexity

Known Analyzed

No. of Chosen

of Analysis

Plaintexts Plaintexts

ńňđ. 1 |