AES key/ciphertext space sizes

Question

This is giving me a brain ache now... If I have AES-128, block is 128 bit, then every plaintext (128-bit) can be encrypted to some ciphertext that is also 128-bit. This is the block size. But: 128-bit block can have 2^128 different values. So if I have 128-bit key - then it seems to be natural to have every different key produce different ciphertext for a given plaintext - $P_1$. So let's take another plaintext - $P_2$, which also can be encrypted to $2^{128}$ different output blocks - but still the same values - we have the same binary 128-bit block - again $2^{128}$ values - the same values that $P_1$ used. How AES differentiate between the two?

The second question: what about AES-256? Here I have $2^{256}$ keys, but again for given plaintext - $P_1$ I can get no more than $2^{128}$ output blocks, is it that I only have $2^{128}$ unique keys even for AES-256? What about the previous situation - I can have only $2^{128}$ different output blocks- so what's the use of having $2^{256}$ key space? Shouldn't the block size be also increased for AES-256? Or am I making some terrible mistake here?

Answer 1

So if I have 128-bit key - then it seems to be natural to have every different key produce different ciphertext for a given plaintext - p1.

That is not so. AES is a keyed permutation of a 128-bit block, that is, each different key produces a unique permutation. But the key space is not a permutation on the output! In fact, it is very likely there are two different AES keys out there which will both encrypt plaintext A to ciphertext B, for any A and some B (not all A and B, of course, since that would mean the keys are equivalent).

In any case...

How AES differentiate between the two?

You (hopefully) know the encryption key, and that tells you which permutation you want (even in the case that there exist two equivalent keys, which is not the case for AES, afaik).

The second question: what about AES-256? Here I have 2^256 keys, but again for given plaintext - p1 I can get no more than 2^128 output blocks, is it that I only have 2^128 unique keys even for AES-256?

No, all $2^{256}$ keys produce distinct permutations (well, at least they are supposed to). You need to think in terms of permutations here. There are $2^{128}!$ possible permutations of a 128-bit input/output space. This is an unimaginably large number, and $2^{256}$ is considerably smaller than $2^{128}!$.

However, one thing which occurs here, is that it is no longer likely that there exist two distinct 256-bit keys which both encrypt any A to some B. In fact, it is now certain, due to the pigeonhole principle. And that is not a problem.