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