4
$\begingroup$

From what I could research, XORing a random key adds confusion.

But I do not undertand the rationale for that classification. Shannon's confusion is supposed to obscure the relationship between the ciphertext and key, but the OTP clearly does not do this: unlike many other ciphers, if one has one plaintext and corresponding ciphertext, then there is a trivial relationship between the latter and the key...

Furthermore, what seems to me that OTP actually does is to rely (only) on diffusion: it makes the redundancy of the plaintext harder to notice, but it does not "get rid" (lacking a better expression) of it. In fact, if one obtains two cryptograms enciphered with the same key, one can then obtain the XOR of the corresponding plaintext messages, which must contain some patterns related to the structure of the original messages. (*)

In sum, I'd say the OTP is based on diffusion, and is secure only because of the sui generis requirement that the key be used exactly once. Where am I going wrong?

(*) - Otherwise one could not use the two time pad to recover the original plaintexts.

$\endgroup$
  • 2
    $\begingroup$ TL;DR I wouldn't be too sure that "confusion" and "diffusion" apply to OTP. I think they rather aim at describing round-based ciphers. $\endgroup$ – SEJPM May 23 '15 at 19:48
5
$\begingroup$

The One-Time Pad employs neither confusion nor diffusion, as defined by Shannon:

"Two methods (other than recourse to ideal systems) suggest themselves for frustrating a statistical analysis. These we may call the methods of diffusion and confusion. In the method of diffusion the statistical structure of $M$ which leads to its redundancy is “dissipated” into long range statistics—i.e., into statistical structure involving long combinations of letters in the cryptogram. [...] The method of confusion is to make the relation between the simple statistics of $E$ and the simple description of $K$ a very complex and involved one."

(It's worth noting that, to really understand these definitions, you should read the full paper in detail. In particular, the earlier definition of a "strongly ideal cipher" that the text alludes to is kind of nontrivial, and not something commonly encountered in modern cryptography.)

In the one-time pad, each ciphertext symbol depends on exactly one message symbol and one key symbol. Thus, there is no diffusion, in the sense used by Shannon, since the relationship between the message $M$ and the ciphertext $E$ is trivial, nor can there be any confusion, since the relationship between the key $K$ and the ciphertext $E$ is equally trivial.

Instead, the perfect secrecy of the one-time pad follows from the fact that the use of a random one-time key masks any redundancy in the plaintext: without knowledge of the key, the ciphertext is statistically independent of the plaintext, and thus no ciphertext statistics can reveal any information about the message. (Such statistics can reveal information about the key, if the attacker can guess some of the plaintext; but since the key is never reused, this makes no difference.)

It should be noted that this does not contradict Shannon's statements in any way: the section where the terms "confusion" and "diffusion" are defined is explicitly concerned only with non-ideal (in the sense defined earlier) ciphers using keys of bounded length. The one-time pad is not such a cipher, and so the statistical analysis techniques that confusion and diffusion are supposed to prevent do not (necessarily) apply to it. Furthermore, Shannon never claims that confusion and diffusion would be the only ways to protect a cipher from statistical analysis; merely that they are two obvious and general ways to (attempt to) do so.

$\endgroup$
  • $\begingroup$ That was a most helpful answer; thank you for taking the time to write it! $\endgroup$ – wmnorth Sep 16 '15 at 17:51
0
$\begingroup$

If one obtains the plaintext and the corresponding ciphertext in OTP, then the key is determined. But the key is used only for one message, otherwise it will be two-time pad attack, and the next key is random. So it does not reveal any information about other plaintexts.

Suppose $M=C=K=\{0,1\}^2$ and we are given the ciphertext $c_i = 10$. Can we deduce any useful information?

Clearly, from the ciphertext $c_i$ there is no way to establish any relationship between the next ciphertext and key because the key is as long as the message, random and used only once. Similarly OTP dissipates the redundancy of the plaintext over the whole ciphertext.

Two-time pad attack is because of the wrong use of OTP. So I think OTP satisfies both confusion and diffusion properties.

$\endgroup$
  • $\begingroup$ As I mulled over your answer, I came up with the following argument to say that the OTP only adds confusion: we can always consider that the OTP enciphers one message of length $n$, where $n$ is the sum of the lengths of all messages thus sent. This can be seen as choosing a random function $F$, and putting $c=F(m)$. Or in other words, the cipher consists of an "SBox" with the input size equal to $n$. Clearly this adds only confusion. Maybe the most important remark about Shannon's confusion & diffusion is that they are not exact concepts... (something he explicitly states in the paper). $\endgroup$ – wmnorth May 27 '15 at 12:36

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.