20
$\begingroup$

I understand the basics of OTP: $|\text{key space}| = |\text{plaintext space}|$ implies perfect security, key reuse destroys this.

Cryptanalysis on the $N$-Time Pad for $N > 1$ involves finding patterns in the ciphertext; this, however, all seems based on the premise that patterns exist in the plaintext (e.g. English language).

My question is: if $m_1$ and $m_2$ are two truly random strings, and they are both encrypted with the same OTP key to yield $c_1$ and $c_2$, is it possible to recover $m_1$ and $m_2$ from $c_1$ and $c_2$?

In other words: while "perfect security" (aka perfect indistinguishability) is obviously lost (constructing a distinguisher for two messages is trivial), is the plaintext still safe?

$\endgroup$

3 Answers 3

16
$\begingroup$

Yes, encrypting two different random "plain texts" with the same "pad" is indistinguishable from using two different random one time pads for encrypting the same plain text. You get perfect secrecy in the latter case, so you will get corresponding secrecy in the former case as well.

However, usually there is a functional difference between the key and the plain text that the above argument doesn't account for. More precisely, the recipient will usually "do things" with the plain text once decrypted, and in that respect the above argument might fail.

For instance, if the random messages are symmetric encryption keys for a cipher that is vulnerable to a related key attack, it is obviously not safe to transport those messages encrypted with a reused pad.

$\endgroup$
7
  • $\begingroup$ I am not so sure about your initial argument. In the case of encrypting a single message with two independent pads you do not reduce the entropy of the message. In the case of encrypting two random messages with the same pad you reduce the entropy on the random messages to that of the pad (i.e., entropy is halved). So you can not claim "perfect secrecy" in the latter case. $\endgroup$
    – Guut Boy
    Jan 27, 2016 at 15:28
  • $\begingroup$ a xor b || a xor c = b xor a || c xor a. The entropy is exactly the same. $\endgroup$ Jan 27, 2016 at 16:17
  • $\begingroup$ That is my point, the entropy is the same but in one case your message is twice as long. Since perfect secrecy says you should preserve the entropy of the message, in this case you only have half the entropy you should have. $\endgroup$
    – Guut Boy
    Jan 27, 2016 at 17:41
  • $\begingroup$ Isn't your point covered by the second paragraph in my answer? You will preserve the entropy of the message if you discard it immediately after transmission, but only then, and that's typically not what you want to do with messages. $\endgroup$ Jan 27, 2016 at 17:52
  • $\begingroup$ No, it is not. I also don't see how discarding messages changes the entropy of the random messages in the adversary's view. Think of it this way: in order to guess two random messages each length n bits, given proper OTP ciphertexts you must guess 2n bits. You can do this with probability 2^{-2n} at best. However, if the two messages are OTP encrypted with the same key the all you need to do is guess the n bit key. You can do this with probability 2^{-n}. I.e., you lost at least n bits of entropy by misusing OTP. $\endgroup$
    – Guut Boy
    Jan 27, 2016 at 21:36
9
$\begingroup$

If you encrypt the messages $m_1$ and $m_2$ with the pad $p$ as

$$\begin{aligned} c_1 &= m_1 \oplus p, \\ c_2 &= m_2 \oplus p, \end{aligned}$$

where $\oplus$ denotes the binary operation of a finite group (e.g. addition on integers modulo $n$, or XOR on bitstrings, etc.) and $p$ is a random element of the group, then, indeed, an attacker who intercepts only $c_1$ and $c_2$ will not be able to recover either $m_1$ or $m_2$. However, the attacker can recover

$$\begin{aligned} c_1 \oplus c_2^{-1} &= m_1 \oplus p \oplus (m_2 \oplus p)^{-1} \\ &= m_1 \oplus p \oplus p^{-1} \oplus m_2^{-1} \\ &= m_1 \oplus m_2^{-1}, \end{aligned}$$

where $x^{-1}$ denotes the group inverse of $x$.

(It's somewhat interesting to note that the group does not even need to be abelian for this to work: all we need is a practical way to compute inverses and apply the group operation.)

Thus, the attacker does gain information about the relationship between $m_1$ and $m_2$. In particular, if they later find out either of the messages, they will know the other one too — and, more generally, any information the attacker obtains about one of the messages will give them information about the other one.

Essentially, if the keyspace (i.e. the group from which $p$ was randomly chosen) has $n$ elements, then knowing $c_1 \oplus c_2^{-1} = m_1 \oplus m_2^{-1}$ narrows the number of possible values of $(m_1, m_2)$ from $n^2$ to $n$.

All of the above holds regardless of how the messages $m_1$ and/or $m_2$ are chosen. If both (or even just all but one) of them are completely random, and if you can guarantee that the attacker will never gain any information about the random messages beyond what they've obtained from the ciphertexts, then this knowledge will, indeed, do them no good. But, as others have pointed out, this pretty much rules out using the messages for anything. (In particular, using $m_1$ and $m_2$ as one-time pads to transmit further messages would be a very bad idea.)

$\endgroup$
6
$\begingroup$

You would retain perfect security in the situation you described.

Consider your question in reverse. Use the ciphertext as a OTP and use the n-time-pad as the ciphertext. Since your ciphertexts are random their concatenated result is also random and would qualify as an OTP. At this point is doesn't matter what the OTP was, the conditions for perfect security have been met.

This conclusion is a bit startling. You can reuse an OTP to securely transmit data as long as that data is indistinguishable from random (essentially it must be random).

However you cannot use the random data in an observable way.

Consider: Alice has two comm channels. One only transmits random data, using a secret n-time-pad, known to Bob. Alice also sends messages to Bob, using OTP encryption. Those OTP's are sent to Bob via the first comm channel. If Eve can observe both channels, she can brute for the secret n-time-pad exactly as if it had been used to encrypt original message.

$\endgroup$
1
  • $\begingroup$ I gave this answer on stackoverflow and was immediately modded down :) $\endgroup$
    – Maarten Bodewes
    Apr 4, 2012 at 18:54

Your Answer

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

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