# How difficult is it to find the “pre-image” of a block cipher?

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?

• Pick any key $k_2$ and decrypt $C_1$ to obtain $M_2$. – Thomas Jul 20 '13 at 13:54
• @Thomas I guess I'm asking is there a way to do this without enumerating the entire key space... – samoz Jul 20 '13 at 14:01
• Or better yet, what about the scenario where $M_1$ and $M_2$ are fixed. – samoz Jul 20 '13 at 14:05
• @samoz If $M_2$ isn't fixed then Thomas' suggestion works for every key. – CodesInChaos Jul 20 '13 at 14:31
• 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. – minar Jul 20 '13 at 19:32

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.