3
$\begingroup$

Say that I have

$$ C_1 = AES_{k_1}(M_1) $$

How difficult would it be to find a key, K2 and plaintext M2

$$ C_2 = AES_{k_2}(M_2) $$

such that

$$ C_1 == C_2 $$

How would using a block cipher algorithm other than AES effect this problem?

$\endgroup$
  • 4
    $\begingroup$ Pick any key $k_2$ and decrypt $C_1$ to obtain $M_2$. $\endgroup$ – Thomas Jul 20 '13 at 13:54
  • $\begingroup$ @Thomas I guess I'm asking is there a way to do this without enumerating the entire key space... $\endgroup$ – samoz Jul 20 '13 at 14:01
  • $\begingroup$ Or better yet, what about the scenario where $M_1$ and $M_2$ are fixed. $\endgroup$ – samoz Jul 20 '13 at 14:05
  • 2
    $\begingroup$ @samoz If $M_2$ isn't fixed then Thomas' suggestion works for every key. $\endgroup$ – CodesInChaos Jul 20 '13 at 14:31
  • 1
    $\begingroup$ Some precisions about your question would be useful. 1. As written, the natural interpretation is to consider that $M_1$ is a single-block message. It is really what you intended ? 2. When you say a plaintext $M_2$, people here understand that $M_2$ can be an arbitrary binary string of the right length. Did you intend to say a meaningful message ? If so, you need to add a description of what is acceptable. $\endgroup$ – minar Jul 20 '13 at 19:32
8
$\begingroup$

Take $C_2$ and pick any $k_2$. Then decrypt using $k_2$ so that $M_2 = AES_{k_2}^{-1}(C_2)$. Now obviously we have $AES_{k_2}(M_2) = C_2 = C_1$.

This extends to any blockcipher, because blockciphers are specifically designed to be reversible.


In the comments you asked about the scenario where $M_2$ is also fixed. This is as hard as breaking AES. Consider this problem:

Find $k_2$ given $k_1, M_1, M_2$ such that:

$$AES_{k_1}(M_1) = AES_{k_2}(M_2)$$

Giving $k_1$ (and thereby $M_1$) does not add information for the solver to this problem, because there is no relation between $k_1$ and $k_2$ other than that there exists a ciphertext that was created using both keys - which is non-information because all keys can create such ciphertext given the correct plaintext. Thus the problem with irrelevant information removed becomes:

Find $k_2$ given $M_2$ such that:

$$C_2 = AES_{k_2}(M_2)$$

This is obviously the problem of breaking AES itself.

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