AES-128. Do there exist two different keys for a pair (text, encrypted text)?

I have two very close questions.

Question 1

y = AES-128(x, key).
Is it possible that AES-128 will return the same y (encrypted text) for different keys?

I know that each key selects one permutation from the set of (2^128)! possible permutations. We have (2^128) possible keys and it is less than number of possible permutations. But it doesn't mean that there are no two different keys for some pair of text and encrypted text.

Question 2

If we have fixed x,y (both of them have the size of 128 bit) does there exist a key( key size is 128 bit) so that y = AES-128(x, key) ?

Example.
We have 2 bit message and 2 bit key. There are 4 possible messages: msg1 = {0,0}, msg2={0,1}, msg3 = {1,0}, msg4 = {1,1} and there are 4 possible keys. We have 4! = 24 possible permutations of messages.
I can select the next permutations

| From\key | key1 | key2 | key3
--------------------------------
| msg1     | msg2 | msg3 | msg4
--------------------------------
| msg2     | msg1 | msg4 | msg3
--------------------------------
| msg3     | msg4 | msg1 | msg2
--------------------------------
| msg4     | msg3 | msg2 | msg1
--------------------------------


Here I have a mapping from a message to every message. e.g. I can get msg4 from msg1 using key3. Has the AES-128 the same property for the mentioned x,y?

$\newcommand{\given}{\mathrel{|}}$Answer 1.

Let $\pi_0, \pi_1$ be independent uniform random permutations of $\{0,1\}^{128}$. What is the probability that for any fixed string $x \in \{0,1\}^{128}$, $\pi_0(x) = \pi_1(x)$?

For any fixed string $x$ and each $i$, the variable $\pi_i(x)$ is a uniform random element of $\{0,1\}^{128}$. (Only if we consider multiple distinct inputs $x_0 \ne x_1$ does the fact that $\pi_i$ is a uniform random permutation rather than a uniform random function come into play, when we consider whether repeated elements are possible in $\pi_i(x_0), \pi_i(x_1)$.) Since $\pi_0$ and $\pi_1$ are independent, so are $\pi_0(x)$ and $\pi_1(x)$.

Thus \begin{align*} \Pr[\pi_0(x) = \pi_1(x)] &= \sum_y \Pr[\pi_0(x) = y \given \pi_1(x) = y]\cdot\Pr[\pi_1(x) = y] \\ &= \sum_y \Pr[\pi_0(x) = y]\cdot\Pr[\pi_1(x) = y] \\ &= \sum_y 2^{-128} \cdot 2^{-128} = 2^{128} \cdot 2^{-128} \cdot 2^{-128} = 2^{-128}. \end{align*}

What if instead of uniform random $\pi_i$ we had $\pi_i = \operatorname{AES}_{k_i}$ for uniform random strings $k_i$? If you could predict how that would affect the distribution nonnegligibly, you could distinguish AES from a uniform random permutation, violating the pseudorandom permutation family property that it is conjectured to exhibit, and there would be lots of cryptographers who would like to have a word with you.

So, for any fixed plaintext $x$, does there exist a pair of keys $k_0, k_1$ under which $\operatorname{AES}_{k_0}(x) = \operatorname{AES}_{k_1}(x)$? Maybe, but you're not likely to find them—for each plaintext, only $1/2^{128}$ of the $2^{256}$ possible pairs $(k_0, k_1)$ of these keys is likely to work! (It's not guaranteed that any of them will work, but it would be a remarkable publication if you could say one way or another about that guarantee.)

Does there exist any plaintext $x$ such that there exists a pair of keys $k_0, k_1$ under which $\operatorname{AES}_{k_0}(x) = \operatorname{AES}_{k_1}(x)$? Note the order of quantifiers: We are not asking about some particular fixed $x$; we are asking whether there is any pair of keys that agrees on any plaintext. This is a little trickier. To approximate an answer, let's first try the uniform random function model. A random function is not restricted to be a permutation, so its values at two distinct points are independent, which makes the analysis a little easier.

In the uniform random function model, what is the probability that there exists a plaintext $x$ on which two random functions $f_0$ and $f_1$ agree, $\Pr[\exists x. f_0(x) = f_1(x)]$? We can answer this by answering it in the complement: what is the probability that for all plaintexts $x$, two random functions disagree on $x$?

\begin{align*} \Pr&[\exists x. f_0(x) = f_1(x)] \\ &= 1 - \Pr[\neg\exists x. f_0(x) = f_1(x)] \\ &= 1 - \Pr[\forall x. f_0(x) \ne f_1(x)] \\ &= 1 - \prod_x \Pr[f_0(x) \ne f_1(x)] \\ &= 1 - \prod_x \bigl(1 - \Pr[f_0(x) = f_1(x)]\bigr) \\ &= 1 - \prod_x (1 - 1/2^{128}) = 1 - (1 - 1/2^{128})^{2^{128}}. \end{align*}

That may look painful to evaluate, but it's turns out to be approximately $1 - e^{-1} \approx 63\%$, since $(1 + x/n)^n \to e^x$ as $n \to \infty$. (This is why you should pay attention in calculus, kids!)

That's the probability that there exists an input on which two uniform random functions agree. Of course, AES isn't even conjectured to be a random function—it's designed to be a random permutation. How does this answer change if we use random permutations $\pi_i$ instead of random functions $f_i$? The crux is that $\pi_i(x)$ and $\pi_i(\xi)$ for $x \ne \xi$ are dependent—they cannot be equal—whereas $f_i(x)$ and $f_i(\xi)$ are independent.

So let's consider how that affects the expansion of $\Pr[\forall x. \pi_0(x) \ne \pi_1(x)]$, first by examining the case of two distinct inputs $x \ne \xi$, and expanding with the chain rule:

\begin{align*} \Pr&[\pi_0(x) \ne \pi_1(x), \pi_0(\xi) \ne \pi_1(\xi)] \\ &= \Pr[\pi_0(x) \ne \pi_1(x) \given \pi_0(\xi) \ne \pi_1(\xi)] \cdot \Pr[\pi_0(\xi) \ne \pi_1(\xi)]. \end{align*}

For the case of $f_i$, by independence of $f_i(x)$ and $f_i(\xi)$ we reduced this to

\begin{align*} \Pr[f_0(x) \ne f_1(x)] \cdot \Pr[f_0(\xi) \ne f_1(\xi)] = (1 - 2^{-128}) \cdot (1 - 2^{-128}). \end{align*}

How do the left-hand factors compare? We can expand the permutation case by Bayes' rule:

\begin{align*} \Pr&[\pi_0(x) \ne \pi_1(x) \given \pi_0(\xi) \ne \pi_1(\xi)] \\ &= 1 - \Pr[\pi_0(x) = \pi_1(x) \given \pi_0(\xi) \ne \pi_1(\xi)] \\ &= 1 - \Pr[\pi_0(x) = \pi_1(x)] \frac{\Pr[\pi_0(\xi) \ne \pi_1(\xi) \given \pi_0(x) = \pi_1(x)]} {\Pr[\pi_0(\xi) \ne \pi_1(\xi)]} \\ &= 1 - \Pr[\pi_0(x) = \pi_1(x)] \frac{1 - \Pr[\pi_0(\xi) = \pi_1(\xi) \given \pi_0(x) = \pi_1(x)]} {1 - \Pr[\pi_0(\xi) = \pi_1(\xi)]} \\ &= 1 - 2^{-128} \frac{1 - 1/(2^{128} - 1)}{1 - 1/2^{128}}. \end{align*}

The quantity $1/(2^{128} - 1)$ arises because if $\pi_0(x) = \pi_1(x)$, the common value is excluded from the possible values of $\pi_0(\xi)$ and $\pi_1(\xi)$.

Thus, $$\Pr[\pi_0(x) \ne \pi_1(x) \given \pi_0(\xi) \ne \pi_1(\xi)] > \Pr[f_0(x) \ne f_1(x)],$$ from which we can conclude that $$\Pr[\forall x. \pi_0(x) \ne \pi_1(x)] > \Pr[\forall x. f_0(x) \ne f_1(x)].$$ This further means that $$\Pr[\exists x. \pi_0(x) = \pi_1(x)] < \Pr[\exists x. f_0(x) = f_1(x)],$$ so there's less than about a 63% chance that any pair of permutations chosen uniformly at random agree on any plaintext.

Turning back to AES, we might guess that for about 63% of the key pairs $(k_0, k_1)$ there is a plaintext $x$ with $\operatorname{AES}_{k_0}(x) = \operatorname{AES}_{k_1}(x)$. Not bad odds for existence—but will you find them by flailing around randomly, which is about the only thing you can do until you're ready to publish a novel cryptanalysis of AES? No—there's too much hay in that stack of $2^{128}$ possible plaintexts.

• No, I might have done something horribly wrong toward the end, because obviously there's no way the probability of any triple $(\pi_0, \pi_1, x)$ having $\pi_0(x) = \pi_1(x)$ is anywhere near $e^{-1}$. I must have meant something like the probability for any $x$ that there exists such a pair $(\pi_0, \pi_1)$ satisfying that. Pooh. – Squeamish Ossifrage Nov 6 '17 at 20:59