What is the mathematical property stating that it is hard to find a collision in the AES algorithm?

Question

Finding a collision in the AES algorithm is (apparently) hard. Why ?

What is the mathematical property stating that there is a negligible probability to find a collision by taking two random plaintexts and setting the key ?

Here I mean collisions like : $\operatorname{AES}_{K}(P_1)=\operatorname{AES}_{K}(P_2)$, with $P_1$ and $P_2$ being two random plaintexts and $K$ a 128 bits long fixed key.

In other terms, as AES 128 is mapping a 128 bits input to a 128 bits output, how can we be sure that all the outputs will be reached, for a given key ? What is the mathematical property in the design of AES making it a function "nearly" (fully ?) bijective ?

And, for AES-256, if we now set the plaintext and vary the keys (giving a function with input set size equal to $2^{256}$ and output set size equal to $2^{128}$), why is it difficult to find a collision ?

To clarify: for the last question only, I mean collisions like $\operatorname{AES}_{K1}(P_1)=\operatorname{AES}_{K_2}(P_1)$, with $P_1$ being a plaintext and $K_1, K_2$ two 256 bits long keys.

Answer 1

The answers here so far are very problematic. The answer to the question is simple.

1. For every $k$, the function $f(x) = AES_k(x)$ is s bijection and thus by definition, for every $x\neq x'$ it holds that $AES_k(x)\neq AES_k(x')$. This has nothing to do with the security of AES as a pseudorandom anything. Thus, a collision with the same $k$ and different $x,x'$ does not exist.
2. If the question refers to a collision on both key and input, then this is a different story. In this case, in contrast to some of the other answers, it is trivial to find collisions. In particular, choose any $k,x$ and compute $y=AES_k(x)$. Then, choose any $k'\neq k$ and compute $x' = AES_{k'}^{-1}(y)$. With very high probability $x' \neq x$ and thus this is a collision. That is, we have found $k,x$ and $k',x'$ (different to each other) such that $AES_k(x)=AES_{k'}(x')$.
3. If the question refers to a collision of different keys with the same input (i.e., the goal is to find $k,k',x$ such that $AES_k(x)=AES_{k'}(x)$), then it's less clear. However, this is not ruled out in general. For example in DES (or 3DES) this is easy using the notion of weak keys. I'm not sure about AES, but am wary about applying the ideal cipher when the attacker has full control over the keys.

Answer 2

As mentioned in several of the other answers, AES is a family of permutations indexed by the key. Hence there cannot exist any collision of the form $AES_k(x) = AES_k(x')$ for $x\neq x'$.

On the other hand, if we look at the function $f_x: k \rightarrow AES_k(x)$ we should ideally have a random function. Finding a non-random property of this function would be a major step in cryptanalysis of AES. So, with this reasoning the standard reasoning for random functions applies. For AES this means we have a function that maps 256 (192, or 128) bit strings to 128 bit strings. By the birthday paradox we know that an adversary that evaluates $f_x$ $q$ times has a success probability of $\mathcal{O}(\frac{q^2}{2^{128}})$ and that is also the best one can do without a huge improvement in the cryptanalysis of AES. However, this means one can find collisions of that function in about $2^{64}$ AES evaluations. This is already doable: the bitcoin network currently does about $2^{70}$ SHA2 computations per day! And AES is faster than SHA2.

Answer 3

AES is idealised as a pseudorandom permutation, mapping 128 bit strings to 128 bit strings. Being a permutation, it should not produce any collision ($E_k(m_1)=E_k(m_2)$).

UPDATE: If we treat AES as a pseudorandom permutation, then for all plaintext $m$, the outputs of $\operatorname{AES}_{K1}(m)$ and $\operatorname{AES}_{K_2}(m)$ are independent and uniformly random (to all computationally bounded algorithms).

That means $Pr[\operatorname{AES}_{K1}(m)=x]=2^{-128}$ and $Pr[\operatorname{AES}_{K2}(m)=x]=2^{-128}$. Collision as defined in your question means $\operatorname{AES}_{K1}(m)=x \land \operatorname{AES}_{K_2}(m)=x$, the probability is $2^{-256}$.

Answer 4

The reason why AES is a permutation is that it is based on a substitution-permutation network. These construction consists in sequences of highly non-linear "small permutations" applied in parallel on small blocks of the data (the S-boxes), followed by large linear permutations applied on the entire data. The goal of this approach is to implement a "confusion-diffusion" strategy: introduce a lot of confusion locally using S-boxes, which are highly non-linear, and diffuse this confusion across the entire state, using a large permutation (which is linear for efficiency reasons). As all of these core operations are permutations, the resulting AES function is a permutation on its domain (note that when the domain is an interval of the form $[0,2^n]$, breaking an element into small blocks of length $t$, and applying a "small" permutation of $[0,2^t]$ to each block, clearly leads to a permutation over the entire domain).

Answer 5

If $F$ is a block cipher and $F_k(m) = F_{k'}(m)$ then $k,k'$ are a key collision for $F$.

If $F$ is modeled as an ideal cipher, then the analysis given in Changyu Dong's answer holds. Basically such collisions are as hard as you would naturally expect.

In the standard model, the problem of key collision resistance is discussed in:

Buchman et al: On the Security of the Winternitz One-Time Signature Scheme

But it has a bug that is repaired in:

Lafrance and Menezes: On the security of the WOTS-PRF Signature Scheme

From what I understand (from a brief skim of the papers), these papers discuss how to bound the number of key collisions that occur in a secure block cipher, but do not explicitly discuss whether these collisions are actually hard to find.

The final answer does not look very straight-forward. In any case, it seems (to me) like quite a reasonable assumptions that such collisions are hard to find.