On 2011-06-10 13:12, kg wrote at sci.crypt:
> Francois Grieu<[email protected]> 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
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
