Conventional Security Analysis - A Classical Introduction to Cryptography: Applications for Communications Security - page 100

If x and x + a are plaintext blocks such that this characteristic holds, we call

( x a )a right pair . Otherwise we call it a wrong pair . The above heuristic analysis

shows that we have at least a fraction of 2 − 13 . 4

, x +

of right pairs.

After the expansion in the sixth round, the input difference of 405c0000 leads
to an input difference of

14 00 13 70 00 00 00 00

for the S -boxes: the input difference of S 2 , S 5 , S 6 , S 7 , and S 8 are zero. Thus the output
difference of these S -boxes is zero. The output difference of these S -boxes in the eighth
round is XORed to (1) the output differences of the same S -boxes in the sixth round (thus
zero) and (2) the corresponding bits from the input difference in the sixth round, which
are known (provided that we have a right pair) in order to produce some ciphertext-
difference bits. Thus we can compute the inputs of the corresponding S -boxes in the
eighth round and the output differences for the right pairs. Next we can try all possible
corresponding key bits (six per S -box, which gives 30 bits) in order to suggest some
30-bit combinations.

In Fig. 4.2, unknown differences are represented by question marks, and com-
putable values (from the ciphertext pairs) are represented by dots. Thus for each ci-
phertext pair, we compute two vectors of 30 bits which are the inputs of S 2 , S 8

before the XOR with the subkey and one vector of 20 bits which is the output difference
of these S -boxes, provided that we have a right pair. Each of these vector triplets will
be consistent with some 30-bit subkey vector.

S 5 , S 6 , S 7 ,

Now we use counters for every 30-bit combination. Namely, we make N exper-
iments in which we query ( x

a ) pairs. For each pair we increment the counter
of suggested combinations. At the end we hope the right combination to have been
suggested many times in order to distinguish it (see Fig. 4.3).

, x +

The right combination is suggested for every right pair. So it is at least suggested
with probability p 1 ≈ 2 − 13 . 4 for each experiment. Its counter will thus eventually be in

the range of Np 1 ± √ Np 1 . This is called the signal .

Any other combination is suggested w ith p robability p 2 ≈ 2 − 20 . Their counters

are thus eventually in the range of Np 2 ± √ Np 2 and are considered as noise .

The signal over noise ratio is thus p 1 / p 2 = 100, which is high enough. We still

need to choose N such that

Np 2 < Np 1

N ( p 1 − p 2 )

2 13 . 4 .

in order to separate the two distributions, which means N 1 / p 1 ≈