When Is It Random Enough? 153
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?
Digitize Zener noise? (Score:5, Informative)
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.
http://www.random.org (Score:3, Informative)
Define "strong encryption key". (Score:5, Informative)
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.
Operating Sytem (Score:2, Informative)
User interaction is random, be it keystrokes, program calls, etc. Other forms of input could also be monitered, such as mouse movements, or even network traffic. Just stick in a little daemon or kernel code that moniters I/O like that and then harvests randomness from it, storing it somewhere to be called upon later by software.
Some known ways to sample random noise (Score:4, Informative)
RFC 1750: Randomness Recommendations for Security (Score:5, Informative)
Intel Motherboards (Score:3, Informative)
use /dev/urandom (Score:5, Informative)
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.
Re:Digitize Zener noise? (Score:3, Informative)
Re:Operating Sytem (Score:2, Informative)
NAME DESCRIPTION
Re:What's so expensive? (Score:3, Informative)
Analog input is good, *IF* (Score:4, Informative)
IF the input source of the analog converter has a low autocorrelation - in other words, what has gone before has little or no bearing on what is happening now. Crinkling cellophane into a mic *by itself* is a poor choice for randomness because of the relatively long periods of quiet, and because the microphone and input circuits will "color" the signal (specifically, the signal will be low passed by the input circuits and bandpassed by the microphone's response curve, both of which increase the autocorrelation of the signal).
IF after getting the signal, you then run the signal through a process that will increase the entropy of the signal - like most compression algorithms will (although compression algorithms will still add some non-randomness to the signal in the form of the framing data for the algorithm).
Most modern motherboard chipsets include a noise diode RNG in them - this is a device which uses the thermal noise of a diode to create real, genuine random numbers. Why are you messing around with your sound card if you have one of these?
As others have pointed out, under Linux and *BSD you have a great source of good random numbers,
So why do you wish to re-invent the wheel, when you can get a nice one already made?
Re:Why not /dev/random (Score:3, Informative)
With /dev/random, you have to worry about what to do if it blocks, and you have to worry about causing others to block.
If you really need actual random numbers, as opposed to cryptographically secure random numbers, then yes, you should use /dev/random, but for almost all applications, cryptographically secure random numbers are all that you need, and so using /dev/urandom is sufficient, without the hassle of dealing with blocking.
Re:Operating Sytem (Score:5, Informative)
Re:"Truly Random" (Score:3, Informative)
A step up from that are events derived from things believed to be random, like user input. However, they are always mediated by other factors, like the circuitry and response time in the keyboard or mouse, for instance. This is probably pseudo-random data at least some of the time. The numbers are still pretty random, but in theory, skilled cryptographers might be able to tease patterns out of the bitstreams. This could potentially allow them to successfully mount mathematical attacks on encrypted data.
Another method of generating numbers is with an algorithm... given a seed number, it will produce a stream of 'random' numbers. If the seed and the algorithm are known, many of these streams can be cracked. Because they aren't really random, but have many of the features of true random numbers, they're called pseudo-random. With a strong enough algorithm, at least in theory, encryption based on pseudo-random numbers should be just about as difficult to crack as encryption based on REAL random numbers.
But even if we can't easily detect it, any number stream generated by an algorithm DOES have a pattern. We may not be smart enough to find it yet, but there's a good chance we may someday be that smart (or have that much computing power). Encryption based on truly random numbers should be crackable only by brute force; no analysis should ever reveal a pattern, since by definition there will be no pattern to find. (If we ever DID find consistent patterns in true random numbers, this would shake our understanding of the universe right down to the foundations... just about to the point of having to start over from scratch.)
Also note that a number stream generated by a Random Number Generator(RNG) can't be *too* random... if the chaos is too perfect, it becomes order, and is attackable. (weird, eh?)
I'm neither a cryptographer nor a mathematician. This is how I understand things to be, but I'm just a layperson and could easily be wrong. Pay attention to replies.
When is pseudo-random enough? (Score:3, Informative)
The only real question is what stream cipher (cryptographic PRNG) to use. They all strive to produce output that's random enough for cryptography, but they also try to do it as fast as possible. If you're concerned that they data will not be random enough, you can just trade speed for quality by combining the output of several completely different stream ciphers.
Mix PNG and RNG (Score:5, Informative)
http://www.fourmilab.ch/hotbits/ [fourmilab.ch]
--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.
Use and Entropy Pool RNG (Score:3, Informative)
random number generators (PRNGs) and hardware random number
generators.
The PRNGs started out terrible and ended up being, essentially,
cryptography. Supply them with a good (and unknown!) seed, and they
produce excellent output.
The "true" RNGs are, indeed, random, but frequently have biases (like
the purported coin that might land 51% of the time on the starting
face--it has a bias, but it is otherwise a valid random number
source), these RNGs will need some post processing to clean up these
biases.
But you don't really want to use either of them.
Rather, a modern RNG uses a hybrid "entropy pool" model. The pool is
the unknown seed, and is used to feed a PRNG algorithm. If the pool
starts out unknown, the PRNG algorithm will produce good output. On
the other end, a hardware entropy source is used to mix the pool in on
going basis. Go ahead and feed biased coin tosses into the pool, the
PRGN algorithm will remove any biases.
Where can you get such an RNG? The Linux
well. Feed your favorite entropy sources into
much random data as you want out of
similar feature.
Religious note:
entropy,
you must use
estimation is really hard to do, and
wrong time and open you up to a denial of service risk. I say use
-kb