AES key expansion: 256bit key

Question

In AES algorithm, in the key schedule, Why does the expansion of a 256 bit key need an extra application of the S-box, unlike the expansion of 128 bit and 192 bit keys ?

(The obvious answer would be "because it is more secure" ... but why ? And if it is more secure, why don't use it on 128 and 192 ?)

Answer 1

It has to do with the alignment between the size of cipher the key and the size of a round key. Since a 256-bit key is twice the size of a round key, the nonlinearity of the key schedule would be aligned to every other block, and that is bad.

Here is an example of the round keys generated by the key schedule for a key (hex bytes) of value 0000000000000000000000000000000000000000000000000000000000000001:

00  00000000 00000000 00000000 00000000
01  00000000 00000000 00000000 01000000
02  637c6362 637c6362 637c6362 637c6362
03  fb10fbaa fb10fbaa fb10fbaa fa10fbaa
04  cf51a96f ac2dca0d cf51a96f ac2dca0d
05  6ac88f7d 91d874d7 6ac88f7d 90d874d7
06  c131c8f9 6d1c02f4 a24dab9b 0e606196
07  c11860ed 50c0143a 3a089b47 aad0ef90
08  a19db82e cc81bada 6ecc1141 60ac70d7
09  118931e3 414925d9 7b41be9e d191510e
10  0aa339ef c6228335 a8ee9274 c842e2a3
11  f9a5a9e9 b8ec8c30 c3ad32ae 123c63a0
12  ea6ad234 2c485101 84a6c375 4ce421d6
13  d0cc541f 6820d82f ab8dea81 b9b18921
14  173c1ad3 3b744bd2 bfd288a7 f336a971

And here is what happens when you take out the extra SubBytes:

00  00000000 00000000 00000000 00000000
01  00000000 00000000 00000000 01000000
02  637c6362 637c6362 637c6362 637c6362
03  637c6362 637c6362 637c6362 627c6362
04  c9d6739b aaaa10f9 c9d6739b aaaa10f9
05  c9d6739b aaaa10f9 c9d6739b abaa10f9
06  50b4df55 fa1ecfac 33c8bc37 9962acce
07  50b4df55 fa1ecfac 33c8bc37 9862acce
08  dbf275cc 21ecba60 12240657 8b46aa99
09  dbf275cc 21ecba60 12240657 8a46aa99
10  358c2f70 14609510 06449347 8d0239de
11  56f04c12 771cf672 6538f025 ef7e5abc
12  5053dcee 443349fe 4277dab9 cf75e367
13  9985af75 ee995907 8ba1a922 64dff39e
14  5b1042a3 1f230b5d 5d54d1e4 92213283

It can be seen as far as round 9 the round keys are still extremely linear, and because the sbox application is performed every other round key, 3 of the 4 subkeys for the round keys are identical to a neighboring round key up to the 9th round, and the 4th only differs by a 4 bit maximum.

Answer 2

To give some general intuition:

Longer keys give the attacker more "degrees of freedom" in a related-key attack. Therefore, defending against related-key attacks likely requires more complex key schedule if the key is long, than if the key is short. That might explain, at a conceptual level, why 256-bit keys require more complexity in the key schedule.

The other possible explanation is that the number of rounds in AES varies based upon the key length. When you use a 256-bit key, AES uses more rounds, so it needs to generate more round-subkeys. That might explain why the key schedule includes extra step for longer keys.

Your best source will be to read the design docs and analysis written by the designers of Rijndael. Have you looked at them? If not, start there.