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?
$\begingroup$
$\endgroup$
5
asked Jul 20, 2013 at 13:41
-
4$\begingroup$ Pick any key $k_2$ and decrypt $C_1$ to obtain $M_2$. $\endgroup$– ThomasCommented Jul 20, 2013 at 13:54
-
$\begingroup$ @Thomas I guess I'm asking is there a way to do this without enumerating the entire key space... $\endgroup$– foobarfuzzbizzCommented Jul 20, 2013 at 14:01
-
$\begingroup$ Or better yet, what about the scenario where $M_1$ and $M_2$ are fixed. $\endgroup$– foobarfuzzbizzCommented Jul 20, 2013 at 14:05
-
3$\begingroup$ @samoz If $M_2$ isn't fixed then Thomas' suggestion works for every key. $\endgroup$– CodesInChaosCommented Jul 20, 2013 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$– minarCommented Jul 20, 2013 at 19:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
