Score:2

Reconstructing the AES-192 key out of the last roundkey

cn flag

Lets assume we know the last-round key of AES.

For AES-128, the whole key can be reconstructed using the last-round key since every WORD in the key schedule is based on the previous 128-bit entry.

For AES-256, it cannot be reconstructed, as we only know 128-bits. However, the reconstruction of the 4 WORDS would take us $2^{128}$ steps (bruteforce).

Now the question comes for AES-192, since we do not know either 64 or 96 bits of (2 to 3 WORDS), can we still bruteforce it?

fgrieu avatar
ng flag
Hint: Examine the key [schedule](https://en.wikipedia.org/wiki/AES_key_schedule#The_key_schedule). Identify what you know, and what you are missing to be able to reconstruct all the round subkeys. The answer will follow.
cn flag
@fgrieu I already did that, in AES192 you are able to reconstruct 3 out of 6 WORDs, my question is: is it enough to bruteforce it and retrieve the key? Is bruteforcing 2^96 a challenge? In worst case it could be bruteforcing 2^64 since the first WORD is xored with a value we already know from the last round key
fgrieu avatar
ng flag
For the difficulty of bruteforcing $2^{96}$, see [this](https://crypto.stackexchange.com/a/13305/555). Back to your question: I suggest you look at the [AES key schedule](https://en.wikipedia.org/wiki/AES_key_schedule#The_key_schedule) again, asking yourself: exactly what $W_i$ get known when a good fairy tells the last round key? How many other $W_i$ (that you select) does the good fairy need to tell before you can reconstruct all the $W_i$ systematically?
cn flag
@fgrieu For the AES192 key, the fairy told us the W48-51. We need W42-47 to reconstruct the key. From the last key we can easily get W43, W44 and W45. W46 is completly not related to the last roundkey, while W48, which is known to us, is related to W42 and W47, since its the result of: W48 = W42 xor g(W47). The question is, does the last equation make it easier to not do an 2^96 search, since we could search both of these information parallelly? Since if we find the right W42, we automatically find the right W47 and vice versa
fgrieu avatar
ng flag
Yes the fairy tells us W48-51. No we don't need all of W42-47. Hint: Assume the fairy gave W46-51, write the equations for these and deduce more Wi.
cn flag
@fgrieu since we know W46-51, we know 5/6 of the forelast roundkey. We can calculate W43-W45 out of W48-W51. If we know W47 and W48, we can easily compute W42, since W42= W48 xor g(W47). Therefore we recomputed the whole forelast key and can invert the key schedule to calculate all the previous keys. So Im a bit confused now, since it is an easier assumption on how to reconstruct the AES192 key, knowing even more than only the last roundkey
fgrieu avatar
ng flag
Don't be confused. You just showed that if you have the last round key, and 64 other bits (W46-47) about the key, then you can compute all the round keys, thus can compute AES with the full key. With the last round key only, and a plaintext/ciphertext pair (a standard assumption), you can test a guess of these other 64-bits, very selectively. That's all you need for a bruteforce attack.
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.