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

Francois Grieu fgrieu at gmail.com
Fri Jun 10 05:04:12 EDT 2011


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

Among other results, this paper claims an attack against DESX
with 2^32.5 plaintext/ciphertext pairs, 2^87.5 DES operations,
and about 64 GiB of memory (I guess for each attack device).
So far I had taken this peer-reviewed paper at face value, but
I'm actually trying to dive into the details.

And I fail to understand how the attack works!

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, P 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.
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.

Is anyone aware of a corrected version?

   Francois Grieu

[posted at sci.crypt and cryptography mailing list @randombit.net]

More information about the cryptography mailing list