(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 S₂, S₅, S₆, S₇ and S₈ 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 C_i 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 S₂, S₅, S₆, S₇ and S₈ in round 6. The inputs to these S-boxes in round 6 can be computed to be E₂, E₅, E₆, E₇ and E₈, 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 J₂, J₅, J₆, J₇ and J₈ 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 L₀R₀ and is right pair with respect to a characteristic if and for all i, 1 ≤ i ≤ n. 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 E_j, , 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 J_j will be included in the set test_j. If the pair is a wrong pair, then the value of will be incorrect, and it seems reasonable to hypothesize that each set test_j will be essentially random.

We can often identify a wrong pair by this method: If |test_j| = 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 |test_j| = 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 test_j’s have positive cardinality is estimated to be , so the probability that at least one test_j 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