3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$$

$\endgroup$

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.