Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Reference : Tutorial by HM Heys
If we find a differential trail that holds with some non negligible probability for n-1 rounds for a n rounds SPN structure, then we can recover some of the bits of the last round subkey.
What happens when we only manage a differential trail that holds with non negligible probability for only few of the rounds R where R < n-1? How do we proceed in that case to make a key recovery attack?
I will really appreciate some hints to think about this.
self-study
I would disagree with the answer by @kodlu. In classic differential cryptanalysis, we don't pay "probability" for the last rounds, but rather we pay for the enumeration of the involved key bits. In other words, decryption is not statistical.
And that's what makes using smaller $R$ difficuly: the key guesses. Ciphers have good diffusion and with each extra round to partially decrypt in the end, the number of key bits needed to be guessed in order to verify the output difference (now, statistically, per each key guess) grows very fast.
In addition, the shape of the output difference matters too: if it has high weight (activates many S-boxes in the consequent rounds), more key bits guesses are needed.
Note that $R$ and the number of key bits to guess are in a trade-off: smaller $R$ increases differential probability, but also increases the number of key bits to guess. Usually, the gain in differential probability by going from $R=n-1$ to $R=n-2$ does not outbalance the increase in key guess complexity when partially decrypting 2 rounds instead of 1.
The reason $R=n-1$ (or $R=1,$ applied to the decryption mapping) is used is the following. All the individual differential approximations as well as the differential trail which is chosen over the $R$ rounds yield statistical relationships.
However, one can now use the ciphertext output, run the Sboxes in the last round in reverse, and conditional on each guess for the round keys XORed into the inputs of the $n^{th}$ round Sboxes have non-random and exact guesses for the outputs of the targeted Sboxes from round $n-1.$ This means a reliable statistical experiment can be run and the empirical differential probability of the chosen input output difference can be calculated reliably.
At this stage, given enough P/C pairs, the key guess that results in the largest empirical probability is declared the most likely key guess.
See my answer to the following question for more concrete details.
Differential cryptanalysis tutorial of Howard M. Heys
Edit: Thanks to @fractalice for catching the sloppy last part of my answer. It is indeed the computational complexity of going through the key guesses of the "active" Sboxes in the last round that is significant. So the differential probability of $\epsilon$ of the $n-1$ differential characteristic means that you need to use roughly $c/\epsilon$ P/C pairs for the characteristic to empirically be the dominant one, and if there are $k$ active Sboxes in the last round you will need to try $2^{4k}$ (since Sboxes are 4 bits wide) guessed keys while trying to decide which guessed keys are the most likely.
