Given two plaintexts $p_1$ and $p_2$, is it possible to find two keys for AES(-CBC) so that $$E_{k_1}(p_1) = E_{k_2}(p_2) $$

I want to make sure that will never happen, or is there any way to prevent that from happening? Because that will make my system unreliable.

  • $\begingroup$ Sorry, my English is not very good, it means deterministic input. $\endgroup$
    – Lich
    Commented Apr 7, 2019 at 9:21
  • $\begingroup$ For example, here are two texts, one is "aaa" and one is "bbb", is it possible to compute two keys let the ciphertext of "aaa" is the same as the ciphertext of "bbb"? $\endgroup$
    – Lich
    Commented Apr 7, 2019 at 9:30
  • $\begingroup$ I've edited our question, make sure that it is what you want. Secondly, could you elaborate on your real problem? What mode of operation you have to use, ECB, CBC, CTR. etc... $\endgroup$
    – kelalaka
    Commented Apr 7, 2019 at 9:47
  • $\begingroup$ Thanks!! This is what I mean. I use the CBC mode. My purpose is to make sure that this is impossible, so that I can make sure that the system I am designing is reliable, otherwise I might consider designing another solution. $\endgroup$
    – Lich
    Commented Apr 7, 2019 at 9:58
  • $\begingroup$ My problem is to prove that different plaintexts can't quickly find two keys in a short time let their ciphertexts are the same. $\endgroup$
    – Lich
    Commented Apr 7, 2019 at 10:01

1 Answer 1


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

The answer of Lindell is important.

For an adversary with infinite computation power it is always possible to find $p_1$ and $p_2$ s.t. $E_{k_1}(p_1) = E_{k_2}(p_2)$. Choose any values $k_1, k_2$ with $k_1 \neq k_2$ and calculate $p_3 = E^{-1}_{k_2}(E_{k_1}(p_1))$ and stop if $p_3 = p_2$, otherwise repeat with different $k_2$.

However if the question is how easy it is to find such $k_1, k_2$ it is a different story.

  • $\begingroup$ Thank you for your answer, this is what I want. $\endgroup$
    – Lich
    Commented Apr 7, 2019 at 12:44
  • $\begingroup$ Is it really "always possible", or just possible with an extremely high likelihood? $\endgroup$
    – forest
    Commented Apr 8, 2019 at 6:22
  • $\begingroup$ It is always possible (for an adversary with infinite computation power) since AES is a bijection and $E_{k_1},E_{k_2}$ share the same input/output space. $\endgroup$ Commented Apr 8, 2019 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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