Can we always find a key to map a given plaintext block to a given ciphertext block in AES?

Question

I am revising for my exams and I have come across this question in a past paper and I am not confident about it at all.

Assuming that only the smallest permissible key and block sizes can be used I have derived the following:

Possible plaintext blocks: $2^{128}$

Possible ciphertext blocks: $2^{128}$

Possible mappings: $(2^{128})!$

Possible keys: $2^{128}$

My assumption is that it is true that you can find a key given a plaintext and ciphertext since there are significantly way more mappings than there are keys. But then again, are there even enough mappings for that to be possible?

I really feel like I am missing something important here. Are there any hints or suggestions you can give?

Answer 1

The answer is no, such a key need not exist. Let the given plaintext/ciphertext pair be $P,C$ and let $n=2^{128}.$

How many permutations on $n$ points map $P$ to $C$? Clearly $(n-1)!.$ Thus, if we could uniformly sample all possible permutations, the probability that under a given permutation $P$ would map to $C$ is a tiny $$ \frac{(n-1)!}{n!}=\frac{1}{n}. $$

Since the AES keyspace also has size $n,$ the expected number of keys that would have this property is $n\times(1/n)=1,$ provided we assume AES perfectly samples the keyspace with respect to this arbitrary property $P\mapsto C.$ But there are no guarantees that it does so since it uses only 128 bits instead of $\log n!$ bits.

Answer 2

As you said, there are many more possible permutations than keys. So it may be that the permutations that contain the particular mapping are not selected by any key in the tiny amount of $2^{128}$ keys available.