2
$\begingroup$

I'm researching to see if there is an algorithm that encrypts different inputs with different keys to produce the same output.

So let's say I have 2 messages.

var message1 = "My password is: Doggies!1"
var message2 =  "My password is shdhe93-4" 

And two keys.

var key1 = "DummyKey"
var key2 = "RealKey"

I would like to be able to encryption it like so

var encryptedText = encrypt([message1, message2],[key1,key2]

And decrypt it like so

decrypt(encryptedText, key1) === message1
decrypt(encryptedText, key2) === message2

Is there a standardized way to achieve this?

$\endgroup$
2
  • 2
    $\begingroup$ The term you're looking for is "Deniable Encryption". I'm posting this as a comment rather than an answer because I don't know enough about it to create a decent write-up, but hopefully just knowing the term will help you (or someone else) in your research. $\endgroup$ Jun 28, 2023 at 15:06
  • $\begingroup$ Thanks, just that term will help me vastly in researching $\endgroup$
    – johnny 5
    Jul 5, 2023 at 15:37

3 Answers 3

2
$\begingroup$

If (as in this comment) one does not want to hide that there are different messages according to what key/password is entered on decryption, what's asked in the question is rather easy.

On encryption:

  • Start with empty result.
  • For each (message, key) pair, assumed to contain no duplicate key
    • Strech the key (actually a password at this stage) into a more robust key using e.g. Argon2id.
    • Encrypt and integrity-protect the message using the stretched key (and a proper random IV), e.g. per ChaCha20-Poly1305, getting ciphertext
    • Append to result the length of ciphertext on 8 bytes (per some agreed endianness) then ciphertext
  • Output result which is the overall ciphertext.

On decryption

  • Strech the key/password into a more robust key
  • While there remains data in the overall ciphertext received
    • Read 8 bytes, forming an integer $n$ in $[0,2^{64})$; if EOF is reached doing so, terminate.
    • Read $n$ bytes forming ciphertext; if EOF is reached doing so, terminate.
    • Decrypt and integrity-check ciphertext using the stretched key. If and only if the integrity check passes, output what was decrypted.

Limitations:

  • The decryption time increases about as the sum of the length of the messages. This in isolation is easily fixed with a few extra bytes of overhead allowing to quickly validate if the key/password applies to a given embedded ciphertext.
  • Per the standard assumption that the method is public, anyone can find how many different (message, key) pairs there was on encryption, and their length. That's fixable to a degree, including leaving one knowing the method unable to tell with absolute certainty if there is more messages in a given ciphertext than they know there are (because they have the corresponding key/password)†. However, it's not possible to hide that the method used (if public) leaves open the possibility that there are more messages.
  • The overall ciphertext size grows about as the sum of the length of the messages, even if they share much. Fixing this is possible to some degree for large messages, but somewhat complex if we want to maintain security in the sense that knowing one key/password does not reveal too much about the other messages beyond their length.

These things belong to the field of (Plausibly) Deniable Encryption (PDE). There are a number of softwares attempting that. Problem is that until they come in wide use, merely possessing one can be risky in most situations where one would be useful. Also they do not hide that the overall ciphertext is the result of encryption, as steganography aims at.


† One way to achieve this is to add random segment(s) of length distributed about as the true segments, prefixed by their length; and shuffle true and dummy segments randomly. We can add $1$ dummy segment with probability $0.5$, $2$ with provability $0.25$, $i$ with probability $2^{-i}$. This way, one can never be sure if they hold the key(s) to all the true segment(s).

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for this answer, there is a lot for me to digest, here so it may take a while for me to ask a few more question but it does seem to satisify what I need the main things I care about are 1. The cypher text is the same 2. The user cannot tell how many other keys exist in the message. 3. I may think about always adding a dummy key with padding to help normalize the length of the cypher text, and restrict the message size to assure that it doesn't go beyond that $\endgroup$
    – johnny 5
    Jun 30, 2023 at 19:13
5
$\begingroup$

Is there a standardized way to achieve this?

That's actually a fairly common request - here's the problem - there's no way to do it without making the ciphertext as long as the two plaintext messages concatinated (after compression).

Let us suppose we had a magic box that could take the two plaintext messages and the two keys, and generate a ciphertext that could be decrypted either way.

Then, we could use that magic box to attempt for text compression - we could take our two messages (and pick two arbitrary keys) and generate the ciphertext. That ciphertext is the 'compressed' version of those two texts.

To uncompress them, we just decrypt the ciphertext with the two keys, giving us the original messages.

Because this acts as a lossless compression, it seems unreasonable for us to expect it to work better than known lossless compression techniques.

For example, if the two strings are both random 256 byte strings (that is, uncompressable), then the ciphertext cannot be shorter than 512 bytes.

And, if the magic box picks the keys (in addition to generating the ciphertext), then the limit is one on the total length of the keys and the ciphertext (because then the keys would need to be included in the 'compressed' version...

$\endgroup$
9
  • $\begingroup$ I don't understand the issue. I don't care if the crypher text grows provided that both keys decrypts it differently $\endgroup$
    – johnny 5
    Jun 27, 2023 at 21:52
  • $\begingroup$ Also a longer messages will zip better with the other longer messages so the cypher text doesn't always have to be 2n $\endgroup$
    – johnny 5
    Jun 27, 2023 at 21:54
  • $\begingroup$ The issue is that most normal encryption methods don't expand the plaintext that much; if you have one that does, it makes is suspicious (and brings up the question: is there something else hiding there in the ciphertext?) Usually, when people ask for this, they're trying to avoid such suspicion. $\endgroup$
    – poncho
    Jun 27, 2023 at 22:00
  • $\begingroup$ Yeah but there's a lot of good valid usecases for technology like this other than to avoid suspicion. $\endgroup$
    – johnny 5
    Jun 27, 2023 at 22:06
  • 1
    $\begingroup$ @johnny5 you can use a veracrypt file container to do this $\endgroup$
    – knaccc
    Jun 27, 2023 at 23:27
2
$\begingroup$

I think poncho did well in explaining what would happen if both keys are just arbitrarily sampled from the key space. If you don't have any restrictions on keys, I think you can achieve that using a turn around with dependently generated keys.

For instance, let the cipher to be the OTP. You can get the same encryption $m_1\oplus k_1$=$m_2\oplus k_2$ if $k_2=m_1\oplus k_1 \oplus m_2$.

I'm not sure if that would be workable for you.

$\endgroup$
1
  • 5
    $\begingroup$ Of course, if you get to select the keys, it can be even easier: just do $k_1 = m_1$, $k_2 = m_2$ and the ciphertext can be empty :-) $\endgroup$
    – poncho
    Jun 28, 2023 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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