AES - What is the advantage of a 256-bit key with a 128-bit block cipher? 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.)
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 -&gt; a
b -&gt; b
c -&gt; c


but also:

a -&gt; b
b -&gt; c
c -&gt; a


and

a -&gt; c
b -&gt; a
c -&gt; b


and

a -&gt; c
b -&gt; b
c -&gt; 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.