9
$\begingroup$

After reading this paper entitled Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds, I was left wondering why AES's key schedule is invertible.

In the paper, the authors use a related-key-attack to recover the round keys, bit by bit, making some guesses, but they are eventually able to recover the original key by simply putting the round keys through the inverse key schedule.

If the round keys were derived from some one-way function of the key, then this attack would not be possible. Why make the key schedule invertible? Doesn't this reduce the strength of the cipher?

$\endgroup$

1 Answer 1

7
$\begingroup$

Now, the AES Key Schedule may be weak (it certainly does appear to be the weakest part of AES); however, I don't believe invertibility is really the problem.

If someone has a way to get some information on the last-round subkey for an N round cipher, well, he has some information on the original key if the key schedule is invertible; if he determined $k$ bits of that subkey, that is equivalent to knowing $k$ bits of key. Using that to complete the attack is the easiest way to attack the key, and so that's what attacks on AES (and AES variants) do.

On the other hand, if the key scheduling were noninvertible, there is another avenue of attack; gaining information on the last-round subkeys also gives us information about what the cipher state was after N-1 rounds. Using this information, we can presumably use the same style of attack to get information about the N-1 round subkeys. And, since we're asking the distinguisher to go through one less round, it'd presumably be stronger, and hence can be expected to take less effort than recovering the round N subkeys. Then, after recovering the round N-1 subkeys, we can start attacking the round N-2 subkeys, etc.

With this hand-waved approach, the attacker can get the entire set of subkeys with an effort that is only a constant factor greater than obtaining the single round subkey. And, even if knowledge of all the subkeys cannot give us information of the real key, it is enough information to encrypt/decrypt with the keys (which is usually why we're interested in the key in the first place).

Again, published attacks against AES and AES-variants don't take this approach, because it is more work (and harder to specify) than inverting the key schedule; however, it does show that making the key schedule noninvertible won't, by itself, make things that much more secure. If it does make things more secure, it's because that change would prevent someone from finding the last round subkeys, instead of preventing him from parlaying that knowledge into knowledge of the original key.

In addition, making the key schedule invertible does have these benefits in practice:

  • It's easy to prove that each subkey is unbiased (that is, each of the possible $2^{128}$ values is equiprobable), given that the original key is unbiased. If the keyschedule were noninvertible, well, this might not hold (and, in fact, with a 128-bit key, there would likely be values that a particular round key cannot hold). It's not at all obvious if having nonuniform subkeys would lead to a weakness, however with an invertible key schedule, we don't have to worry about it.

  • One implementation approach that I've seen that some AES hardware take is that if the AES key was to be used for decryption, we give the hardware the last round subkey (and possibly next-to-last for 192 and 256 bit AES). Then, as the data was being decrypted, the hardware would run the key schedule in reverse, deriving the previous round key as required. This allows the hardware not to run the full AES key schedule before starting decryption, and also without having the full AES subround keys preprogrammed. This approach may be trickier with a noninvertible key schedule (depending, of course, on the details of how it works).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.