When Is It Random Enough?

TheCamper asks: "The generation of random numbers is very important in many areas, especially encryption. Pseudo Random numbers created by software is simply not good enough. Many key generation applications ask the user to move the mouse or bang on the keyboard to add to the randomness. You can also purchase a (very expensive) hardware random number generator to make truly random numbers. Wanting the randomness of a hardware random number generator without wanting to pay for or build my own, I was wondering if crinkling cellophane (or the like) into my computer's microphone would be considered random enough for serious encryption key generation." What entropy sources would you use for the generation of strong encryption keys?

OK.

[CommanderNacho]

How about something like motherboard sensor readings?

What's so expensive?

[sakusha]

I don't understand why people think it's so expensive to make a circuit that produces truly random numbers. Radioactive decay is the absolute gold standard of randomness. I remember seeing a project in someplace like Ciarcia's Circuit Cellar that showed how to use a small radioactive source as a randomness generator, IIRC the total cost was about $25. You can buy commercial radioactive random generators for about $150, for example the RM-60 from:
http://www.aw-el.com/ [aw-el.com]
If any hardware manufacturer wanted to incorporate this sort of feature into a chip, it would probably cost about $5 in mass quantities. But the general PC market hasn't demanded this level of true randomness.

Why not hardware

[delirium of disorder]

If you want to go through the effort to get good randomness, why not use a method that is fairly simple and proven secure under some testing? This looks like an easy apparatus to make that also could be pretty secure.
http://www.willware.net:8080/hw-rng.html/ [willware.net]
There are schematics for lots of other HRNGs on the web.

On the other hand, your choice of a random data source might not matter much at all. Although I'm sure none of this is proven in the formal sense of the word, I strongly suspect that any source of entropy that has some original indeturminability (due to true randomness in the physical world*, complexity of the data's origin, or lack of a human means to measure the source of the data's origin**) is as good a source as any other. Computers can extract entropy from a mix of ordered and disordered data. The data compression WinZIP and bzip2 do is a good example of this. Therefore, I suspect that the security of an RNG rests less or the inherent entropy of the source then on the quality of the algorithm used to amass usable random numbers from the source data.
*if that exists at all
**think Heisenberg uncertainty principle

LavaRnd

[kinema]

If you need entropy on the cheap check out LavaRnd [lavarnd.org]. LavaRnd uses a low cost off the shelf "webcam" with it's lens cap in place as a random number generator.

Re:White Noise?

[X0563511]

How about randomly sorted slices of randomly-chosen radio frequencies? I was under the impression that was the kind of thing the NSA uses.

You could then take the sliced-and-diced random radio noise and apply some kind of simple encryption to it with user entropy and use the result as the random data. That would be pretty random.

Re:Why not /dev/random

[rjh]

/dev/random only has a finite number of bits. It harvests believed-random data from events on the PC. When you exhaust /dev/random, you're out of random data until you get more system events. This is potentially a Really Bad Idea if there are other apps on your machine which also need extremely high-quality believed-random numbers.

Biased coins -- not good enough.

[cryptor3]

One (semi) interesting talk I went to recently brought up the point the scheme described isn't random if the coin is biased.

And this is a reasonable possibility, because you don't know if the coin weighs exactly the same on both sides, or maybe you're really good at flipping heads.

In order to get unbiased results, there's a simple protocol that will guarantee a non-biased random result. Suppose the probability of heads is p. Then the probability of tails is (1-p).

Flip the coin twice.
a. If it comes up heads the 1st time and tails the 2nd, call it a 1.
b. If it comes up tails the 1st time and heads the 2nd, call it a 0.
c. If it comes up heads both times or tails both times, re-run the trial until you get one of the first two.

If the coin flips are assumed to be independent, then the probability of events a and b are p*(1-p) and (1-p)*p, which are equal.

There are improvements on this scheme which output more random bits per trial (it reduces/removes the probability of the outcome c where your result is inconclusive).