Hacker News Reader

Comment by tptacek | Hacker News Reader

To achieve the "theoretical" unbreakability that keeps one time pads perennially in the discussion, you need a true random source of bits: a (sufficiently bias-free) measurable natural process to sample. That's what makes OTPs unbreakable: there's no structure anywhere to attack.

To achieve practical unbreakability, you just need your bits to be indistinguishable from random. You can take a relatively small number of unguessable bits and then run them through the Blake2-based LRNG algorithm to spool out a practically unlimited number of "random" bits. Theoretically you can attack Blake2 and the LRNG system; there could be some vulnerability there. In practice, this would be a deeply shitty setting to try to cryptanalyze anything, even if Blake2 was broken, which it isn't.

If you are going to go through the trouble of literally distributing physical pads to all the counterparties, though, you might as well just generate true random numbers.

View on HN

The problem with true random is that you might screw up your avalanche diode circuit (or whatever) in a way that makes it random, but not uniformly distributed. It might also pick up EM from somewhere and not "really" be random all the way. By the time you add all the whitening and that sort of thing to make those problems go away I'm not sure how the information theory proofs hold up. Probably what you would want to do is keep the physical random number generator in a fine-mesh Faraday cage in a controlled environment, and run statistical tests for a while before generating your pads. The rng-tools package on Linux has a test tool. Make sure you disconnect the test wires before generating the pads though!

I don't think you can verify the safety of a one-time pad with statistical tests.

> By the time you add all the whitening and that sort of thing to make those problems go away I'm not sure how the information theory proofs hold up.

Why wouldn't the information theory proofs hold up?

Fun puzzle: Suppose I give you coin you can flip with some bias (weight). Maybe 75% of coin flips are heads. Maybe its 65%. You don't know.

You want to generate a sequence of bits with uniform randomness (exactly 50%). Without first sampling the coin & calculating the bias, how do you generate the uniform sequence of bits?

The answer to that puzzle would probably work fine for your theoretical one time pad.

Also, in practice I suspect most of the obvious ways your random noise circuit could be broken could be detected using statistical methods. You can't use math to prove a random number generator is truly random. But you can certainly detect a lot of common failure modes of "random" number sources.

Rejection sampling works when your bias is constant, not when it varies depending on the environment.

I'd imagine just XORin CSPRNG and HWRNG would solve most of those issues. Even if HWRNG would have problems (say some interference would make it generate much less entropy), attacker can't devise CSPRNG state (even if it was vulnerable) because there is no way to "un-XOR" the output.

Also for OTP nonuniform distribution would "only" cause numbers on average to have less entropy and that could be corrected by just having them be a bit longer.

The problem with a true OTP solution is not generating the random bytes. It really isn’t. There are many many ways to do it, that are well documented. Pretty much all modern phones and many (most?) computers in the last 5 to 10 years have hardware rngs, and can generate true random values very fast compared to the old “sample some part of the computer” mechanisms while also being much more robust.

The problem is a true OTP requires both sides to have access to the same stream of random, and they must have enough for all messages. You can’t do that online, because transmitting the random key stream would require it’s own random key stream that was at least as long.

That’s why OTP are impractical.

Reply on news.ycombinator.com