0
$\begingroup$

Suppose to have a chipertext that you can't decrypt, but you know that the plaintext can be A, B or C. Then arrives to you the key which is used to encrypt the chipertext. You can decrypt the chipertext and you get a plaintext equal to A. Is it possible that the original plaintext was B or C and you have received a key such that the decryption process gives as output a different plaintext (A)?

Of course, each A, B and C have a meaning to you, so if you decrypt something else (like D, E, F...) you understand that it is meaningless. Also, i want to add that the source from which you receive the key cannot be trusted, but this doesn't mean that the key is always incorrect.

For clarification:

  1. I receive a ciphertext I can't decrypt
  2. I receive a key to decrypt the ciphertext
  3. I decrypt the ciphertext with the key from step 2 and get the plaintext

How can I be sure that the plaintext obtained is infact the one previously encrypted if I can't trust the source from which I get the key and the ciphertext?

$\endgroup$
  • $\begingroup$ I do not use any algorithm right now, but if you can point to me anyone for which this couldn't happen, i will be very glad to hear that. $\endgroup$ – Daniel Dec 11 '18 at 7:07
  • 3
    $\begingroup$ It is possible to have encryption schemes like this. It's called equivocal encryption. The one time pad is for example fully equivocable. However, full equivocability requires the key to have the same length as the message. There are weaker notions of partial equivocability and somewhere equivocability. (I'll write an answer once I'm not on mobile, unless someone's faster than I am.) $\endgroup$ – Maeher Dec 11 '18 at 7:10
  • $\begingroup$ I guess it's important to clarify: do you want this property? Or do you want to prevent it? $\endgroup$ – Maeher Dec 11 '18 at 7:13
  • $\begingroup$ You can make an allowance in the system that half the message is padding, then key A decrypts one half, key B decrypts the other half. $\endgroup$ – daniel Dec 11 '18 at 7:15
  • 1
    $\begingroup$ some related questions: crypto.stackexchange.com/questions/33255/… and crypto.stackexchange.com/questions/1001/… $\endgroup$ – kodlu Dec 11 '18 at 10:26
1
$\begingroup$

How can I be sure that the plaintext obtained is in fact the one previously encrypted if I can't trust the source from which I get the key and the ciphertext?

In general you cannot. The standard security notions of do not imply any binding. I.e., the definitions do not rule out that, given a key $k$ and a ciphertext $c \gets \operatorname{Enc}(k,m)$ an attacker might be able to find a key $k'$, such that $m' = \operatorname{Dec}(k',c)$ for some $m' \neq m$. In fact, for many encryption schemes, such as block ciphers in some non-authenticated mode of operation, or a stream-cipher this is always possible, since decryption will always succeed with any key. What differs between different schemes is how much control an attacker may have over $m'$. But for many schemes some control, such as ensuring that a few bits have specific values is certainly possible.

Opening an encryption scheme to a different value than was originally encrypted is called equivocation. The one-time pad as described by AleksanderRas is an extreme of an equivocal encryption scheme, being *fully equivocal. I.e., for any ciphertext $c$ and any plaintext $m'$ it is possible to find a key $k'$, such that $\operatorname{Dec}(k',c)=m'$. Being equivocal is in fact a useful property of an encryption scheme in applications such as secure multi-party computation. However, being fully equivocal actually implies the scheme must necessarily have a key size which is as large as the message size. There are relaxed notions of somewhere equivocal and non-committing encryption.

That name of that last notion brings us to the fact that you do in fact want your encryption scheme to not be equivocal. The opposite of an equivocal encryption scheme would be a committing encryption scheme, where the ciphertext serves as a commitment to the plaintext.

At this point your question and in particular the "key-exchange" tag lead me to believe that you are probably not actually looking for an encryption scheme, but a commitment scheme. A commitment scheme allows one party to commit to a message $m$ in a commitment $c \gets \operatorname{Com}(m;r)$. Such a commitment can later be opened usually by revealing the randomness $r$ used in the commitment.

A commitment scheme has two important properties:

  1. It is hiding, meaning that $c$ reveals nothing about $m$.
  2. It is binding, meaning that it is infeasible to equivocate, i.e., to open the commitment $c$ to a message $m'\neq m$.
$\endgroup$
0
$\begingroup$

It is indeed possible (as Maeher correctly pointed out) to have such a property.

Probably the most known encryption system with this property is the one-time pad. It has some limitations, like the key has to be (cryptographically secure) random and the same length as the plaintext.

Procedure:

  1. Encrypt a message $m_1$ with key $k_1$
  2. Now we have a ciphertext $c$
  3. It's now possible to decrypt the ciphertext $c$ with:

    a. The (correct) key $k_1$ and get the resulting message $m_1$

    b. The (incorrect) key $k_2$ and get a different message $m_2$

The problem is, that we can not be sure which key was originally used to encrypt the message $m_1$, because both decryptions could be valid (= make sense).

Let's directly take the example from Wikipedia:

  1. Alice want's to send a message ($m_1$) to Bob

    HELLO

  2. She chooses the key ($k_1$)

    XMCKL

  3. By using modular addition (see the example in wikipedia if this step is unclear) we get the ciphertext $c_1$

    EQNVZ

  4. Bob can now decrypt the ciphertext $c_1$ with the key

    a. $k_1$ (XMCKL) and obtain the intended plaintext message $m_1$

    HELLO

    b. $k_2$ (TQURI) and obtain a different message $m_2$

    LATER

This is possible because both the word HELLO and LATER have 5 characters. It's actually possible to decrypt any ciphertext ($c_1$) to any given plaintext ($m_n$) with the same length.

$\endgroup$
  • $\begingroup$ This fails the last part: if I can't trust the source. $\endgroup$ – kelalaka Dec 11 '18 at 10:59
  • $\begingroup$ You can use Pedersen commitment on the key. $\endgroup$ – kelalaka Dec 11 '18 at 15:21

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.