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

In each of the eight counter arrays, there is a unique counter having the value 3. The positions of these counters determine the key bits in J₁, . . . , J₈. These positions are (respectively): 47, 5, 19, 0, 24, 7, 7, 49. Converting these integers to binary, we obtain J₁, . . . , J₈:

J₁ = 101111

J₂ = 000101

J₃ = 010011

J₄ = 000000

J₅ = 011000

J₆ = 000111

J₇ = 000111

J₈ = 110001.

We can now construct 48 bits of the key, by looking at the key schedule for round 3. It follows that K has the form

0001101	0110001	01?01?0	1?00100
0101001	0000??0	111?11?	?100011

where parity bits are omitted and “?” denotes an unknown key bit. The complete key (in hexadecimal, including parity bits), is:

1A624C89520DEC46.

3.6.2 An Attack on a 6-round DES

We now describe an extension of these ideas to a probabilistic attack on a 6-round DES. The idea is to carefully choose a pair of plaintexts with a specified x-or, and then to determine the probabilities of a specified sequence of x-ors through the rounds of encryption. We need to define an important concept now.

DEFINITION 3.5 Let n ≥ 1 be an integer. An n-round characteristic is a list of the form

which satisfies the following properties:

2. Let 1 ≤ i ≤ n, and let L_i-1, R_i-1 and

be chosen such that

and

. Suppose L_i, R_i and

are computed by applying one round of DES encryption. Then the probability that

and

is precisely p_i. (Note that this probability is computed over all possible 48-tuples J = J₁ . . . J₈.)

The probability of the characteristic is defined to be the product p = p₁ × . . . × p_n.

REMARK Suppose we choose L₀, R₀ and so that and and we apply n rounds of DES encryption, obtaining L₁, . . . , L_n and R₁, . . . ,R_n. Then we cannot claim that the probability that and for all i (1 ≤ i ≤ n) is p₁ × . . . × p_n. This is because the 48-tuples in the key schedule K₁, . . . . , K_n, are not mutually independent. (If these n 48-tuples were chosen independently at random, then the assertion would be true.) But we nevertheless expect p₁ × . . . × p_n to be a fairly accurate estimate of this probability.

We also need to recognize that the probabilities p_i in a characteristic are defined with respect to an arbitrary (but fixed) pair of plaintexts having a specified x-or, where the 48 key bits for one round of DES encryption vary over all 2⁴⁸ possibilities. However, a cryptanalyst is attempting to determine a fixed (but unknown) key. He is going to choose plaintexts at random (such that they have specified x-ors), hoping that the probabilities that the x-ors during the n rounds of encryption agree with the x-ors specified in the characteristic are fairly close to p₁, . . . p_n, respectively.

As a simple example, we present in Figure 3.10 a 1-round characteristic which was the basis of the attack on the 3-round DES (as before, we use hexadecimal representations). We depict another 1-round characteristic in Figure 3.11.

Let’s look at the characteristic in Figure 3.11 in more detail. When f (R₀, K₁) and are computed, the first step is to expand R₀ and . The resulting x-or of the two expansions is

Figure 3.10 A 1-round characteristic

Figure 3.11 Another 1-round characteristic

So the input x-or to S₁ is 001100 and the input x-ors for the other seven S-boxes are all 000000. The output x-ors for S₂ through S₈ will all be 0000. The output x-or for S₁ will be 1110 with probability 14/64 (since it can be computed that N₁ (001100, 1110) = 14). So we obtain

with probability 14/64. Applying P, we get

which in hexadecimal is 00808200₁₆. When this is x-ored with , we get the specified with probability 14/64. Of course always.

The attack on the 6-round DES is based on the 3-round characteristic given in Figure 3.12. In the 6-round attack, we will start with , L₆R₆ and , where we have chosen the plaintexts so that and . We can express R₆ as follows:

Figure 3.12 A 3-round characteristic

can be expressed in a similar way, and hence we get

Table of Contents