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?
Windy (Score:3, Funny)
Re:Windy (Score:2)
White Noise? (Score:1)
Re:White Noise? (Score:2)
Of course, that the OP doesn't seem to want to make very many numbers.
Re:White Noise? (Score:3, Interesting)
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:White Noise? (Score:3, Insightful)
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 d
Re:White Noise? (Score:2)
You could avoid the sudden changes by using a simple cypher as I stated, I believe. Even so, it shouldn't matter if the end use was as a cypher key.
Re:White Noise? (Score:2)
How about randomly sorted slices of randomly-chosen radio frequencies?
Then I explained why that was a bad idea. More to the point, we wouldn't need the setup you suggested if we had a source of random electromagnetic radiation! A simple low-noise reciever and analog-to-digital converter would be sufficient. But finding random terrestrial signals is nearly impossible.
I also don't see why you sant to avoid "patterns" in the signal. All this does is lower entropy. Say we each flip a perfect
Re:White Noise? (Score:2)
As for a source of random EM radiation, why not aim a small/cheap radio telescope at the sun and use that? That should be random, right?
Re:White Noise? (Score:2)
I'm glad.
Re:White Noise? (Score:2)
I don't recall which book it was, but one of the opening scenes in a Tom Clancy novel has Jack Ryan discussing a process to verify that the random numbers generated from the reception of cosmic radiation are actually random. They were planning to use this for encryption...
Re:White Noise? (Score:2)
I'm pretty sure that it would be possible to convince a judge that a sequence was random to a degree of certainty that it would be admissible as evidence. Unless I missed it, we haven't fingerprinted and validated the uniqueness of individual fingerprints of the entire human race. Fingerprints are - at least on occasion - admitted as evidence.
No, of course there would be no realistic way to prove the data were comple
Re:White Noise? (Score:2)
Kind-of, I'm sure you meant to say it, but you still have characteristics in your microphone, a2d converter and the noise source which will lead toward patterns in the numbers, so you still have to do some mathematical trickery to analyze the ways in which your source is random and then exploit those random aspects and nothing else.
Lava Lamps for Random numbers (Score:3, Insightful)
http://www.lavarnd.org/what/index.html [lavarnd.org]
OK. (Score:2, Interesting)
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.
Re:Digitize Zener noise? (Score:3, Informative)
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.
Re:Digitize Zener noise? (Score:2)
The real problem like you say is speed. I have been doing research which requires megs of randomn data per second. However, I can't really get that, so 99% of the computation is wasted :)
Re:Digitize Zener noise? (Score:2)
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.
Re:Define "strong encryption key". (Score:2)
Re:Define "strong encryption key". (Score:3, Insightful)
Re:Define "strong encryption key". (Score:2)
So then it'll just land on edge, and you'll be able to read minds for the day, until it gets knocked over..
So... (Score:2)
Do you use offsets into a pad and just specify the (secret) offset?
Re:So... (Score:2)
Until it consumes too much memory and gets written to swap during extended operations (and if this is on Windows, everything gets preemptively written to swap regardless of memory usage to speed up operations).
Re:Define "strong encryption key". (Score:2)
> computer's microphone would be considered random
> enough for this application; it's easy, and I can
> make an unlimited amount of numbers this way.
Use the noise to seed a good PRNG and you'll be fine.
Or just use
Re:Define "strong encryption key". (Score:2)
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 som
Re:Operating Sytem (Score:2, Informative)
NAME
DESCRIPTION
Re:Operating Sytem (Score:2)
random is completely random and will only give out numbers until it runs out of entropy. urandom continues to hand out numbers even if the entropy of the kernels pool has reached zero.
Of course any use of these interfaces assumes trust that your OS hasn't been compromised (not a big deal the same is required when you use the computer to encrypt something) and that the implementors did things properly.
Re:Operating Sytem (Score:5, Informative)
/dev/random (Score:2)
Re:/dev/random (Score:2)
/dev/random is pretty slow, if exhausted, would it just spew data more slowly?
Slow (Score:2)
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.
Some known ways to sample random noise (Score:4, Informative)
Re:Some known ways to sample random noise (Score:2)
Re:Some known ways to sample random noise (Score:2)
Re:Some known ways to sample random noise (Score:2)
Unfortunately, with hardware random number generators it is notoriously difficult to detect when they fail. Basically, the software needs to perform statistical analysis on the random stream and "cut it off" when it exceeds certain bounds.
BTW -- The B1/B2 algorithm you describe was originally created by Alan Turing, IIRC.
RFC 1750: Randomness Recommendations for Security (Score:5, Informative)
Intel Motherboards (Score:3, Informative)
What's so expensive? (Score:3, Interesting)
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.
Re:What's so expensive? (Score:2)
Re:What's so expensive? (Score:3, Insightful)
A perfect Gei
Re:What's so expensive? (Score:2)
Re:What's so expensive? (Score:2)
Disclaimer: I'm a physicist, not a cryptographer.
Re:What's so expensive? (Score:2)
Re:What's so expensive? (Score:2)
Science is difficult and one may find that there doesn't exist definite answers on anything, hence it is very hard to be authoritative.
In your case, perhaps you would benefit from reading some litterature on Random Number Machines [ciphersbyritter.com].
Hint: the grandparent is correct. Radioactive sources are deemed truly random according to QM, but not the way we can measure decay. This is enough to generate some autocorrelation and spoil the randomness.
An excerpt:
Santha, M. and U. Vazirani. 1986. Generating Qua
Re:What's so expensive? (Score:3, Informative)
Re:What's so expensive? (Score:2)
http://www.ciphergoth.org/software/unbiasing/ [ciphergoth.org]
Correcting for the increase in decay is practically impossible; use a long-lived source.
Re:What's so expensive? (Score:2)
It is simply a matter of knowing the limits of your system, and designing around them.
Re:What's so expensive? (Score:2)
Use the output of the Geiger counter to seed a good PRNG and you will have uniformly distributed random numbers good enough for cryptography.
Re:What's so expensive? (Score:2)
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.
/dev/random and /dev/urandom fail uniformity tests (Score:2)
Re:Why not /dev/random (Score:5, Interesting)
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.
a nice hot cup of tea (Score:3, Funny)
Re:a nice hot cup of tea (Score:2)
In H2G2 Logic: As every object in the universe exerts an influence on every other object in the universe it is in fact possible to extrapolate all of creation from a small fairy cake. Hence it would be a simple extension of the principle used in the total perspective vortex for anyone to know the exact state of your brownian motion producer at any point so long as they have easy access to the necessary baked good.
In the real world: I
Someone should make a... (Score:3, Funny)
"Truly Random" (Score:2)
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
Re:"Truly Random" (Score:3, Insightful)
Re:"Truly Random" (Score:2)
I would expect a bad quality soundcard to have all sorts of filters to improve its noise and distortion characteristics (instead of higher-quality components). Wouldn't this make it less than ideal?
Quantum mechanics: remedial reading (Score:2)
Wikipedia kicks ass, by the way. There is a whole article discussing alternate interpretations of quantum mechanics [wikipedia.org], if you don't happen to agree with Mr. Bohr and his colleagues.
Re:"Truly Random" (Score:3, Informative)
Re:"Truly Random" (Score:2)
Surely not. You're positing that the universe is deterministic, which seems like Einstein vainly trying to argue that "God does not play dice" with the universe.
The
Re:"Truly Random" (Score:2)
the universe is not, in fact, deterministic and at a quantum level things do behave probablistically.
If that's in fact true, I'm afraid it blows my mind. I guess I have good company.
That an isotope will not decay one moment, but will the next, for truly no reason at all...if there is no reason that precipitates the decay, then why does it at all?
Well. I guess it'd take more math than I know to have it proved to me, but I can see why it made Einstein uneasy. It's almost like ascribing a will to quantu
Re:"Truly Random" (Score:2)
In fact, some modern philosophers (e.g. Roger Penrose, The Emperor's New Mind) have quantum randomness as a defense of free will. Although it may (as, e.g., Dennet) by more of a proof of random will.
Re:"Truly Random" (Score:2)
Well, if you can agree on definitions then the whole argument collapses on one obvious solution. Which one depends on the definitions that you agree on.
Suppose that I'm presented with a choice between vanilla and chocolate ice cream. Imagine the following 3 possibilities:
1. The universe is completely deterministic. Everything leading up to that point will cause me to pick vanilla.
2. The universe has is not deterministic. The
Why not hardware (Score:3, Interesting)
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
VIA mobos (Score:2)
Hardware, and cheap. And, built-in.
-bzj
Comment removed (Score:5, Funny)
LavaRnd (Score:3, Interesting)
When it comes to security . . (Score:2)
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:Analog input is good, *IF* (Score:2)
Here: (Score:2, Funny)
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.
True Random Numbers (Score:5, Funny)
Ed Almos
Budapest, Hungary
Re: (Score:2)
if you need things like this (Score:2)
either that, or you're probably doing something you shouldn't be doing.
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
Re:Use and Entropy Pool RNG (Score:2)
Stock Market (Score:2)
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.
How to verify random number streams (Score:2)
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).
AU1550 Security Engine (Score:2)
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 o ductInformation/0,,50_ [amd.com]
Re:An idea (Score:2)
Daniel
Re:An idea (Score:5, Funny)
Re:An idea (Score:2)
Re:old (nerd) school analog random number generato (Score:2)
Re:old (nerd) school analog random number generato (Score:2)
How to get untraceable random numbers:
Since the dice-making process and number generating process cannot be observed, and the bias
Re:old (nerd) school analog random number generato (Score:2)
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 chec
Re:old (nerd) school analog random number generato (Score:2)
Biased coins -- not good enough. (Score:5, Interesting)
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).
Re:Biased coins -- not good enough. (Score:2)
Transform the output of any psudo-random noise generator into a stream of 8 bit bytes. If a byte is between 0 and 127, call it "heads"; if it's between 128 and 255, call it "tails". Run that stream of "heads" and "tails" through your protocol and I think you've got a true random number generator. It's essentially a filter for a psudo-random number generator that removes the non-random bits, leaving the truly random bits. The cost is that at best, with a truly random input, it take
Re:Biased coins -- not good enough. (Score:2)
Re:Biased coins -- not good enough. (Score:2)
That was certainly random.
Re:Biased coins -- not good enough. (Score:2)
The output of the system I described produces a Bernoulli RV with p precisely equal to 0.5. There are no epsilons about it. It may be some amount of trials before the system produces any output at all, but when it does, the bias on the random variable is guaranteed to be fair, right from the start.
There is no need to try to "average out" the results by performing more trials. The system you describe may make the difference between your RV and an unbiased RV "insignificant" a
Re:Mouse (Score:2)
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
There you go, no charge. You wanna see the other half?