An (Important) Disproof of the One-Time Pad

http://techcrunch.com/2015/08/16/a-disproof-of-the-one-time-pad/?ncid=rss&utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+Techcrunch+%28TechCrunch%29

by chris-at • 11 years ago

8 16 11 years ago

techcrunch.com

pckspcks• 11 years ago

And, sadly, completely incorrect.

isaacg• 11 years ago

This entire article is utterly false and misconceived. It asserts that because "ONETIMEPAD" will be encrypted as "ONETIMEPAD" one time in 141167095653376, one time pads are not actually secure. The reason this is false is that just as often, "ONETIMEPAD" will be encrpted as "TWOTIMEPAD", or any other 10 letter string. Thus, the encryped string provides no information about the plain text, and so is perfectly encrypted. This article utterly wrong.

camperman• 11 years ago

I agree. The fallacy in his reasoning is here:

"Let’s choose the very first key (in alphabetical order): AAAAAAAAAA. When we encrypt our plaintext of ONETIMEPAD with this key, we end up with a ciphertext of… ONETIMEPAD. Oops."

Yeah, so what? He knows the plaintext already. An attacker doesn't and as you point out, there's nothing in the key that provides any information about the plaintext.

dragonwriter• 11 years ago

Yes.

For a different illustration, sure, with the right key, a plaintext of "ATTACK US AT DAWN" will have a ciphertext of "ATTACK US AT DAWN". Which, you know, in isolation, sounds undesirable. But a ciphertext of "ATTACK US AT DAWN" will be equally likely (from an attacker's perspective, who has no advance knowledge of the plaintext content or the key) to correspond to a plaintext of "ATTACK US AT DUSK" or "ABORT US ATTACKS" or "DEFEND UK AT DUSK" or "LAUNCH FAST DRONE".

(In fact, if you could guarantee that the ciphertext was never the plaintext, that would be an undesirable feature, because then if you knew the ciphertext and the encryption method without knowing the key or plaintext, you would learn information about the plaintext -- specifically, that it was not whatever the ciphertext was.)

remram• 11 years ago

In fact, the fact that a letter could not encrypt to itself was part of the weaknesses of the Enigma machines used by the Germans during WWII, which eventually led to its breakage.

benmmurphy• 11 years ago

tldr:

an adversary could make a really lucky guess at the key therefore onetime pad is insecure.

davidshepherd7• 11 years ago

So it still fits the definition of perfect secrecy, but (with vanishingly small probability when the key is large) it's possible for a key to be chosen that is more "guessable"?

I don't think this is a problem. Depending on the guess for the key an attacker could get back any possible message as the plaintext. So there is no reason for them to believe that the message they obtain by using a simple key (e.g. AAAAAAAAAAAA as in the example) is the original plaintext?

w0000t• 11 years ago

Yes. They don't know if the string ONETIMEPAD was produced by the key AAAAAAAAAA or GHASDIJAWE. And thus they don't know if ONETIMEPAD is actually the plaintext or not.

charriu• 11 years ago

Yes.

Guessing the correct key by chance doesn't give you the (necessary) information that the key was correct, because any number of other keys results in correct-looking messages.

panic• 11 years ago

I was skeptical at first, but it looks like TechCrunch's foray into academic publishing is finally starting to pay off. It's been amazing to follow their transition from a tech tabloid to a place you can find groundbreaking work in fields like cryptography.

jarfil• 11 years ago

Academic tabloid, FTFY

shalmanese• 11 years ago

Well, I now have a conclusive proof that I will never trust Zendo with my messages.

serge2k• 11 years ago

pretty much yeah.

DanBC• 11 years ago

This article makes me not trust Zendo.

If you're going to take a pop at Shannon (and all the other cryptographers who support that) you probably need to i) have a cleaer description of what you're doing and ii) do some math.

Turing_Machine• 11 years ago

Next up: TechCrunch solves the halting problem by using

    while(1){
        ;
    }

and

    exit(1);

as counterexamples.

Crito• 11 years ago

This is a case where the article author is either a moron, or a liar.

Either genuinely believe that he is correct (in which case he is a moron) or he doesn't genuinely believe it, but is saying it for some reason (in which case he is a liar).

Those are the only two possibilities here, and neither is flattering.

An (Important) Disproof of the One-Time Pad

Related Stories