Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

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 invertable? Doesn't this reduce the strength of the cipher?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Now, the AES Key Schedule may be weak (it certainly does appear to be the weakest part of AES), however I don't believe invertability 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 noninvertable, 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 the 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 noninvertable 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 invertable 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 original key is unbiased. Of the keyschedule were noninvertable, 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 invertable key schedule, we don't have to worry about it.
  • One implementation approach that I've seen that some AES hardware take is, if the AES key was to be used for decryption, that 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 noninvertable key schedule (depending, of course, on the details of how it works)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.