How do we find the subkey out of a differential cryptanalysis?

Question

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

Answer 1

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.

Answer 2

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.