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

As an illustration we consider eight rounds of DES. As depicted in Fig. 4.8, the
output mask after the seventh round is

b = 21040080 00008000

and the input mask is

a = 01040080 00011000

so that if f is the function which maps a plaintext into the output from the seventh
round, we have

· ⊕ · = ⊕

B 1 ⊕

B 3 ⊕ B 4 ⊕ B 5 ⊕ B 7

( a x ) ( b f ( x )) cste

where cste is a constant bit which depends on the key and the B i 's are bias bits in round
i . Note that B 1 , B 3 , B 5 , and B 7 are bias bits around the S 5 substitution box of DES
whereas B 4 is a bias bit around S 1 . Due to the piling-up lemma we obtain

16 2 125

2 15

2

× 10 × 2 × 20 × 20

LP f ( a 2 − 16

, b ) = = ≈ .

32 5

Note that f consists of the first seven rounds. The last round of eight-round DES
is a little special since we will use the ciphertext and a guess for some key bits in order
to compute the input of S 1 , to deduce the output of S 1 , and to subtract the bit masked
by 00008000 from the ciphertext. This would lead us to the output from the seventh
round, provided that the guess for the key bits is correct. This means that we have
indeed a characteristic property of the right guess: for each guess of the 6 bits which

are used in order to compute the input of S 1 in the last round, we can make statistics
on the random bit ( a

κ

· x ) ⊕ ( b · f ( x )), where b · f ( x ) is computed from C ( x ) and κ .If

guess κ is not correct, this random bit is approximately a uniformly distributed one. If

2 − 16 .

guess κ is correct, this random bit has a bias LP approximately equal to λ =

More concretely, let X be a uniformly distributed random variable which represents
a plaintext, and let Y

C ( X ) be the ciphertext after we have reduced DES to eight
rounds with an unknown secret key. We let U be equal to the 6 bits of the right half of
Y which will input to S 1 in the last round after a XOR with 6 key bits. We also let V
be a bit equal to

=

V = ( a · X ) ⊕ ( b L · Y R ) ⊕ ( b R · Y L )

where b = b L b R and Y = Y L Y R , i.e. b L (resp. b R ) denotes the left (resp. right) half of

b and the same for Y .

If κ is the right guess for the 6 bits of the key, we are interested in the bit

W κ =

V ⊕ ( b R · P ( S 1 ( U ⊕ κ ) || 0000000 ))