Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
4  
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
2  
@samoz If $M_2$ isn't fixed then Thomas' suggestion works for every key. –  CodesInChaos Jul 20 '13 at 14:31
1  
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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