. 1
( 2)



>>

Prev. Chapter Home Previous Page
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
( 2)



>>