5
$\begingroup$

Suppose I have two messages $M_1$ and $M_2$ and I have two different symmetric keys $k_1,k_2$.

Is it possible to achieve this?

$CipherText(M_1)_{k_1}$ = $CipherText(M_2)_{k_2}$

Edit: Im asking for standard ciphers used in practice, not for theorical ones.

$\endgroup$
  • $\begingroup$ Are you asking about a particular cipher like AES or are you interested in some academic constructions too? $\endgroup$ – mikeazo Jan 25 '18 at 14:30
  • $\begingroup$ Im asking for ciphers that are used in practice, thanks for pointing it out. $\endgroup$ – llompalles Jan 25 '18 at 14:33
  • $\begingroup$ With the One-time pad (which you should never use anyways), given $M_1$, $M_2$, a random $k_1$, and $C_1$ (the encryption of $M_1$ with $k_1$), I can find (quite easily) a $k_2$ that would decrypt $C_1$ to $M_2$. I didn't post this as an answer as I don't consider OTP to be a "standard cipher". Is there any problem with this scenario (beyond the use of OTP)? $\endgroup$ – mikeazo Jan 25 '18 at 14:35
  • 2
    $\begingroup$ The question is ill-posed: if your already have the messages and keys, then either the equality holds, or not. A better question would be to ask if we can construct $M_1$ or/and $M_2$ matching this for given other variables (the answer is yes for all block ciphers and most ciphers not giving authentication; hint: use decryption to exhibit $M_2$). Or if we can construct $k_1$ or/and $k_2$ matching this for given other variables (that's harder, and practically impossible for many ciphers). We should of course reject solutions with $M_1=M_2$ and $k_1=k_2$. $\endgroup$ – fgrieu Jan 25 '18 at 15:24
  • $\begingroup$ very related answers to this question discuss technicalities of how to do it with modern ciphers. crypto.stackexchange.com/questions/1001/… $\endgroup$ – kodlu Mar 27 '18 at 13:20
6
$\begingroup$

This is actually possible in practice because to us, human beings, a "meaningful message" can be a file.

Now, depending how we encrypt our files, we have more or less slack variables at hand to play around with the resulting ciphertexts.

Ange Albertini played a lot with file formats and he actually has a PoC where he encrypts given images into other files, even valid images... Or where he encrypts a JPG into a PNG if using AES and into a PDF if using 3DES... Or even worse!

The worst part, 3 different files out of a single one (image by Ange Albertini, CC3.0BY)

How comes? Well, this is mostly done by abusing the way the modes of operation work, as well as the way the file formats work.

When you encrypt a file using AES CBC, for instance, you can choose your IV, which means that you can control the first 128 bits of your ciphertext. Furthermore you can also append any plaintext data at the end of your ciphertext, and it will get encrypted when you decrypt your ciphertext, but it also means that you can obtain its corresponding ciphertext so that it gets decrypted when you encrypt your plaintext appended with that ciphertext...

With this two details you already have plenty of room to play around with the file formats in a way that would produce valid files when encrypted/decrypted!

Now, a question that was not addressed by Ange is whether this is secure... Well, as long as you are appending encrypted data or that you are not reusing your IVs, this does actually protects the content of your files (especially Ange's limited deniability example), as long as your secret key remain secret... (But it might be a problem in the case of CBC, depending on your use of the cipher, as it mandates most of the time the IVs to be unpredictable, unlike CTR where it suffices to have unique nonces.)

So, is it possible to do the same in the other direction, decrypting into two different files given different keys? Well, if you can have different IVs, then yes, it is possible using the same kind of tricks that Ange used.

In the end, is this related to the way the actual ciphers work? No, not at all. This is not a cryptographic property, but a consequence of the file formats' malleability.

| improve this answer | |
$\endgroup$
0
$\begingroup$

Since a symmetric encryption is a reversible permutation determined by the key it is always possible to decrypt an encrypted message with another key. Whether the result is meaningful or not depends on the type of message one is using. If we are talking about English texts the answer is that it is rather unlikely. For binary messages the likelihood is higher. It depends on what proportion of possible bit combinations are meaningful messages.

| improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Disagree, take a stream cipher and let's assume my two messages are "dog" and "cat". Pick $k_1$ at random and you should be able to bruteforce $k_2$ fairly easily. The messages are only 24 bits, so finding the right key such that "cat" encrypt to the same thing as "dog" (under the other key) wouldn't take long. $\endgroup$ – mikeazo Jan 25 '18 at 23:56

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.