Slashdot Mirror
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?
Zener diode noise is random. Zener diodes cost less than a dollar. What about digitizing Zener noise? Amplify it with an op amp. Digitize it by feeding it into an Analog to Digital converter.
IAAGSSTS (I Am A Grad Student Studying This Shit).
There are two different concerns going on here; the first is the strength of the key and the second is its lifetime. If you really desperately need a truly random 128-bit session key, then take out a quarter and start flipping; it takes about five minutes and you're done. But if you're in a situation where your applications will be changing keys every second, then you don't want rekeying to take five minutes.
Honestly, the best advice is to look long and hard at your reasoning for trying to roll your own generator. If you can point out precise reasons why you need truly random numbers and back your reasons up with references to the literature, then great, break out a quarter. If you can point out precise reasons why existing PRNGs are all insufficient for your task, then great, try to roll your own.
Otherwise, find a good pseudorandom number generator--and by "good", I mean "well-understood with good analysis and well-known behavior", such as the ANSI X9.17 pseudorandom number generator. Read up on its weaknesses and where it fails and how it fails. Avoid those failure modes.
Creating good PRNGs is extraordinarily hard. Trying to roll your own generator is fraught with risk; even when experienced professionals do it, they fail more often than they succeed. If you just want to learn about PRNGs and RNGs, then sure, go for it; I'm all for that. However, be very, very careful before you put your handrolled system into production code.
RFC 1750: Randomness Recommendations for Security
These are cryptographically secure PRNGs, which means they are good enough for key generation, one time pads, etc.
There are a very very very few situations where they aren't good enough, but the only people who are going to be doing things that hit those situations are people who know enough about this subject that they would not need to be asking on Slashdot about this stuff. :-)
If you must generate your own random numbers, get the book "Practical Cryptography" by Niels Ferguson and Bruce Schneier, and read the section on Fortuna.
Accounting troll: "That's our random number generator."
RNG: "nine. nine. nine. nine. nine. nine."
Dilbert: "Are you sure that's random?"
Accounting troll: "That's the problem with randomness; you can never be sure."
Quidquid latine dictum sit, altum sonatur.
/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.
You just described the Linux kernel's /dev/random.
Warning: this article may contain humor, sarcasm, parody, and perhaps even irony. Read at your own risk.
I think there's a daemon process you can run that will do that - maxwelld I think :-)
http://www.fourmilab.ch/hotbits/
--you can get 16384 bits at a time. Then I use the Muddle-Square method (of Blum, Blum, and Shub: described by Knuth, Art of Computer Programming, ch. 3) to expand those bits.
For example, manually retrieve 10 Mbits from HotBits (takes a few hours), and then expand those by a factor of 50 via Muddle-Square. That's 500 Mbits that are essentially indistinguishable from true random.
It's free, and you get to learn a bit about random numbers from reading Knuth.
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).
Female reasoning, that should be random enough but you might have problems converting the actions of a woman into a series of 32 bit numbers.
Ed Almos
Budapest, Hungary
The more corrupt the state, the more numerous the laws. - Tacitus, 56-120 A.D.