[cryptography] Status of the Biryukov/Wagner slide attack against DESX?

Francois Grieu fgrieu at gmail.com
Fri Jun 10 10:17:38 EDT 2011

On 2011-06-10 13:12, kg wrote at sci.crypt:
 > Francois Grieu<fgrieu at gmail.com>  wrote:
 >> I am reviewing the best known attacks against DESX. There is in
 >> particular A. Biryukov and D. Wagner: Advanced Slide Attacks,
 >> in the proceedings of Eurocrypt 2000
 >> <http://www.iacr.org/archive/eurocrypt2000/1807/18070595-new.pdf>
 >> <http://www.cs.berkeley.edu/~daw/papers/advslide-ec00.ps>
 >> [...]
 >> DESX is defined from DES as
 >>    DESXenc(<K,Kx,Ky>, P) = E(K, P xor Kx) xor Ky = C
 >>    DESXdec(<K,Kx,Ky>, C) = D(K, C xor Ky) xor Kx = P
 >> where E is DES encryption and D is DES decryption.
 >> The attack as I read it at page 608 (14 in the PDF/PS) goes
 >> 1. Obtain 2^32.5 plain/ciphertext pairs<Pi,Ci>
 >> 2. Enumerate the 2^56 DES keys K, and for each
 >> 3.- Compute each D(K, Ci) xor Pi and detect collisions
 >> 4.- For the few<i,j>  with D(K, Ci) xor Pi = D(K, Cj) xor Pj
 >> 5.-- Recover Ky = Ci xor Cj  and Kx = Pi xor D(K, Ci xor Ky)
 >>       [Note: the paper states  Ky = Ci xor C'j]
 >> 6.-- Test that<K,Kx,Ky>  on a few plain/ciphertext pairs.
 >> I fail to see why at step 5. there would be a sizable chance that
 >> Ky = Ci xor Cj would recover the actual Ky, or what is meant in
 >> the paper by C'j and/or how to obtain it.
 > I think the C'j is a typo, it should be Cj.
 > The argument should go as follows:

In summary: I now get it fully, thanks to your excellent explanation!

 > (1) Among the observed plaintexts, the birthday paradox means that it
 > is likely that for some i != j,
 >          (*) Ci xor Cj = Ky.

OK (with the the additional hypothesis that Ky!=0).
[ I fail to derive that from the usual statement of the birthday
   paradox, but get something similar by considering
     F(i,j) = Ci xor Cj
            = E(K, Pi xor Kx) xor E(K, Pj xor Kx).
   F(i,j) is independent of Ky, and except for the fact that F(i,j)
   with i<j never reaches 0, if F(i,j) was strongly biased towards
   a particular value for a random instance of K, then E would
   become distinguishable from a random permutation given the set
   of plaintexts and Kx ]

 > (2) If Ci xor Cj = Ky, then (see paper)
 >          (**) D(K,Ci) xor Pi = D(K,Cj) xor Pj.

OK. I see how to derive that. If Ci xor Cj = Ky then
   D(K,Ci) = D(K, Ky xor Cj)
           = (D(K, Ky xor Cj) xor Kx) xor Kx
           = Pj xor Kx
and similarly
   D(K,Cj) = Pi xor Kx
hence (*) implies (**).

 > (3) For a given key K, we can compute D(K,Ci) xor Pi for all possible
 > i and look for collisions. This gives us pairs satisfying (**), but
 > perhaps not (*).

OK. I now get it!

 > (4) If (**) holds for a pair and a key K, we can check if (*)
 > holds by computing Ky and Kx and checking these for a few other
 > plaintext-ciphertext pairs.
 > This seems to match the authors' claims.

It does!

 >> Critically, I observe that the DES ciphertext fed into D at step 3
 >> is mostly different from the DES ciphertext for actual
 >> plain/ciphertext pairs, unless of course Ky is 0; thus I fail to
 >> see how the detected collisions help.
 > Most of the detected collisions do not help, but you notice that
 > they don't help when you get the wrong keys.

OK. Even for the right K, it is possible that we get a false hit,
but that would remain very marginal.

Again, many thanks.

   Francois Grieu

More information about the cryptography mailing list