Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
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 J1, . . . , J8. These positions are (respectively): 47, 5, 19, 0, 24, 7, 7, 49. Converting these integers to binary, we obtain J1, . . . , J8:
J1 = 101111 |
J2 = 000101 |
J3 = 010011 |
J4 = 000000 |
J5 = 011000 |
J6 = 000111 |
J7 = 000111 |
J8 = 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.
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:
The probability of the characteristic is defined to be the product p = p1 × . . . × pn.
REMARK Suppose we choose L0, R0 and so that and and we apply n rounds of DES encryption, obtaining L1, . . . , Ln and R1, . . . ,Rn. Then we cannot claim that the probability that and for all i (1 ≤ i ≤ n) is p1 × . . . × pn. This is because the 48-tuples in the key schedule K1, . . . . , Kn, are not mutually independent. (If these n 48-tuples were chosen independently at random, then the assertion would be true.) But we nevertheless expect p1 × . . . × pn to be a fairly accurate estimate of this probability.
We also need to recognize that the probabilities pi 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 248 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 p1, . . . pn, 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.
Lets look at the characteristic in Figure 3.11 in more detail. When f (R0, K1) and are computed, the first step is to expand R0 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 S1 is 001100 and the input x-ors for the other seven S-boxes are all 000000. The output x-ors for S2 through S8 will all be 0000. The output x-or for S1 will be 1110 with probability 14/64 (since it can be computed that N1 (001100, 1110) = 14). So we obtain
with probability 14/64. Applying P, we get
which in hexadecimal is 0080820016. 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 , L6R6 and , where we have chosen the plaintexts so that and . We can express R6 as follows:
Figure 3.12 A 3-round characteristic
can be expressed in a similar way, and hence we get
Previous | Table of Contents | Next |
Copyright © CRC Press LLC