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?
I prefer to burp or pass wind. Nobody can do that like I can; and the random number produced helps keep my data safe.
Lava Lamps:
http://www.lavarnd.org/what/index.html
How about something like motherboard sensor readings?
PORN
PORN
PORN
PORN
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
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.
* A AM or FM tuner tuned to an unused frequency produces noise. The problem is to find a really unused frequency. Under good weather conditions, even a sender far away may be received, thus the signal is no longer truely random. * All semiconductors produce thermal noise. The base-emitter diode of a germanium PNP transistor, operated in reverse-biasing, is said to produce very much thermal noise. Feed the signal trough an op-amp (uA 741 or similar) so that you get the noise up to line level. Both ways end in an ADC, for example in the line-in of a soundcard. * An old TV (without noise cancelling) tuned to an unused frequency is able to produce the same noise as a tuner, but it additionally offers another way to sample noise: It displays random white and black dots that change 50 or 60 times per second. Add some photo diodes and a lot of duct tape and you get a low-speed digital random noise generator. There is a simple algorithm to improve the quality of the generated noise so that it is more random: Read two bits, B1 and B2, from the raw noise source. If B1 == B2, read again. Return B1. (I don't remember where I read about this algorithm, sorry.) Tux2000
Denken hilft.
RFC 1750: Randomness Recommendations for Security
Some Intel motherboards have a hardware rnd device built-in. There's even a driver in the linux kernel to access the device, and userspace tools (rng-tools) to feed the random bits into /dev/urandom at a specified interval. Check out http://home.comcast.net/~andrex/hardware-RNG/ for more info.
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/
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.
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.
OK, technically it's brownian motion, but isn't that random enough?
http://alternatives.rzero.com/
d1,00,000,000 for this...
Apparently, you haven't heard of quantum mechanics and Heisenberg's uncertainty principle, which states that it is impossible to know the exact position AND velocity of an electron, thus making the motion of one unpredictable. There are quite a few sources like this -- radioactive decay, various noise sources. In fact, you could probably have a decent random number generator just by sampling the noise on an unused input on a soundcard (the crappier the soundcard, the better).
http://www.willware.net:8080/hw-rng.html/
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
------ Take away the right to say fuck and you take away the right to say fuck the government.
NAME DESCRIPTION
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.
If you need entropy on the cheap check out LavaRnd. LavaRnd uses a low cost off the shelf "webcam" with it's lens cap in place as a random number generator.
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.
For large sets, this will be our guide even unto death, for the LORD will work for each type of data it is applied to...
/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.
Notice that you require a random sorting of frequencies and samples. You'd need a random number generator to come up with one of those.
:-)
Even if you had one of those, this wouldn't increase the entropy of your data set. The problem is that in slicing and dicing your recording, you'd be creating discontinuities in the function that describes the original wave form. Fourier analysis tells us that this would shift the spectrum upwards, reducing entropy since there's limited bandwidth in our channel.
If don't believe me, record a cd of white noise and put a couple of scratches in it. It should be immediately apparent where the scratches are when you listen to it.
After all, I am strangely colored.
Analog input is a good source of randomness, *IF*.
/dev/random - and /dev/urandom if you need random-ish number in greater quantities than /dev/random spits them out. /dev/random pulls its entropy from network events, keystrokes, disk access, hardware RNGs (like the afore-mentioned noise diode sources), and many other sources, and applies very strong entropy increasing algorithms to them.
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?
www.eFax.com are spammers
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.
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.
84213475436342364273642 There's your random number. Use that.
I think there's a daemon process you can run that will do that - maxwelld I think :-)
As I understand it, true randomness only comes from measuring effects at the quantum level, like radioactive decay. (mentioned in other threads here). As nearly as we can determine, individual quantum events are absolutely random and completely unpredictable. We can make fairly precise predictions about groups of events, but we can't predetermine when, say, a given atom will decay. We can tell you about how many will decay in any given second, and this prediction will become more and more precise as events accumulate over time, but we can't tell ANYTHING about an individual event until after it happens. True random number generators depend on this.
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.
All you need is a large enough seed to produce a pseudo-random stream that will never be broken. A 128 bit key is strong enough to bet your life on and still sleep easy, Take what we can break now, and do it 2^56 times. You might as well use a 256 bit key though, since computers are fast, and you seem a little paranoid.
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.
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.
Historically, there are two kinds of random number generators. Pseudo
/dev/urandom works really /dev/urandom, pull as /dev/urandom. I think BSD has a
/dev/random will block when it computes it is out of /dev/urandom will continue producing output. Some will say /dev/random, others will point out that the entropy /dev/random will block at the /dev/urandom, but make up your own mind.
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