# 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 ciphertext. 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.

-
Perfect thanks, my confusion was about '26 different permutations'. It's clear now. – lynks Dec 17 '12 at 13:54
What do you mean by 26 plaintexts and 26 ciphertexts? That would only be the case for a single-character message, for which there is one permutation (the identity) and 26 possible substitutions. – Stephen Touset Dec 17 '12 at 21:26
@StephenTouset The single-character case is the case when we look at this substitution cipher as a block cipher – one character in, one out. – Paŭlo Ebermann Feb 19 '13 at 17:43
I'm not sure how I missed that on my first read-through. Apologies. – Stephen Touset Feb 19 '13 at 18:32

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.

-
+1 for your final paragraph – lynks Dec 17 '12 at 14:39