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."

Comments

Bizarre sequences of random numbers

[umrgregg]

I just used LavaRnd's Lotto Number Generator with default values and it returned:

1, 2, 3, 4, 5, 6

Talk about random...

Anyway, my idea for an open source number generator is to have people on slashdot post the first number that comes to mind in this thread. I don't know if it could get more random.... (patent pending)

Re:Bizarre sequences of random numbers

[wfberg]

Anyway, my idea for an open source number generator is to have people on slashdot post the first number that comes to mind in this thread. I don't know if it could get more random.... (patent pending)

69

Re:Bizarre sequences of random numbers

[inertia187]

You think that's bizarre, I got "503 Service Unavailable." How do I use that as a lotto number??

Re:Bizarre sequences of random numbers

[Elbelow]

I just used LavaRnd's Lotto Number Generator with default values and it returned:

1, 2, 3, 4, 5, 6

Well, in a truly random sequence, this combination is just as likely as any other... :-)

Re:Bizarre sequences of random numbers

[drewbradford]

What strikes me as odd is that the term "random numbers" is still used even among us, the excessively nerdy. Of course, pseudo-random is better, but I think that "unpredictable" would be the best term.

All numbers generated are based on something, so they'll never be truly random. The best that we can do is make them truly unpredictable, such that it cannot be determined which specific factors they are based on.

===
http://www.drewbradford.com/

Re:Bizarre sequences of random numbers

[Guano_Jim]

That sounds like the combination an idiot would have on his luggage!

Re:Bizarre sequences of random numbers

[pclminion]

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.

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.

Re: Bizarre sequences of random numbers

[Black Parrot]

> 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.

Re:Bizarre sequences of random numbers

[Ed Avis]

A number is not 'random'. There is no test you can apply to determine that 25 is random, while 44 is not. Randomness is not a property of individual numbers, it is a property of the number generator or source.

So when people say 'a random number' they really mean 'a number drawn from a random source'.

You're talking about Kolmogorov complexity, I think - the complexity of some data is the length of its shortest description. But even there you have to agree what language the description will be in. You could define a language where 18282822 is represented by the symbol 'A' and any other number is represented by itself.

I can see it now...

[Anonymous Coward]

"But, sir, I need this lava lamp for my cubicle! It's required for encrypting our company's secrets. I also need the black light, for, uh... stopping pop-ups."

Sourceforge Copy

[Anonymous Coward]

Site's already /.'ed.

You can nab the code off sourceforge though:

http://sourceforge.net/projects/lavarnd

I'm going to get modbombed to hell, but...

[Anonymous Coward]

I don't want to start a holy war here, but what is the deal with you SGI lava lamp fanatics? I've been sitting here at my freelance gig in front of a lava lamp (SGI LavaRnd lamp) for about 20 minutes now while it attempts to create me a 17 Meg file of random numbers. 20 minutes. At home, the lava lamp I got from my mom, which by all standards should be a lot slower than this SGI lamp, the same operation would take about 2 minutes. If that. In addition, during this random number generation, Netscape will not work. And everything else has ground to a halt. Even Emacs Lite is straining to keep up as I type this.

I won't bore you with the laundry list of other problems that I've encountered while working on various SGI lava lamps, but suffice it to say there have been many, not the least of which is I've never seen a SGI lava lamp that has run faster than its 1960s counterpart,despite the SGI lamp's smaller viscosity. My lamp with runs faster than this SGI lamp at times. From a productivity standpoint, I don't get how people can claim that the SGI LavaRnd is a "superior" machine.

SGI addicts, flame me if you'd like, but I'd rather hear some intelligent reasons why anyone would choose to use a SGI over other faster, cheaper, more stable systems.

Does it

[Timesprout]

A Open Source Project for Truly Random Numbers

cause random n's to be dropped from sentences ?

other semiconductors

[fortunatus]

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.

A mic listening to the environment?

[van der Rohe]

I'm not a math guy. At all.
So forgive me if this is dumb or not the right idea.
But why not just use a sensitive microphone listening to the ambience in a room to "seed" some sort of algorithm?

Re:A mic listening to the environment?

[haystor]

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.

Re:A mic listening to the environment?

[Suicyco]

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.

I have the most portable solution...

[PrimeWaveZ]

For generating random numbers: A quarter in my pocket and a lot of free time.

what about audio output?

[mbreitba]

I had a friend that 5 or 6 years ago used the "white noise" from his SB 16 to generate random numbers. Wouldn't this be much more portable than a lava lamp? -Matt

Study Chaos

[tshak]

Nothing is truly random about a lava lamp, or even the fractals on a leaf. "Randomness" as we understand it has always been about complex order and large numbers. Meaning, it's too complex for us to see the pattern and the statistical possibility of numbers occuring in a measurable pattern over time is extremely low.

Apple ][ used keypress timing seeds

[call -151]

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...

Paranoid

[Quill_28]

>so the truly paranoid can take it with them when they travel."

pfftt, like there is anyone on Slashdot that is paranoid.

Re:What about double-slit experiment?

[zeotherm]

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...

Re:Can't be done.

[CyberGarp]

Ahh contrair, you assume hidden variables young grasshopper. Even Einstein had trouble believing that quantum physics depended on randomness. The hidden variable theory has been attacked from many angles, and noone has been able to prove yet that there are hidden variables, in fact there is much evidence that quantum mechnics depends on randomness.

whatch_durrin vs. VIA

[henele]

From an article on VIA's Antaur processor...

"The Antaur also ships with Via's "Padlock" feature, a random-number generator that actually produces "true" random numbers by measuring random components of the thermal energy produced by the chip, according to its designer, Glenn Henry. RNG generators can be used to develop true randomized cryptographic keys."

Paranoid??

[ocie]

the truly paranoid can take it with them when they travel.

Oh, that just what you'd want us to do isn't it???

Different objectives

[m11533]

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.