Is this OTP scheme safe?

I have a message $m_1$ and I want to encrypt it by XORing it with two keys $k_1$ and $k_2$:

$$c_1 = m_1 \oplus k_1 \oplus k_2$$

So far so good.

Now I was wondering if I could create a "fake" result with a different message $m_2$:

$$c_2 = m_2 \oplus k_1 \oplus k_2$$

This way, if I'm forced to hand over $c_1$, I can give $c_2$ instead and $m_2$ will be reconstructed (instead of $m_1$). I know OTP keys shouldn't be reused, so maybe this can't be called OTP (or can it?).

So the question is: Is this safe? Can $m_1$ be reconstructed from anything different than $k_1$, $k_2$, and $c_1$? Eg: $c_2$, $c_1$, and $k_2$. Don't consider $m_1$ and $m_2$ as options since they are gone after the encryption, they aren't stored anywhere.

Note 1: The messages and keys have a fixed length, about 150 characters, which isn't a lot. This doesn't give enough material for cryptanalysis, right?

Note 2: Each key is going to be given to a different party; that's why I don't combine $k_1$ and $k_2$ into a single key.

-
Are you going for plausible deniability? You might want to clean up some of the notation, it's rather confusing at the moment. $K_3$ and $K_4$ are apparently ciphertext and $K_1 \oplus K_2$ may as well be merged into a single variable $K$ as they cannot be separated. –  Thomas Jun 7 '13 at 11:24
@Thomas I wanted to give each K to a different party to keep them safe, so I need them separated to better understand the problem. But yes, I should learn the notation. –  ChocoDeveloper Jun 7 '13 at 11:45
Just encrypt $m_1$ with $k_1$ by XORing: $c_1 = m_1 \oplus k_1$. If you are "forced" to turn over your keys, it is trivial to forge a key $k_2$ such that the decrypted message comes out to whatever you'd like it to be. $k_2 = c_1 \oplus m_2$ where $m_2$ is some innocuous message of the same length as $m_1$. –  Stephen Touset Jun 9 '13 at 1:49
@StephenTouset I don't want to have to forge it when I'm forced, I need to have it prepared beforehand. That's why I want to know whether I'm spoiling the security (and to what degree) by reusing the keys, even if it is for a fake message. –  ChocoDeveloper Jun 9 '13 at 2:14
So forge it now. –  Stephen Touset Jun 9 '13 at 4:45

To allow effective cryptanalysis of a scheme, two things must be clear: first, our goal (e.g., what we want to keep secret, what we want to preserve the integrity of, etc.), and second, what the attacker(s) are allowed to know or do.

So, our goal is to preserve the secrecy of $m_1$, I take it. So, the attacks will try to find it.

Now, what can the attacker know? This seems much less certain in your question. There are really four items your question, excluding the messages: $c_1$, $c_2$, $k_1$, and $k_2$. So, not having any solid ground to go on from your question, let's simply enumerate the various combinations of what attackers could know. At the end, we can observe what breaks the scheme and what doesn't.

First, let's see if an attacker knowing any two items could break the scheme. $\binom{4}{2} = 6$, so there are six sets of two-items-each that an attacker might gain.

Option 1: Let the attacker know $c_1$, $c_2$.

In this case, the attacker can compute

$$c_1 \oplus c_2 = m_1 \oplus m_2$$

which might break your messages, or at least give an idea of what they say. I'm not going to say much else on this; look up the consequences of a two-time pad, since that is what this is. In short, you probably don't want this to happen.

Options 2, 3, 4, 5: Let the attacker know one key and one ciphertext.

In this case, the key the attacker doesn't know still acts as a one-time pad on that message. So, this is a 'safe' situation.

Options 4, 5: Let the attacker know $k_1$, $k_2$.

Not much to say here. Without a ciphertext, they're not going anywhere.

In sum, only option 1 is scary here.

Second, let's see if an attacker knowing any three items could break the scheme. $\binom{4}{3} = 4$, so there are four sets to consider. (As an aside, $\binom{n}{n-1} = n$, more generally.)

Options 1, 2: Let the attacker know $c_1$, $c_2$, and $k_i$, where $i$ is a fixed 1 or 2.

The same situation as option 1 above happens: the attacker can compute

$$c_1 \oplus c_2 = m_1 \oplus m_2$$

which again is a two-time pad and might be vulnerable. The introduction of another key is not terribly useful here, as I don't see any way to get any information more useful than $m_1 \oplus m_2$.

Option 3: Let the attacker know $c_1$, $k_1$, and $k_2$.

Broken! (Obviously.) Compute

$$c_1 \oplus k_1 \oplus k_2 = m_1.$$

Option 4: Let the attacker know $c_2$, $k_1$, and $k_2$.

This the scenario you presented in your question. In this case, all the attacker can recover is $m_2$, since he doesn't have any ciphertext even relating to $m_1$.

In sum, options 1, 2, and 3 are the scary ones.

I question this scenario though. Attackers don't usually ask for ciphertexts; they intercept them. Generally, we would assume communication across a line that is wiretapped, say, by an eavesdropping party (usually named Eve). And when authorities are forcing you to reveal anything, it's the encryption keys. They usually already have the ciphertext(s). Usually.

I agree with Stephen Touset, however. You can prepare, in advance, a "fake" key that, when used, will decrypt the ciphertext to whatever message you so desire. In this case, there is only one ciphertext to be intercepted or known, while you (alone) have two separate keys. One key is for the real message and would be well-hidden. The other would be less-well-hidden, enough so to fool an authority figure, and it would be the one you reveal when compelled. This has the advantage of allowing surveillance while simultaneously knocking out the need for other people to hold on to your keys for you.

-
Perfect, thanks a lot! –  ChocoDeveloper Jun 10 '13 at 0:12

If you have $c_2$ and $m_2$ you can reconstruct the used key by

$$k' = m_2 \oplus c_2$$

Now I have the key to decrypt $c_1$.

Also know that using multiple keys for OTP does not increase the security as the resulting key is

$$k'' = k_2 \oplus k_3$$

-
You are right. Maybe I should have specified that M1 and M2 are both gone after the encryption, since that's why I'm using encryption in the first place: to protect the message. –  ChocoDeveloper Jun 7 '13 at 11:42
About your second point: I should have specified that each key is going to be given to a different party. It's a 3-of-3 scheme, where you need to recover all 3 parts to reconstruct the message. –  ChocoDeveloper Jun 7 '13 at 11:44
It doesn't matter if M1 and M2 are gone. You have been forced to turn over your keys. They can produce M1 and M2 from C1 and C2 trivially. –  Stephen Touset Jun 9 '13 at 1:47
@StephenTouset When they ask for the 3 parts needed to reconstruct m1, I won't hand over k1, k2, and c1. I will hand over k1, k2, and c2, and they will reconstruct m2, which is the fake message. –  ChocoDeveloper Jun 9 '13 at 2:09
@StephenTouset But that's only if I have access to all 3 parts in the first place. Normally I won't. I will keep only 1, and give the other two to other parties. –  ChocoDeveloper Jun 9 '13 at 2:11
show 1 more comment