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.
I'm no expert, but perhaps piping some white noise into the audio-in would do it?
could it be?
Lava Lamps:
http://www.lavarnd.org/what/index.html
How about something like motherboard sensor readings?
PORN
PORN
PORN
PORN
Moving your mouse around for a minute should be enuff, sure it takes a bit, but so does setting up a mic and getting styrophome.
IMagine how many time the mouse changes direction, and how many different spots u can hit in 60 seconds, I dont think ne1 could reproduce that. I remember Waste(http://waste.sourceforge.net/) asked me to move my mouse around to generate a 1024, or 2048 bit key, have fun cracking something that huge, takes long enuff to crack 128 bit.
-EL
For those really fancy peeps, wouldn't it be pretty "entropic" to have a device that follows the movements of gas molecules? My understanding is that it is very random what with all of the bounciness involved.
http://www.lavarnd.org/news/lavadiff.html
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
Try this:
Flip a coin with heads = 0, and tails = 1 as many times as needed.
First flip gives a 0 or 1 for the ones,
Second flip gives a 0 or 1 for the twos,
Third flip gives a 0 or 1 for the fours,
Fourth flip gives a 0 or 1 for the eights,
etc. etc..
Convert from binary to decimal, and voilà! Random number!
"Oh drat these computers, they're so naughty and so complex, I could pinch them." --Marvin the Martian
Random.org.
After all, I am strangely colored.
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.
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.
* 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...
Philosophical question: what's meant by truly random? Everything can be predicted if you know the variables that go into it's creation; you could predict the roll of a die, for instance, if you could precisely measure it's velocity when hitting the table and the amount of friction that results.
So while the OP wants to draw a distinction between "pseudo-random" and "truly random", at what point does a generator change from one to the other?
That said, I would suppose that a "truly random" generator would involve, for instance, isotope degeneration--not that there is no reason that an isotope decays or not, but it is beyond our (current) understanding of quantum physics to predict it. But surely it must still be the effect of some cause, even if the cause is as yet imperceptible...
--
$tar -xvf
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.
Do you, at decrypt time, specify a source file and a pad file stored on a CD you keep locked in a safe when not in use?
Do you use offsets into a pad and just specify the (secret) offset?
THIS THING CAN TURN ON A DIME, MACROSSZERO STYLE ALSO FUCK BETA, ~NYORON
http://www.via.com.tw/en/initiatives/padlock/hardw are.jsp
Hardware, and cheap. And, built-in.
-bzj
.sig
Why not /dev/random ?
/dev/urandom
It is more random than
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.
. . . It's never random enough.
Pretty Pictures!
Why exactly are pseudo randomly generated (e.g. /dev/urandom) numbers not good enough for your purpose? I can't think of a situation where these numbers, when generated from a suitably random state (for example after some random mouse movements etc.) would not be sufficient.
Much as geeks like to discuss ridiculously impractical ways of generating randomness, I really can't see a situation where this would be required. If anyone knows differently and has an example of how a code was cracked due to problems with a cryptographically strong PRNG, I'd be interested to hear it.
The BOFH covered this topic yesterday. I think the method he decided on was very secure. -> Fritz
Spooooon!!!!!
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
I always enjoyed the SGI's use of lava lights. There's an open source implementation available, that was mentioned previously.
It's a USB hardware RNG about the size of a thumb drive. 100 kb/sec. It's cool but I don't use it much. Linux friendly, and if Java ever gets around to a USB API it will work well with that.
Transcend Humanity. Please.
84213475436342364273642 There's your random number. Use that.
ffs! mod this up! its a bloody rfc and answers every question!
;)
well done Joel!
Ha! Bravo.
What I wouldn't give for a mod point today. Funniest thing I've heard in weeks.
Polyhedral dice by the handful!
Sheeesh, and you call yourselves geeks...
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.
Polyhedral dice by the handful! ...unless you want to choose a number from a set of three or less, in which case a polyhedron is overkill (and for which a normal six-sided die will work). =)
The only surefire protection against Microsoft infections is abstinence. - The Onion
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.
As rjh also pointed out, the ANSI-X9.17 pseudo-random number generator (a 3-DES based PRNG) is a high quality PRNG. So if you lack a good hardware random source, or if your hardware random source cannot deliver quality values fast enough for your purposes, then the ANSI-X9.17 might be your next best choice.
chongo (was here)
How to get untraceable random numbers:
- Build soundproof, lightproof, disconnected room in the middle of nowhere.
- Enter room with nothing but some wood, tools, paper and pen. Seal room from inside.
- Make a number of dice out of wood.
- Jumble dice, pick one and throw it.
- Congrats, your first random number!
- Repeat until finished.
- Chop all dice into pieces, incinerate.
- Exit room.
Since the dice-making process and number generating process cannot be observed, and the bias of the dice cannot be determined, what you have is random numbers.Also, the bias of individual dice is reduced by the use of several dice, so any bias in the final output could either be because all the dice happened to have the same bias, or just by accident. Either way, it's impossible to know since the dice are hand-made on the spot.
Also, building of room might not be necessary in all cases.
True confidence comes not from realising you are as good as your peers, but that your peers are as bad as you are.
Try http://www.random.org/
Ok, it's Pseudo-random, but it's not bad :
" Entropy = 7.999805 bits per character.
Optimum compression would reduce the size
of this 1048576 character file by 0 percent.
Chi square distribution for 1048576 samples is 283.61, and randomly
would exceed this value 25.00 percent of the times.
Arithmetic mean value of data bytes is 127.46 (127.5 = random).
Monte Carlo value for PI is 3.138961792 (error 0.08 percent).
Serial correlation coefficient is 0.000417 (totally uncorrelated = 0.0). "
(from http://www.random.org/essay.html )
For the situations where /dev/random can't feed enough random-data there are 2 tools for seeding the kernel PRNG: audio-entropyd (which I'm maintaining) and video-entropyd (which I developed myself).
Audio-entropyd takes a stereo audio-device and calculates random bitstreams of what it 'hears' and feeds that to the kernel. video-entropyd is the same altough it retrieves images from a video4linux-device and feeds that (after processing) to the kernel.
www.vanheusden.com - home of Multitail, HTTPing, CoffeeSaint, EntropyBroker, rsstail, bsod, listener, nagcon, nagi
OpenBSD makes use of the hardware PRNGs on various hardware cards (and are cheap) and gets entropy from a number of sources.
Trolling is a art,
http://random.org/
...the odds are you are way too paranoid.
either that, or you're probably doing something you shouldn't be doing.
"Champagne for my real friends - and real pain for my sham friends!" http://ericblade.postalboard.com/
Unfortunately, IO monitoring is generally somewhat bounded in terms of how much entropy you can gather. There are only so many interrupts per second, only so many context switches per second, etc. I don't know how quickly /dev/random can be exhausted, but I was quite surprised to discover that Java's SecureRandom class can be exhausted if you request as few as 2500 bytes from it at once. Of course, SecureRandom only uses thread-switching behaviour as a source of entropy, so /dev/random can certainly provide more -- but a limit certainly exists, probably up around a few hundred megabytes.
But say a lack of uniformity in the materials (it's wood, after all) caused one die to be chosen more often than the others in the jumbling process. Or even if the dice are chosen with equal frequency, that the bias on each individual die causes a certain number to be rolled more often for that specific die. Patterns, however slight, would emerge over time.
Nope, radioactive decay is the way to go. I say you construct a Schrodinger's Cat apparatus and write down a '1' if the cat's still living when you check on it, and a '0' otherwise. Sure, that's a lot of cats (depending on how many bits you need), but you can reuse the cats until you get a 0, and there are a lot of ex-girlfriends out there that need revenging upon.
The only surefire protection against Microsoft infections is abstinence. - The Onion
Take a picture with a digital camera, pointing it in any direction. Take the bitmap as one large binary number. Truncate at whatever size you wish.
If my grammar and spelling are off, I am [distracted/tired/careless] (take your pick)
Wood is a good material because anyone can handle it. Of course, if you have a portable laser cutter and some metal lying around, go ahead and use them and eliminate all material bias. :)
True confidence comes not from realising you are as good as your peers, but that your peers are as bad as you are.
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
Try here
Tap the fluctuations of the stock market.
If anyone breaks your product due to lack of randomness, get a detailed description and laugh all the way to the bank.
Volume two of the "Art of Computer Programming" by Knuth has tests for randomness. If the source passes the tests then it is random enough not to be overly prone to cracking by analysis. Random number theory is relatively young though. There may be attacks not yet developed.
"Sometimes it's hard to tell the dancer from the dance." --Corwin Of Amber in CoC
Thank god. Please mod parent up, so people will stop suggesting /dev/*random.
Can you comment on a few other random topics?
Have you used the Diehard tests and if so, how do you feel they compare to the 800-22 tests you used.
What do you think of the tests attempting to show anomalies in random number generation around the time of significant (to humans) events?
Do you think the type of test used on prngs in this paper could add any value to the tests you are already using?
Yes, that's what I mean. It would presumably slow down to a crawl as it slowly gathered more entropy. Of course, it might deliberately stop functioning, as an entropy daemon in such a state is almost certainly more open to manipulation.
Speaking from experience, Java's SecureRandom slows down a few bytes a second, because it has to wait for sufficient context switches to take place within the JVM.
For example, Linux has a good PRNG distribution based, but *BSD has (or used to have last year--hopefully it is fixed) a poor distribution. The high 2 bytes of are god, but the 2 low bytes are not good (not evenly distributed).
Well, the people who discovered quantum mechanics didn't agree with you. This is known as the Copenhagen interpretation.
Wikipedia kicks ass, by the way. There is a whole article discussing alternate interpretations of quantum mechanics, if you don't happen to agree with Mr. Bohr and his colleagues.
In addition to the aforementioned Intel chips there are also AMD MIPS based solutions that you may look into.
o ductInformation/0,,50_2330_6625_10509,00.html
The Au1550 Security Engine runs seperately from the processor (albeit using the same memory) and has a RNG built in. The RNG uses entropy by letting enough noise build up in a pair of ring oscillators and then querying from them.
The throughput for the RNG is also fairly high and you can get 412.5K words per second.
More info.
http://www.amd.com/us-en/ConnectivitySolutions/Pr
internet like monkeys'