3
$\begingroup$

I understand the differential cryptanalysis up to the "finding the last subkey" part. If XORing with the key doesn't change the differentials, how can testing different key affect the equations we found?

EDIT: I think I kinda get the answer now. Although I'd like a confirmation:

After getting all those probabilities on the differentials at different stage in the cipher. You test these probabilities with real pairs of messages and ciphertexts and you see if for an hypothetical key the probabilities you found hold. If they don't it's probably because you had a bad key, if they do then you probably have a good key.

EDIT2: Mmm, actually no I still don't understand. Even with a bad key, probabilities we found still should apply...

$\endgroup$
  • 1
    $\begingroup$ The exact details of how differential cryptanalysis is used (and how we use a differential to obtain information about the key) depends on the internals of the cipher being attacked; what cipher were you looking at? $\endgroup$ – poncho Dec 15 '14 at 21:47
  • $\begingroup$ Let's say a amazingly simple and fictive Substitution Permutation Network. $\endgroup$ – David 天宇 Wong Dec 15 '14 at 21:52
  • $\begingroup$ so, like 4 round AES? $\endgroup$ – Richie Frame Dec 16 '14 at 1:42
  • $\begingroup$ or even 2 rounds to make it simplier $\endgroup$ – David 天宇 Wong Dec 16 '14 at 18:59
2
$\begingroup$

The key does not effect the cipher' differentials threw the equation (x+k)+(x'+k)=x+x' (the + sign means xor)

How you can yes the key is X1+k=x2 And threw the xor k=X1 +x2

X1 is the value beffor the xor with the key value k. X2 is the output of X1+k

To make this attack work beffor you must find a differential for the two input pairs threw a chosen plaintext attack x'+x= D1 (differential 1) Then the corresponding cipher text outputs y'+y=d2 then you follow the differential path that you have made. (Threw this attack you can drop one round as once you found 1 key then the other key must also follow suit to be able to get the cipher text wanted)

To lower the probability of the correct key you repeat this process with a new path and a new chosen plaintext. If keys match between the two keys found then the probability goes up.

If this doesn't help try http://www.theamazingking.com/crypto-diff.php

And http://www.cs.cmu.edu/~hannes/diffLinAES.pdf

Some defenses against DC is adding more rounds or by trying to get differential uniformity for the s-box.

$\endgroup$
1
$\begingroup$

XORing with a key indeed does not change the difference. But usually before the XORing there is nonlinear layer (Sboxes?) which changes the difference. For example $(N rounds...)(Sbox)(AddKey)$. You can use a differential up to the beginning of this layer. Then, for different subkeys you will get same sbox output differences, but the sbox input differences will vary.

So, to recover the subkey in such way, the part which you attack (last round?) must have some nonlinearity with dependence on the subkey (obviously $(AddKey)(Sbox)$ will not work).

You can also consider some tricks - if you can't find good differential for the whole cipher, you can bruteforce some last rounds' subkeys (e.g. "drop some rounds from the bottom") and attack smaller amount of rounds. Of course you need to check that resulting complexity is good enough.

$\endgroup$
  • $\begingroup$ how is the sbox input difference varying? $\endgroup$ – David 天宇 Wong Dec 23 '14 at 14:57
  • $\begingroup$ When you have some amount of plain/ciphertext pairs with plaintext difference $\Delta x$, you are trying all possible last round keys. For a right guess you will have more intermediate values with difference $\Delta y$ than for a wrong guess. $\endgroup$ – Hyperflame Dec 24 '14 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.