Slashdot Mirror
LavaRnd: A Open Source Project for Truly Random Numbers
Phil Windley writes "Truly random numbers are crucial to good encryption.
Most people have heard of Silicon Graphic's use of Lava Lamps to generate random numbers. There were some problems: it required special SGI hardware and software along with six lava lamps, and the solution wasn't portable. But the biggest drawback was that SGI patented the idea so it wasn't freely available. Now, some of the scientists behind the SGI random number system have create LavaRnd, an open source project for creating truly random numbers using inexpensive cameras, open source code, and inexpensive hardware. The system uses a saturated CCD in a light-tight can as a chaotic source to produce the seed. Software processes the result into truly random numbers in a variety of formats. The result is a random number that is crytographically sound, ranking at the top of its class in the NIST 800-22 Billion bit test. Its even portable, so the truly paranoid can take it with them when they travel."
Site's already /.'ed.
You can nab the code off sourceforge though:
http://sourceforge.net/projects/lavarnd
Unless the random-number generator is built outside of our Universe, it can't generate truly random numbers. Only pseudo-random ones. As it stands, there will always be something influencing the result. Fortunately for us, pseudo-random numbers are impossible to differentiate from random ones and are random enough to serve our purposes anyway.
Support the First Amendment. Read at -1
The Apple ][ computers used the pause between keystrokes, measured much more precisely than necessary and disregarding all but the last 8 bits, as an attempt at an analog random number seed for their psuedorandom number generator. Very simple and effective and I haven't seen many implementations of better systems around. One side effect was that if you had a program which ran off the boot disk with no keystrokes, it would do the same thing every time, no matter how improbable that was...
It's psychosomatic. You need a lobotomy. I'll get a saw.
You are correct that white noise can produce appropriately random numbers.
The problem is that for encryption purposes you may need some huge random numbers. If you want to do that from an analog solution you'll have to take your samples closer and closer together, until the numbers become less random. If you start sampling sound 1 million times a second, any two values next to each other my be really close and actually predictable.
t
Yeah, but pseudo-random numbers are, by definition, predictable.
Good idea, but insecure. What happens when I put a tuning fork next to it? That provides order, and order = no entropy = no randomness. Its too easy to tamper with, and a motivated attacker could limit or even predict the output.
:)
You're on the right track though. Its an analog source, just like the lava lamps.. but how the heck are you going to tamper with a lava lamp?
-molo
Using your sig line to advertise for friends is lame.
I'm not a radio expert... but theoretically, couldn't a system like that be attacked by beaming out a strong known signal with limited range on the frequencies (or possibly spill across a broad spectrum) utilized by the random system? Then the attacker could guess the random series since it forced the generator to use a known seed.
At least an optical system is tougher to interfere with since the local user knows what the camera is looking at.
======
In X-Windows the client serves YOU!
Because sound is not random at all. White noise is, but how often do you hear that? Not often. Voices, cars driving by, phones ringing, all of these are patterns. Patterns lead to cracks in the numbers that can be culled for weaknesses in the algorithm. This in turn leads to knowledge of what algorithm is being used, which in turn leads to a directed cryptanalysis of the data, exactly what true random numbers are meant to avoid.
Even using mouse clicks, keystroke times, etc. is not random. Thats why its called "pseudo-random". Processing normal everyday sound through a PRNG (pseudo random number generator) is still only pseudo, not real.
People have been working on this problem for decades. Trust me, what you are asking about has not only been tried, but been used and even attacked.
Where to begin... For starters, the double slit experiment, to see the neat effects of single electron interference, must be done in a vacuum. The electorns must not be influenced by anything else at all, like air/gas molecules. Also, it must be done at temperatures near absolute zero, where the thermal bath of the environment doesn't wash out the quantum effect you are talking about... Just not possible on a portable system...
Amazing how many /.'ers dunno what 42 is. :)
It's the Answer to the Question...
The original motivation for random number generators was simulation. One of the early mainframes, and I am afraid I forget which one, included a true random number generator. It was an unexpected disaster, totally unusable for simulation and other then-state-of-the-art users of random numbers. They were "too random".
It turns out that for an experiment to be useful it need to be repeatable. Thus, it was critical that users be able to repeat the sequence of "random" numbers. Thus the reason why all random number mechanisms permit you to set the seed... otherwise they could just use a sufficiently random seed and life would be good.
Another aspect of random number is that they must not only be "random", but they need to have a well defined distribution over the range of possible values. You might assume it is desirable to have a linear distribution, which IS useful in some settings, but other distributions ("bell curve", and exponential come to mind) are also extremely useful.
IF one has a real need for truly random numbers, the source for those number does need to perform to a certain distribution over the range of possible values. And it can not be used to the exclusion of the existing techniques which have been extremely useful in their intended problem domains. This is really just another case of a good solution in one problem domain being used in another without its underlying foundation being examined for applicability to that new problem domain.
The system you propose is a form of one time pad. While it works in theory, it is not the application needed here. Random numbers are needed in streams where there can be no pattern known or logical pattern findable. How many ways can you think to scratch a CD? Up and down, right and left, circles? With this sort of information you could start to predict the general "form" of the number. Besides, when you need a stream of numbers it needs to change over time. The CD is scratch once use once.
You don't understand what is meant by "uniformly distributed." Say you have a uniform random variable taking on the values 1..10. A "uniform random variable" means that each possible outcome has an equal probability of occurring. It doesn't mean that there must necessarily be equal numbers of 1,2,3,4, etc. in the output.
Imagine the previous random source generating two sequences. The first is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. The second sequence is [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]. How much less likely is it to generate the second sequence than the first one? The answer is, it is no less likely. Both sequences are equally likely. This is the meaning of a "uniform source." It certainly doesn't mean that sequences such as [1, 1, 1, ...] cannot occur!
9 out of 10 people would probably say all 0's or all 1's isn't a random result, even when it comes from a random source.
They probably would say that, but they'd be wrong. People have major misconceptions about randomness. If a random source generates the sequence [1, 6, 3, 3, 8, 2] people will say "Ho hum." If the same source outputs [1, 2, 3, 4, 5, 6] people all of a sudden get interested and say "I wonder what's going on." There's nothing going on. The random source doesn't care whether your brain wants to ascribe some special meaning to the sequence [1, 2, 3, 4, 5, 6]; it generated it mindlessly, and your human tendency to pick out patterns has kicked in. You are imposing your own order on it, when no real order exists.
When designing and building a physical cryptographic strong random number generator (CSRNG, not CSPRNG) you are looking for many things including:
* a uniform or near uniform distribution of the output.
* it must be unpredictable
* it should be very hard / impossible for attacker to influence the output of the CSRNG.
The first two are reasonably easy with physical RNG, but the last one is the kicker when it comes to actually implementing the CSRNG.
The attacker shouldn't be able to influence it by poking a pin-hole in the case (of a light sealed chamber around the CCD), or putting a heat source next a lava lamp (so the goo stays at the top)
As to working on the problem for decades, excellent commercial analog white-noise generators have been available for half a century or more. The only problem is making a very cheap white noise source that can be digitized conveniently.
Look at atomic decay. You can predict fairly well how fast a large sample of a radioisotope will decay, but it is flat-out impossible to predict when any given atom will decay. That's about as random as you can get.
Dewey, what part of this looks like authorities should be involved?
> What always bothers me is when people want uniformly distributed random numbers. I know why its valuable but if you make sure that your numbers are uniformly distributed they aren't really random anymore.
Sure they are. There's a difference between "randomness" and "distribution". You could have random numbers with a uniform distribution, a gaussian distribution, an exponential distribution, some bimodal distribution, etc., and they would still be random.
But it's really convenient to have a RNG with a uniform distribution, since you can easily transform numbers drawn from that distribution to some other arbitrary distribution by taking f(x) with the desired f() and an x drawn from the uniform distribution.
BTW, "uniform distribution" doesn't mean that you get the same number of occurences of each number in the range; it only means they have the same probability of occuring. (OK, that distinction gets a bit tricky when you're talking about pseudo-random numbers, but let's pretend we're talking about genuinely random numbers.)
> Its just as likely to get all 0's or all 1's as it is to get any other single random number and yet 9 out of 10 people would probably say all 0's or all 1's isn't a random result, even when it comes from a random source.
Yeah, but that's because we intellectually identify those numbers as "special", when they aren't really. For instance, people would probably think the numeric representation of their birthdate was special, though someone else might think it a perfectly random number. Strictly speaking, randomness has nothing to do with the importance humans assign to the result.
> I guess the big misunderstanding is that once you have a number, its not random, you know what it is.
Yes, the a posteriori probability of an event, given that the even happened, is always one. Pseudoscientists are fond of constructing probability arguments that they think should be convincing, not realizing that they are just painting a bull's-eye around wherever the arrow happened to strike.
> A random pattern is probably better defined as one you can't predict, and once you have it, recreating it with the same process is not likely.
For most uses we would want to say that "you can't predict" means that all possible patterns are equally likely, i.e. that betting on one has the same expected pay-off as betting on any other, at least if we're talking about a uniform distribution. And as for re-creation, we usually want sequentially generated patterns to be independent, i.e. that knowing what has been produced in the past does not help you predict what's coming up next. In particular, if your generator produced pattern z last time, the probability of producing z next time is still the same as the probability of producing any other pattern.
Any time there is a preferred way to bet, whether considering the past or not, it means that your generator is biased in ways that you probably don't want for a basic RNG. If you want biases, introduce them by filtering the number produced by a RNG with a uniform distribution.
Sheesh, evil *and* a jerk. -- Jade
> audio circuits often use diode junctions in reverse-breakdown mode as a source of "white noise". couldn't we computer folks do the same? seems a similar idea to the the dark CCD technique.
I think there are already a lot of solid-state solutions out there that use thermal noise to generate random bits. The lava-lamp solution and its derivatives sound like a lot of fun geeky fooling-around, but ultimately seem to be a solution in search of a niche.
Sheesh, evil *and* a jerk. -- Jade
creating truly random numbers using inexpensive cameras
Fussy nitpick:
As a matter of principle we shouldn't talk about "true" random numbers. Even if you have a source of quantum randomness (the best you can do), in any practical scheme there will always be differences in how 0's and 1's are detected. The impact of these differences can be minimized through careful design, but they will always be there and will cause a departure from an exact 50/50 split of 0's and 1's.
For example, an attenuated laser passing through a simple 50/50 beamsplitter and into 2 single-photon detectors is far better than a lava lamp. But no beamsplitter is exactly 50/50, and this will cause an excess of 0's or 1's. (You could adjust the detection efficiency or optical alignment of the detectors to compensate, but the point is that this is a manual adjustment that will never result in exactly zero bias.) And no amount of algorithmic hashing or obfuscation can eliminate this bias (although it may reduce it significantly).
It will always be the case that any practical system for generating bit sequences of length N will never generate them with a frequency of exactly 2^(-N) each (in the limit of an infinite number of trials), and with zero correlation between successive bit sequences. "Truly" random numbers are an unattainable goal.
Random numbers are those you cannot predict. I'm no physicist, but I think quantum theory says that many natural events occur randomly - that is, there's no way of knowing which slit a photon will 'choose' to go through, and it isn't particularly 'based on' anything except a 50/50 probability.
So then if all current sources of numbers are not random, what _would_ meet your definition of the word 'random'?
-- Ed Avis ed@membled.com
If you set out with the assumption that such patterned results must never occur, then you have biased your generator against certain results, and your generator is therefore, BY DEFINITION, not random.
Such a generator would still be random, but it would not produce a uniform distribution anymore. Uniform distribution is an important property of a random number generator in most applications, but not required in others, like PIN generation or choosing the combination to one's luggage.
Lava lamp? Nah.. Real geeks use this
These constants aren't of much concern since they are independent of the objects being studied (that's what makes them constants!). No one actually tries to figure out what exactly the Kolmogorov complexity of an object is, since it would be a total bitch to try to prove that a given program is the shortest one there is and as a result of the halting problem, no program can compute the Kolmogorov complexity of an arbitrary object. Instead, one generally tries to find an upper bound on the Kolmogorov complexity of an object which is valid for any computer.
My only political goal is to see to it that no political party achieves its goals.
When working with K. complexity in general the universal computer doesn't matter much, but if you try to pick a particular number or message out of the air and work out the complexity of that it does matter. You could define a Turing machine with one extra instruction that prints out the complete works of Shakespeare, and then the complexity of that particular string would be very low. But such a special machine would not help you at all if trying to reduce the complexity of strings in general. The point is that you have to be very careful when picking a single number and trying to talk about complexity or randomness after the fact. Normally you'd worry about these things for numbers to be drawn from a particular distribution, not just one number you picked out of a hat (with also the liberty of picking a particular computational model out of a hat).
-- Ed Avis ed@membled.com
It seems to be that by our common definition of random, random numbers are in fact impossible. So I am wondering what the definition we are working with regarding random number is?
IMO, I think one stipulation of a true "random number" is that part of the seed has to be externally derived. I.e. in any closed system numbers cannot be truly random. This means doing things using as a seed, the previous random number hashed with the MD5SUM of the system time along with some external information which is unknowable by an attacker or other program. Mouse or keyboard activity, network traffic in some cases, maybe even an MD5SUM of the total range of I/O address ports...... Of course, that would have to be kernel level.
LedgerSMB: Open source Accounting/ERP