AES - What is the advantage of a 256-bit key with a 128-bit block cipher? [duplicate]

Question

This question already has an answer here:

• AES Key Length vs Block Length 3 answers

I'm just trying to wrap my mind around the decision to select the 128-bit Rijndael as the AES cipher, even with 192-bit and 256-bit keys. Even with a 256-bit key, you only get 2^128 possible outputs per 128-bit block, thus kind of rendering the larger key size meaningless (not to mention the weaker key schedules).

Was this a NIST oversight when standardizing AES?

(Answering this isn't urgent. I'm using libsodium, which uses Xsalsa20 + Poly1305, in most of my projects these days, but it's something I don't readily know the answer to.)

Answer 1

No, this isn't an oversight. AES is a block cipher, which is a keyed permutation. Now if you have a permutation of, say, three elements there are e few permutations possible:

a -> a
b -> b
c -> c

but also:

a -> b
b -> c
c -> a

and

a -> c
b -> a
c -> b

and

a -> c
b -> b
c -> a

(there should be $6$ for $3!$, the factorial of three, I won't write them all out)

Now if you look closely, there are more than 3 permutations possible. The actual number of permutations is higher than the input/output! To be precise, the number of permutations is $(2^{128})!$, which is a lot more than $2^{256}$.

The purpose of the key is to select one of the possible permutations. So the key could be a lot larger than 256 bits and still be meaningful. This also means that there may be multiple keys that map a specific ciphertext block to a specific plaintext block. An attacker may have to validate more pairs to be reasonably sure of success. For instance, in both the last two permutations in the example, a maps to c.

---

The block size is - as Yehuda Lindell writes in the other answer - needed when many blocks are encrypted. For instance when you choose a random nonce for CTR mode, the blocksize must be high enough or you will get overlaps in the counter that is encrypted to create the key stream (i.e. choosing a twice in the example). In that case the key stream would repeat, breaking the stream cipher.

---

An example of a block cipher with a much larger maximum key than block size is Blowfish, which has a block size of 64 bits and a key size of max 448 bits. Blowfish is considered deprecated by the author, Bruce Schneier. Besides other issues, the small block size is a major reason for the deprecation. Both followup ciphers, Twofish and Threefish, expand the blocksize.

Answer 2

There is no NIST oversight here. The key size and the block size are two completely different parameters and issues. The only reason that you need a large block size is because bad things start to happen when you encrypt too many blocks. Specifically, for an $n$-bit block size, the birthday paradox kicks in at $\sqrt{2^n}$. So, for a 128-bit block, you need to encrypt so much that it makes no difference. In contrast, a larger key and more rounds (which is what you get for AES-192 and AES-256) gives you a better security margin against cryptanalysis.