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

3.7 Notes and References

A nice article on the history DES is by Smid and Branstad [SB92]. Federal Information Processing Standards (FIPS) publications concerning DES include the following: description of DES [NBS77]; implementing and using DES [NBS81]; modes of operation of DES [NBS80]; and authentication using DES [NBS85].

Some properties of the S-boxes are studied by Brickell, Moore, and Purtill [BMP87].

The DEC DES chip is described in [EB93]. Wiener’s key search machine was described at CRYPTO ’93 [WI94].

The time-memory trade-off for DES is due to Hellman [HE80]. A more general time-memory trade-off is presented by Fiat and Naor in [FN91].

The technique of differential cryptanalysis was developed by Biham and Shamir [BS91] (see also [BS93A] and their book [BS93], where cryptanalysis of other cryptosystems is also discussed). Our treatment of differential cryptanalysis is based largely on [BS93].

Another new method of cryptanalysis that can be used to attack DES and other similar cryptosystems is the linear cryptanalysis of Matsui [MA94, MA94A].

Descriptions of other substitution-permutation cryptosystems can be found in the following sources: LUCIFER [FE73]; FEAL [MI9 1]; REDOC-II [CW91]; and LOKI [BKPS90].

Exercises

3.1 Prove that DES decryption can be done by applying the DES encryption algorithm to the ciphertext with the key schedule reversed.

3.2 Let DES(x, K) represent the encryption of plaintext x with key K using the DES cryptosystem. Suppose y = DES (x, K) and y′ = DES (c(x), c(K)), where c(·) denotes the bitwise complement of its argument. Prove that y′ = c(y) (i.e., if we complement the plaintext and the key, then the ciphertext is also complemented). Note that this can be proved using only the “high-level” description of DES — the actual structure of S-boxes and other components of the system are irrelevant.

3.3 One way to strengthen DES is by double encryption: Given two keys, K₁ and K₂, define

(of course, this is just the product of DES with itself). If it happened that the encryption function

was the same as the decryption function

, then K₁ and K₂ are said to be dual keys. (This is very undesirable for double encryption, since the resulting ciphertext is identical to the plaintext.) A key is self-dual if it is its own dual key.

(a) Prove that if C₀ is either all 0’s or all 1’s and D₀ is either all 0’s or all 1’s, then K is self-dual.

(b) Prove that the following keys (given in hexadecimal notation) are self-dual:

0101010101010101 FEFEFEFEFEFEFEFE 1F1F1F1F0E0E0E0E E0E0E0E0F1F1F1F1

(c) Prove that if C₀ = 0101 . . . 01 or 1010 . . . 10 (in binary), then the x-or of the bitstrings C_i and C_17-i is 1111 . . . 11, for 1 ≤ i ≤ 16 (a similar statement holds for the D_i’s).

(d) Prove that the following pairs of keys (given in hexadecimal notation) are dual:

E001E001F101F101 FE1FFE1FFE0EFE0E E01FE01FF10EF10E 01E001E001F101F1 1FFE1FFE0EFE0EFE 1FE01FE00EF10EF1

3.4 A message authentication code (MAC) can be produced by using CFB mode, as well as by using CBC mode. Given a sequence of plaintext blocks x₁ . . . x_n, suppose we define the initialization vector IV to be x₁. Then encrypt x₂ . . . x_n using key K in CFB mode, obtaining y₁ . . . y_n-1 (note that there are only n - 1 ciphertext blocks). Finally, define the MAC to be e_K(y_n-1). Prove that this MAC is identical to the MAC produced in Section 3.4.1 using CBC mode.

3.5 Suppose a sequence of plaintext blocks, x₁, . . . x_n, is encrypted using DES, producing ciphertext blocks y₁ . . . y_n. Suppose that one ciphertext block, say y_i, is transmitted incorrectly (i.e., some 1’s are changed to 0’s and vice versa). Show that the number of plaintext blocks that will be decrypted incorrectly is equal to one if ECB or OFB modes were used for encryption; and equal to two if CBC or CFB modes were used.

3.6 The purpose of this question is to investigate a simplified time-memory trade-off for a chosen plaintext attack. Suppose we have a cryptosystem in which

, which attains perfect secrecy. Then it must be the case that

implies K = K₁. Denote

. Let x be a fixed plaintext. Define the function g : Y → Y by the rule g(y) = e_y(x). Define a directed graph G having vertex set Y, in which the edge set consists of all the directed edges of the form (y_i, g(y_i)), 1 ≤ i ≤ N.

(a) Prove that G consists of the union of disjoint directed cycles.

(b) Let T be a desired time parameter. Suppose we have a set of elements Z = {z₁, . . . , z_m} ⊆ Y such that, for every element y_i ∈ Y, either y_i is contained in a cycle of length at most T, or there exists an element z_j ≠ y_i such that the distance from y_i to z_j (in G) is at most T. Prove that there exists such a set Z such that

so |Z| is O(N/T)

(c) For each z_j ∈ Z, define g^-T (z_j) to be the element y_i such that g^T (y_i) = z_j, where g^T is the function that consists of T iterations of g. Construct a table X consisting of the ordered pairs (z_j, g^-T (z_j)), sorted with respect to their first coordinates.

A pseudo-code description of an algorithm to find K, given y = e_K (x), is presented in Figure 3.15. Prove that this algorithm finds K in at most T steps. (Hence the time-memory trade-off is O(N).)

Figure 3.15 Time-memory trade-off

Figure 3.16 Differential attack on 4-round DES

(d) Describe a pseudo-code algorithm to construct the desired set Z in time O(NT) without using an array of size N.

3.7 Compute the probabilities of the following 3-round characteristic:

3.8 Here is a differential attack on a 4-round DES. It uses the following characteristic, which is a special case of the characteristic presented in Figure 3.10:

(a) Suppose that the following algorithm presented in Figure 3.16 is used to compute sets test₂, . . . test₈. Show that J_j ∈ test_j for 2 ∈ j ∈ 8.

(b) Given the following plaintext-ciphertext pairs, find the key bits J₂, . . . , J₈.


plaintext	ciphertext

18493AC485B8D9A0	E332151312A18B4F
38493AC485B8D9A0	87391C27E5282161

482765DDD7009123	B5DDD8339D82D1D1
682765DDD7009123	81F4B92BD94B6FD8

ABCD098733731FF1	93A4B42F62EA59E4
8BCD098733731FF1	ABA494072BF411E5

13578642AAFFEDCB	FDEB526275FB9D94
33578642AAFFEDCB	CC8F72AAE685FDB1

(c) Compute the entire key (14 key bits remain to be determined, which can be done by exhaustive search).

Table of Contents