Cryptography: Theory and Practice:The Data Encryption Standard | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

Decryption is done using the same algorithm as encryption, starting with y as the input, but using the key schedule K₁₆, . . . , K₁ in reverse order. The output will be the plaintext x.

3.2.1 An Example of DES Encryption

Here is an example of encryption using the DES. Suppose we encrypt the (hexadecimal) plaintext

0123456789ABCDEF

using the (hexadecimal) key

133457799BBCDFF1.

The key, in binary, without parity-check bits, is

00010010011010010101101111001001101101111011011111111000.

Applying IP, we obtain L₀ and R₀ (in binary):

The 16 rounds of encryption are then performed, as indicated.

Finally, applying IP^-1 to R₁₆L₁₆, we obtain the ciphertext, which (in hexadecimal form) is:

85E813540F0AB405.

3.3 The DES Controversy

When DES was proposed as a standard, there was considerable criticism. One objection to DES concerned the S-boxes. All computations in DES, with the exception of the S-boxes, are linear, e.g., computing the exclusive-or of two outputs is the same as forming the exclusive-or of two inputs and then computing the output. The S-boxes, being the non-linear component of the cryptosystem, are vital to its security (We saw in Chapter 1 how linear cryptosystems, such as the Hill Cipher, could easily be cryptanalyzed by a known plaintext attack.) However, the design criteria of the S-boxes are not completely known. Several people have suggested that the S-boxes might contain hidden “trapdoors” which would allow the National Security Agency to decrypt messages while maintaining that DES is “secure.” It is, of course, impossible to disprove such an assertion, but no evidence has come to light that indicates that trap-doors in DES do in fact exist.

In 1976, the National Security Agency (NSA) asserted that the following properties of the S-boxes are design criteria:

P0 Each row of each S-box is a permutation of the integers 0, . . . , 15.

P1 No S-box is a linear or affine function of its inputs.

P2 Changing one input bit to an S-box causes at least two output bits to change.

P3 For any S-box and any input x, S(x) and S(x ⊕ 001100) differ in at least two bits (here x is a bitstring of length 6).

Two other properties of the S-boxes were designated as “caused by design criteria” by NSA.

P4 For any S-box, for any input x, and for e, f ∈ {0, 1}, S(x) ≠ S(x ⊕ 11ef00).

P5 For any S-box, if one input bit is fixed, and we look at the value of one fixed output bit, the number of inputs for which this output bit equals 0 will be “close to” the number of inputs for which the output bit equals 1. (Note that if we fix the value of either the first or sixth input bit, then 16 inputs will cause a particular output bit to equal 0 and 16 inputs will cause the output to equal 1. For the second through fifth input bits, this will not be true, but the resulting distribution will be “close to” uniform. More precisely, for any S-box, if the value of any input bit is fixed, then the number of inputs for which any fixed output bit has the value 0 (or 1) is always between 13 and 19.)

It is not publicly known if further design criteria were used in the construction of the S-boxes.

The most pertinent criticism of DES is that the size of the keyspace, 2⁵⁶, is too small to be really secure. Various special-purpose machines have been proposed for a known plaintext attack, which would essentially perform an exhaustive search for the key. That is given a 64-bit plaintext x and corresponding ciphertext y, every possible key would be tested until a key K such that e_K (x) = y is found (and note that there may be more than one such key K).

As early as 1977, Diffie and Hellman suggested that one could build a VLSI chip which could test 10⁶ keys per second. A machine with 10⁶ chips could search the entire key space in about a day. They estimated that such a machine could be built for about $20,000,000.

At the CRYPTO ’93 Rump Session, Michael Wiener gave a very detailed design of a key search machine. The machine is based on a key search chip which is pipelined, so that 16 encryptions take place simultaneously. This chip can test 5 × 10⁷ keys per second, and can be built using current technology for $10.50 per chip. A frame consisting of 5760 chips can be built for $100,000. This would allow a DES key to be found in about 1.5 days on average. A machine using 10 frames would cost $1,000,000, but would reduce the average search time to about 3.5 hours.

3.4 DES in Practice

Even though the description of DES is quite lengthy, it can be implemented very efficiently, either in hardware or in software. The only arithmetic operations to be performed are exclusive-ors of bitstrings. The expansion function E, the S-boxes, the permutations IP and P, and the computation of K₁, K₂, . . . , K₁₆ can all be done in constant time by table look-up (in software) or by hard-wiring them into a circuit.

Current hardware implementations can attain extremely fast encryption rates. Digital Equipment Corporation announced at CRYPTO ’92 that they have fabricated a chip with 50K transistors that can encrypt at the rate of 1 Gbit/second using a clock rate of 250 MHz! The cost of this chip is about $300. As of 1991, there were 45 hardware and firmware implementations of DES that had been validated by the National Bureau of Standards.

One very important application of DES is in banking transactions, using standards developed by the American Bankers Association. DES is used to encrypt personal identification numbers (PINs) and account transactions carried out by automated teller machines (ATMs). DES is also used by the Clearing House Interbank Payments System (CHIPS) to authenticate transactions involving over $1.5 × 10¹² per week.

DES is also widely used in government organizations, such as the Department of Energy, the Justice Department, and the Federal Reserve System.

Table of Contents