# For a given plaintext-ciphertext pair, how many valid AES keys are there?

For $PT\in \mathbb{M}$ and $CT\in \mathbb{C}$, let $\mathbb{F}=\{f|f:\mathbb{M}\rightarrow\mathbb{C}\}$ be the collection of all functions from $\mathbb{M}$ to $\mathbb{C}$. Then AES encryption under key $k$ is one of these functions, say $f_k$, such that $f_k(PT)=CT$. Then,

1. Is there any key $k'$ such that $k\neq k'$, but $f_k(PT)=f_{k'}(PT)$?
2. If so then is there any fixed cardinality of such sets of keys?

If $f_k$ is AES the block cipher, then there are $2^{128}$ possible output values for a given plaintext and $2^{|k|}$ possible AES keys, where $|k|$ is either 128, 192 or 256, depending on which AES key size you use.

Assuming AES chooses a random permutation, $g_{PT}(k) = f_k(PT)$ behaves like a pseudorandom function*, so you expect something like $2^{127}$ pairs with AES-128 for a given plaintext, but it is possible that there are none. With AES-192 and AES-256 there are always some colliding keys for every plaintext. You expect every key to have (many) other keys that produce the same ciphertext. Roughly, you expect $2^{255}$ and $2^{383}$ pairs, with multicollisions handled as in the above linked question.

If $f_k$ is AES in some mode of operation, then the answer depends on the length of the message. When message length is close to the key length, you expect a lot of collisions, while if it is higher than twice the key length you expect none due to the birthday bound.

(The previous ignores IV and possible authentication, which depending on mode may make collisions unlikely even for short messages.)

As for whether the cardinality is "fixed", no, it varies with the plaintext. Without exhaustive search or some kind of break in AES, you can only give the expected value.

* Technically not true, since there are related key attacks on AES. You should not rely on $g$ being PRF, but for the purposes of the math here it is probably close enough.

• Bonus question: how to find such a pair :P – Maarten Bodewes Nov 7 '15 at 20:37
• @MaartenBodewes, do you have a cluster for ~$2^{64}$ brute force collision search? – otus Nov 7 '15 at 20:39
• Maybe split the answer in two using "---\n" between two empty lines or use headers... Let me check my pants for such a cluster....no guess not. – Maarten Bodewes Nov 7 '15 at 20:40
• For a 64-bit block, would it be $2^{63}$, and for a 32-bit block, would it be $2^{31}$ pairs? Is that right? – forest May 11 '19 at 5:22