3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean with collision here? $E_{K_1}(P_1)=E_{K_2}(P_2)$? $\endgroup$ – gammatester Jul 26 '18 at 14:10
  • $\begingroup$ @gammatester finding such a collision would be trivial, just calculate E(K1, P1) and decrypt it with any other key $\endgroup$ – Aemyl Jul 26 '18 at 14:25
  • $\begingroup$ collisions like E(K1, P1) = E(K1, P2) are not possible, since AES is completely reversable $\endgroup$ – Aemyl Jul 26 '18 at 14:26
  • $\begingroup$ I can only think of E(K1, P1) = E(K2, P1) (identical keys at least for some plaintexts) but thats very unlikely $\endgroup$ – Aemyl Jul 26 '18 at 14:28
  • 2
    $\begingroup$ Yes I know, therefore I asked how the OP defines collision. $\endgroup$ – gammatester Jul 26 '18 at 14:28
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually bitcoin currently does about 2^81 blockheader-hash per day (each basically two compression rounds of SHA256) but it does so on specialized (and in the aggregate expensive) hardware namely ASICs -- on comparable hardware I doubt AES (single block) is faster, but It would indeed be fast enough to do 2^64. $\endgroup$ – dave_thompson_085 Jul 27 '18 at 0:59
  • $\begingroup$ AES has a smaller circuit than SHA2. Hence, it would be possible to design ASICs for AES that outperform the mentioned SHA2 AISCs. However, this will not be done without a need... $\endgroup$ – mephisto Jul 31 '18 at 11:11
4
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Thank you for your answer. In your case number 1, if such a collision does not exist, it is due to a general property of the SPN ? In other terms, the bijection is implied by the fact that AES is a SPN ? $\endgroup$ – tyuil Jul 27 '18 at 13:10
  • $\begingroup$ The property is because it’s a block cipher which by definition is a bijection. There are a number of ways to build a block cipher, one of them being an SPN. $\endgroup$ – Yehuda Lindell Jul 27 '18 at 13:12
3
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ @tyuil: These comments should be included in your question. And: Even if you have a 256-bit key 128-bit blocks are encrypted to 128-bit blocks. What function $f$ mapping 256-bit to 128-bit do you have in mind: $f : K_{256} \rightarrow E_{K_{256}}(P)$ for a fixed $P?$ $\endgroup$ – gammatester Jul 26 '18 at 15:46
  • $\begingroup$ Yes. The keys vary, and the plaintext is set. $\endgroup$ – tyuil Jul 26 '18 at 16:32
  • $\begingroup$ It's stronger than "should not". Encryption is an invertible operation, so it must be bijective. Decrypting the common ciphertext can return only one of the plaintexts. $\endgroup$ – bmm6o Jul 26 '18 at 16:41
2
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.