AES Key Length vs Block Length

Question

This answer points out that certain key and block lengths were a requirement for the AES submissions:

The candidate algorithm shall be capable of supporting key-block combinations with sizes of 128-128, 192-128, and 256-128 bits.

My question is this; how can having a key length that is greater than the block size enhance security?

If we look at ECB mode for simplicity, when the key length is equal to the block length we have a permutation relationship between the set of all plaintexts and the set of all ciphertexts.

Once you increase the key length beyond that, you start to introduce collisions. In fact, you only introduce collisions from then on don't you? Collisions in the sense that a key will create the same ciphertext-plantext relationship as another key.

This would lead me to believe that only part of the key-space is unique, and only that part of key-space needs to be brute-forced?

I know that I am clearly incorrect, I just don't understand why.

Answer 1

A block cipher is pretty much a substitution cipher. So let's look at a simple alphabetic substitution cipher. There are 26 different plaintexts and 26 different ciphertexts. The cipher is a permutation of these 26 values. But that does not mean there are 26 different permutations, it means that there are $26! \approx 2^{88.4}$ different permutations, which allows an 88-bit key without equivalent keys.

If you transfer this to an n bit block cipher, which has $2^n$ different inputs/outputs, then there are $(2^n)!$ different permutations, which is ridiculously large ($\approx 2^{2^{135}}$) for $n = 128$, much larger than the $2^{256}$ different permutations addressed by a 256 bit key.

So even a 256-bit key only uses a tiny fraction of the available permutations, and thus there are (probably) no equivalent keys if the cipher is ideal.

Answer 2

Once you increase the key length beyond that, you start to introduce collisions. In fact, you only introduce collisions from then on don't you?

I don't know if there's a proof of that. As a pseudo-random function, the expected value of 128-bit keys that produce a given plaintext-ciphertext pair is one, but that doesn't mean that there can't be collisions.

This would lead me to believe that only part of the key-space is unique, and only that part of key-space needs to be brute-forced?

Let's say you do manage to find a 256-bit key key that decrypts the first message block. That's only one of roughly $2^{128}$ keys that do. Unless it also decrypts the subsequent message blocks, it's not the right key, and you're not even one step closer to finding it.

It would be different if there was an easy method to derive all the keys $K'$ such that $AES(K',M)=AES(K,M)$, but that's not the case.

Answer 3

I had the exact same question.

The mistake you make is that the length of key does not determine

How many different ciphertexts can correspond to a single plaintext? (e.g. p(A) = A or p(A) = B or p(A) = C)

which would make the number of possible bijections an exponential function ($2^{n}$) of the key length, but it does determine

How many different permutations of ciphertexts can correspond to all plaintexts listed? (e.g. p(A) = A and p(B) = B and p(C) = C OR p(A) = A and p(B) = C and p(C) = B; note that p(A) = A holds in both cases)

which makes the number of possible bijections a factorial of the exponential function ($(2^{n})!$) of the key length - which means the length of the keys can be many times larger than the block size, without causing collisions.