Curious RNG stalemate [was: use of cpunks]

[Jon Callas]

On Oct 18, 2013, at 12:16 AM, Cathal Garvey (Phone) <cathalgarvey at cathalgarvey.me> wrote:

> Accepted, entirely, but if "noisy diodes" are all you need for quantum entropy, why are designs for OSHW entropy generators so scarce? I suggested smoke alarms not through radioactivity-fetishism but because of ubiquity and low cost, likely low difficulty to adapt.

Because people think that over-the-top is necessary.

Perhaps more to the point, people start gilding the lily, and then worrying about how pure the gold is on the lily, and then deciding that the gilt on the lily needs to be mono-atomic and to form a single crystal.

Even more to the point, they start thinking in their heads that they will be criticized for not having a single-crystal structure on the gilt on their lily, and give up. 

After that, they criticize other people who grow lilies because -- heck, anyone can do that, and years ago, they gave up on lilies because of how hard it is to get mono-crystalline gilt. Go look it up in the cypherpunks archives, for pete's sake. Nicholas Bourbaki discussed it to death there back in '92.

Building a good RNG is both simpler than you think and harder. You need:

* An unguessability source. It doesn't have to be as good as you think it does. If it's crap, you just need more. It just has to be unguessable. The deterministic process going on on my LAN might be good enough. It might not. What matters is the work factor of guessing.

Here's an example of a source I have seen that is plenty good enough, but not what most people think:

- Take an array of unsigned ints; 16 or 32 in length is fine.
- On every interrupt, read the "cpu clock." Lots of CPUs have something good enough. Tick counters, high-speed uptime, etc. It almost doesn't matter.
- XOR that into the current array element. 
- Rotate that element by an odd number of bits. Mathematically, all that's required is that you pick an odd number that's relatively prime with the word size so you get maximum mixing over time intra-element. Most people can pick a suitable odd number.
- Increment/wrap your element pointer.

Poof, you're done. Incidentally, this is *also* a quantum process, it's just quantized fatter than other quantum processes. That's why you want to do it on every interrupt. When I first saw this, my jaw dropped at its elegance.

* A pool and distiller. Hash functions are great here, as are other things. The thing to remember is only that you might get a megabyte of input that has only a single bit of unguessability in it, and you need to cope. That's why hash functions are great. Entropy estimation is highly desirable, but not necessary. This is a long discussion. It's possible to build one with no estimator that works well, and one with an estimator that works poorly.

* An output function. Ciphers and hash functions are your friends. The SP 800-90 DRBGs are all designed by committee, but work (with the obvious exception). Far more important is to have your output function stir back into the pool. Something as simple as feeding back the length of the request is fine. Even better is to feed in something like a cpu tick counter. If you do something mildly reasonable here in stir-back, then you can completely forget about entropy depletion. This is another long discussion, and that's why I'm simply asserting it. There are gentlepersons who disagree with me. 

That's it. Yeah, the devil's in the details, and my sketch is kinda like saying oh, all you have to do to land on the moon is get some rockets and life support. But this is a lot easier than landing on the moon, despite many people thinking it's harder.

And yes, yes, there are other other considerations like rebooting, suspend, hibernate, restoring VMs, and of course initial boot.

	Jon