Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 11 down vote accepted

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 it 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.

share|improve this answer

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.)

share|improve this answer

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.

share|improve this answer
    
I gave this answer on stackoverflow and was immediately modded down :) –  Maarten Bodewes - owlstead Apr 4 '12 at 18:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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