AES Key Length vs Block Length 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.
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.