Cryptography: Theory and Practice:The Data Encryption Standard

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

Previous Table of Contents Next


(Note the similarity with the 3-round attack.)

is known. From the characteristic, we estimate that and with probability 1/16. If this is in fact the case, then the input x-or for the S-boxes in round 4 can be computed by the expansion function to be:

The input x-ors for S2, S5, S6, S7 and S8 are all 000000, and hence the output x-ors are 0000 for these five S-boxes in round 4. This means that we can compute the output x-ors of these five S-boxes in round 6 from Equation (3.4). So, suppose we compute

where each Ci is a bitstring of length four. Then with probability 1/16, it will be the case that and are respectively the output x-ors of S2, S5, S6, S7 and S8 in round 6. The inputs to these S-boxes in round 6 can be computed to be E2, E5, E6, E7 and E8, and and , where

and

can be computed from the ciphertexts, as indicated in Figure 3.13.

We would like to determine the 30 key bits in J2, J5, J6, J7 and J8 as we did in the 3-round attack. The problem is that the hypothesized output x-or for round 6 is correct only with probability 1/16. So 15/16 of the time we will obtain random garbage rather than possible key bits. We somehow need to be able to determine the correct key from the given data, 15/16 of which is incorrect. This might not seem very promising, but fortunately our prospects are not as bleak as they initially appear.

DEFINITION 3.6  Suppose and . We say that the pair of plaintexts L0R0 and is right pair with respect to a characteristic if and for all i, 1 ≤ in. The pair is defined to be a wrong pair, otherwise.


Figure 3.13  Differential attack on 6-round DES

We expect that about 1/16 of our pairs are right pairs and the rest are wrong pairs with respect to our 3-round characteristic.

Our strategy is to compute Ej, , and , as described above, and then to determine , for j = 2, 5, 6, 7, 8. If we start with a right pair, then the correct key bits for each Jj will be included in the set testj. If the pair is a wrong pair, then the value of will be incorrect, and it seems reasonable to hypothesize that each set testj will be essentially random.

We can often identify a wrong pair by this method: If |testj| = 0, for any j ∈ {2, 5, 6, 7, 8}, then we necessarily have a wrong pair. Now, given a wrong pair, we might expect that the probability that |testj| = 0 for a particular j is approximately 1/5. This is a reasonable assumption since and, as mentioned earlier, the probability that is approximately 1/5. The probability that all five testj’s have positive cardinality is estimated to be , so the probability that at least one testj has zero cardinality is about .67. So we expect to eliminate about 2/3 of the wrong pairs by this simple observation, which we call the filtering operation. The proportion of right pairs that remain after filtering is approximately


Previous Table of Contents Next

Copyright © CRC Press LLC



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net