Hacker News Reader

Comment by alecbenzer | Hacker News Reader

> The output is always random, regardless how often the key has been used.

The output of any _one_ use of the pad is, yes, but the point is to consider all of the data that an attacker may have. If you re-use the key multiple times, then the entirety of the cipher texts an attacker has is not random. (See also: https://xkcd.com/221/)

> But how do you know they're using the same one? Or how are you sure, they're not?

You'll be able to tell because you'll see patterns in the data: https://upload.wikimedia.org/wikipedia/commons/f/f0/Tux_ecb....

View on HN

Note, that illustration (Tux_ECB) is demonstrating a different problem—ECB cyphers may expose patterns across blocks—rather than reused one-time pads. One-time pads will always produce random images as their output.

Eh, it's sort of the same? You can imagine each pixel as its own message: the point is that repeatedly transforming things in a consistent but "random" way isn't actually random. The ciphertext of each pixel is "random", but the pattern when looking at all the pixels is clear.

Your more-than-one-time pad is basically an ECB mode cipher with block size = the length of the message.

Assume you have the OTP: 4242.

You encrypt the data ABCD -> EDGF.

You encrypt the data DEFG -> HGJI

Someone intercepts the data, and has: EDGF and HGJI

And now?

Or maybe like this: Since OTP and data are interchangeable, due to matching lengths, isn't using the same OTP with different data, essentially the same like using the same data with a different key?

Look at an ASCII table. Each byte could be any value, but if you’re sending text data the 8th bit is very likely to be 0. That means if your sending say 10 different messages the same pattern is going to show up 10 different times making it clear something is going on.

That ASCII example is rather extreme, but all messages have patterns as long as you’re given enough of them you can break a reused OTP.

I'm reaching the limits of my stats knowledge, but you may be able to figure out, even from just those two ciphertexts, something about the input plaintexts. It's obviously harder with shorter inputs.

I guess one thing to note is that, if what you were transmitting was just random noise to begin with, OTP re-use may not matter/be evident. But essentially all data that people care about transmitting isn't random noise, it has some structure, and that structure comes through with OTP re-use (more and more the more you re-use and the more data you re-use with).

AIUI, the Enigma machine (not quite an OTP but I think similar) was broken in part because of just a few key re-uses https://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma#Op...

EDGF encrypted with HGJI is now the same as ABCD encrypted with DEFG. In this example, that means the distance between characters of the encrypted messages is the same as the distance between the original messages.

From my limited knowledge of the matter, that alone doesn't give you the cypher - you'll need to know additional information about the messages to get the cypher (statistics of words, conditional probabilities of letter sequences etc.). But without the one reuse of your cypher, you couldn't apply these techniques.

The normal operation for an OTP is xor. Now if you reuse the random key K on messages A and B, you get encrypted messages A' = K xor A and B' = K xor B. Now, an attacker who learns A' and B' just needs to do A' xor B' = A xor K xor B xor K = A xor B. Since your input is not random, but structured data like natural language, this is now relatively trivial to break using crypt analysis since you essentially end up with something like "MEET AT DAWN" xor "I LIKE TRAINS".

Story time: The USSR once reused an OTP key (after years or even decades, can't recall), but a US' three letter agency had the old ciphertext (A') and reused that to break the new ciphertext (B'). They probably had some scheme with a broadcaster saying "use codebook 1234, the secret is GARBLED DATA". At least that's the story a cryptography lecturer told us (and the fragments I remember).

Reply on news.ycombinator.com