How were the number of rounds for different key sizes of AES selected?

The number of AES rounds increases with the key length. Why increase the number of rounds at all, and how were these round counts chosen?

-
This question is related to this one. –  user1449 May 21 '12 at 14:49
Maybe this article provides some explanations: research.microsoft.com/en-us/projects/cryptanalysis/aesbc.pdf The math behind the attacks that are detailed in the paper is a bit too much for me, though. –  Mihai Todor May 21 '12 at 16:40
$N_r = len(key)/4 + 6$. –  Chris Smith May 21 '12 at 17:38
Chris Smith, can you elaborate? –  user1449 May 23 '12 at 9:18
As to the choice for the round numbers? Have a look at this document: csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf. Note the "Number of rounds" section under "Motivation for design choices". –  Chris Smith May 23 '12 at 15:40

There are two reasons:

• More rounds means more security against cryptanalysis, simply, since there is more confusion and diffusion.
• For a secure block cipher, there should be no attack faster than exhaustive key search (i.e. brute force). As exhaustive key search takes a lot longer for a larger key size, a theoretical attacker can afford more work to "break" the larger cipher. Thus we also increase the round number a bit to increase the security level of our cipher accordingly.
• For a larger key size (as well as a larger block size), we need more rounds so that every key bit affects every ciphertext bit in a similar way, i.e. without measurable differences which would allow any cryptanalysis.

The 10 rounds for AES-128 seem to be about the lower level of what is (approximately) 128-bit-secure, and 10 rounds for a AES-256-like-cipher would have way below 256 bits of security.

-
keep in mind that while this is generally true for good ciphers (aes, twofish, serpent, etc) there are some attacks that will make the number of rounds a cipher has irrelevant e.g: increasing the number of rounds will not give any additional security against that attack (the slide attack being the one that comes to mind first). –  cipher May 21 '12 at 20:45
@cipher: I used my moderator powers to convert your answer to a comment, as wished. Normally one needs to earn 50 reputation before being able to comment on posts other than your own (or answers to your question). –  Paŭlo Ebermann May 21 '12 at 21:46
Thanks for noting the slide attack, I'll read up on it (but not today). –  Paŭlo Ebermann May 21 '12 at 21:47
Is there a more technical explanation? –  user1449 May 23 '12 at 9:18
This is a bit more detailed in the Rijndael specification (the book one), but I don't have it on hand. Maybe someone else can give a more detailed answer here (I would certainly upvote it). –  Paŭlo Ebermann May 23 '12 at 16:59

A quote from The Design of Rijndael (Section 3.5 "The Number of Rounds")

Two rounds of Rijndael provide 'full diffusion' in the following sense: every state bit depends on all state bits two rounds ago, or a change in one state bit is likely to affect half of the state bits after two rounds. Adding four rounds can be seen as adding a 'full diffusion step' at the beginning and at the end of the cipher.

And also

For Rijndael versions with a longer key, the number of rounds was raised by one for every additional 32 bits in the cipher key.

Unfortunately no derivation of this magic 1:32 ratio is given.

-