Score:1

Differential cryptanalysis - how to extend the attack to rounds before the last?

cn flag

Suppose that we have a block cipher such that the last round of the cipher depends on half of the key and the penultimate round uses the other half. Suppose also that I attacked the last round using differential cryptanalysis and reduced my search space from 2^8 to 2 choices for each byte of that half of the key.

One way to conclude the attack would be to execute bruteforce on the remaining key space, but I would like to keep using differential cryptanalysis to attack also the penultimate round, to achieve better complexity than bruteforce.

As a comment to this question, the user "kelalaka" seems to hint at the fact that we can still use differential cryptanalysis to recover the key used in the penultimate round, as "the probabilities will be better". The user "kodlu", in the answer to the same question, says: "Then the rounds can be peeled off one by one as in the comments.", but then they do not describe how to do it.

Can someone explain to me how to extend the differential attack to the penultimate round, in the specific setting I mentioned or even in general? (the "key schedule" I gave is not particularly important but is just a way to say that we can't recover the full key by using only the last round key)

kelalaka avatar
in flag
Well, It should be clear. The more round the lower success of the attack. This is why the designers calculate and set their rounds as AES designers did. Once you attack to the last round, decrypt all the ciphertext for the last round, now, you have pairs for attacking the penultimate round with at least better probability. Yes, for AES-256 you need more than one round to recover the full key..
kelalaka avatar
in flag
Once the last round is broken, the rest is broken ( in the differential and linear attack case)..
Score:1
pl flag

The intuition is certainly that the last rounds can be removed one by one. If a differential distinguisher allows us to recognize the $n$-th round key, then surely the differential nonuniformity after $n-1$ rounds that allowed us to do this will be even worse at round $n-2$, so clearly the same trick can be used to recover the round key for round $n-1$ and so on... right?

Like any good intuition, this picture of things is incredibly useful and deeply flawed at the same time.

The most practically relevant objection to this is probably that in many attacks (differential or otherwise) that attack ciphers round by round, we only obtain partial information about the target subkey at each step. In other words, when we have used up all of the information that our differential distinguisher gives us about the last subkey, there might still be a rather large number of remaining reasonable candidates. Now if we have a distinguisher, it is true that the number of these candidates will be lower than if we had to try all of the last subkeys, but going down the rounds back to the source, it is still quite possible that the resulting search tree ends up bigger than the number of possibilities that we would have had to consider had we just done exhaustive search.

The usual two ways for attacks to get around this problem are to either show that the distinguisher is indeed good enough to prevent search tree explosion, or to show that at some point, we do not have to treat subsequent round keys as independent from our current final round key hypothesis any more because we can run the key schedule in reverse. In the former case, we can indeed solve the cipher round-by-round, whereas in the latter case, we end up with a set of candidate master keys that is possibly large but, for a successful attack, still smaller than the set of all master keys. These keys can then be tested against some other known information (most commonly known plaintext-ciphertext pairs) one by one.

The assumption that we can run the key schedule in reverse once we know a sufficient number of subkeys is satisfied for most practical ciphers, but is certainly not a law of nature. One could easily imagine a cipher where the subkeys would be derived from the master key by a one-way function, in which case attacks would indeed have to either resort to brute force search or solve for the subkeys as if they were independent.

There are various other cases where the intuition fails that a technique that allows us to solve $n$ rounds will also allow us to solve $n-1$ rounds; for instance, in differential attacks the distinguisher used to break $n$ rounds could depend on a particular difference in round $n-1$ that transitions to round $n-2$ deterministically, in which case we gain no new information when we descend to round $n-2$, or dependencies in the key schedule could make the expected differential nonuniformity of a cipher go up instead of down as rounds are added (although admittedly, this last case happens only in pathological cases).

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.