LavaRnd: A Open Source Project for Truly Random Numbers 549
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."
Bizarre sequences of random numbers (Score:5, Funny)
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 (Score:5, Funny)
69
Re:Bizarre sequences of random numbers (Score:4, Interesting)
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 (Score:2, Informative)
Re:Bizarre sequences of random numbers (Score:3, Informative)
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
Re:Bizarre sequences of random numbers (Score:3, Informative)
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.
Re:Bizarre sequences of random numbers (Score:4, Insightful)
/joeyo
Can someone please define a random number? (Score:3, Informative)
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 unkn
Re:Bizarre sequences of random numbers (Score:5, Informative)
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:There's a statistician in the house! (Score:4, Funny)
oh, wait...
Re: Bizarre sequences of random numbers (Score:5, Informative)
> 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: Humans have trouble creating random numbers (Score:3, Interesting)
We later l
Re: Bizarre sequences of random numbers (Score:3, Insightful)
> > Yeah, but that's because we intellectually identify those numbers as "special", when they aren't really.
> Actually, those numbers are special in a particular way that makes them not random. They have a low Kormalagorov Complexity, so they're highly compressable. Good random data should be uncompressable.
Actually it's the representation of those numbers that is compressible, which is irrelevant to the randomness of a sequence of numbers.
For instance, the number 1,111,111,111 has a compressi
Re:Bizarre sequences of random numbers (Score:5, Insightful)
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.
Re:Bizarre sequences of random numbers (Score:3, Informative)
Re:Bizarre sequences of random numbers (Score:3, Interesting)
Read the definition again, it actually does make some sense. The number 7^99 is not a random number because the description I just wrote is a lot shorter than the number itself. The number 6107094127113957750471164746581366367592130941255 3 1498031084978534953383702400017179 OTOH has the same length as the previous number, but I have no shorter description of this number. In fact I did get it from a random source, but I have n
Re:Bizarre sequences of random numbers (Score:5, Funny)
*That* won't work... (Score:3, Funny)
The only numbers that generates is 42,69,503,and 23. I figure in 2 more posts you might get 17 too.
Re:Bizarre sequences of random numbers (Score:2)
If you want a real number....
72
Re:Bizarre sequences of random numbers (Score:2)
Re:Bizarre sequences of random numbers (Score:5, Funny)
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 (Score:3, Funny)
Re:Bizarre sequences of random numbers (Score:3, Informative)
It's the Answer [wikipedia.org] to the Question...
Incredible! (Score:4, Funny)
1, 2, 3, 4, 5, 6
That's the same combination I use on my luggage!
testing random numbers (Score:2)
Testis, Testis 1,2,3 Testis
Just do not donate your body to science, ok?
Re:Bizarre sequences of random numbers (Score:2)
Myself, I like 2112.
wbs.
Re:Bizarre sequences of random numbers (Score:5, Funny)
Re:Bizarre sequences of random numbers (Score:3, Insightful)
I've had a gripe about random number research since I sat in on a guest colloquium on this topic in the late 80's.
The word "random" cannot describe a result, only the process that generates that result. A truly random generator should be entirely capable of generating such patterned sequences like 1,2,3,4,5,6; although it should select them no more or less than any other sequence you care to consider interesting.
Put another way, every seemingly random sequence will mean something very special to so
Re:Bizarre sequences of random numbers (Score:2)
Arbitrary, not random (Score:3, Insightful)
Answer: none of them were random; all of them chosen by you off the top of your head. There are important mathematical differences between these two cases. What you have given is sets of "arbitrary" numbers, rather than "random" numbers.
Now, if you'd asked which of the sets could be generated randomly, then the answer is all of them, given a generator function with the correct output range.
I can see it now... (Score:5, Funny)
truly random numbers in a variety of formats (Score:3, Funny)
Think about that for a second.
Sourceforge Copy (Score:5, Informative)
You can nab the code off sourceforge though:
[sourceforge.net]
http://sourceforge.net/projects/lavarnd
Analog is the key (Score:4, Interesting)
That being said, could you not measure the exact voltage on a CPU, or the ambient temperature to several decimals, or other environmental conditions, then use that as a base?
Re:Analog is the key (Score:2)
But the more you can add to the entropy pool, combining as many factors, the better. You can at least monitor cpu temperature. I wouldn't be surprised if you can monitor power usage and other things. Maybe your audio port, or mic jack.
Re:Analog is the key (Score:2)
Re:Analog is the key (Score:2)
fallacy is that there is any such thing as a "truly random number."
You haven't been following the stock market much lately, have you?
Analog is NOT the key (Score:2)
The value of the lava lamp is that it's very unpredictable -- the changes are minor, but how they occur is not predictable, meaning it's a good source as parts of seeding a random number generator.
Regards,
--
*Art
Re:Analog is the key (Score:3, Interesting)
Not necessarily. Its best to have some kind of chaotic source [lavarnd.org]. Also, being that the world we live in is analog, not digital, aren't all sources analog in nature?
An interesting source for chaotic conditions would be weather. If one could pick a seed from an arbitrary date in history and a seed for some arbitrary extra weather condition (increase/decrease temp, humidity, pressure, etc) and feed that back into a weather
whatch_durrin vs. VIA (Score:5, Interesting)
"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."
Re:Analog is the key (Score:3, Interesting)
Well, no. Just a strict analog source would be good if you could poll it at random intervals. Unfortuantely, most regular analog sources follow a sine curve when you get to looking closely enough. Temperature will tend to fluctuate within a X of a degree around a certain temperature. No matter what resolution you look to, it will do the same thing, go a little up, and a little down. Basically following a sine curve. Poll
Re:Simplicity is always the best solution. (Score:2, Funny)
turn your head first...
Re:Simplicity is always the best solution. (Score:2)
Is that good? I have no idea. But it was fun.
I'm going to get modbombed to hell, but... (Score:5, Funny)
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.
it's all about parallelism (Score:3, Funny)
Your home PC LavaRnd setup may be able to generate a large random number faster than the SGI-based one... but the SGI LavaRnd has the architecture to generate many concurrent random numbers. It also has the ability to easily handle high definition random numbers without chugging!
=)
First, (Score:4, Insightful)
start with radioactive material...
Does it (Score:4, Funny)
cause random n's to be dropped from sentences ?
What's the probability.. (Score:3, Funny)
that if one were truly paranoid they really travel in this day and age?
A Slashdot secret revealed. (Score:3, Funny)
other semiconductors (Score:5, Interesting)
Re: other semiconductors (Score:4, Informative)
> 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 [google.com] 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.
A mic listening to the environment? (Score:5, Interesting)
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? (Score:5, Informative)
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? (Score:2, Insightful)
Therefore, just putting a mic in a room allows for the possibility that the seed can be manipulated, although figuring out what sounds to make in the room to do so in a predicatable manner is incredibley
Re:A mic listening to the environment? (Score:3, Informative)
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
Re:A mic listening to the environment? (Score:5, Informative)
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.
Re:A mic listening to the environment? (Score:3, Informative)
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.
I have the most portable solution... (Score:5, Funny)
what about audio output? (Score:5, Interesting)
Re:what about audio output? (Score:2)
You're on the right track though.
-molo
Re:what about audio output? (Score:2)
Computers generate white noise by calculating random numbers and converting them to sound patterns.
So when you sample that to turn it back into a number, you've done nothing more than waste CPU, bus, and sound-board resources to create what is probably a degraded level of randomness.
Lava lamps? (Score:2, Funny)
Re:Lava lamps? (Score:2)
Can't be done. (Score:3, Informative)
Re:Can't be done. (Score:3, Insightful)
Seriously though. Your point is valid. In our universe, (good) psuedorandom numbers are just as random as anything else in the universe (that we consider random). The real problem is that people look for a distinction between random and pseudorandom when none exists.
Re:Can't be done. (Score:5, Interesting)
Re:Can't be done. (Score:4, Informative)
Set up a piece of radioactive material next to a geiger counter, plug your geiger counter into your PC and you can generate all the random numbers you want.
I see the first post (Score:2)
Anyway, it's gonna be great for cryptographers to have a source for truly random numbers. It's a pity that it requires CCDs and such. Although I can't see the site, so I can't determine if this can be done with hardware or something similar that would be better in server environments.
cool idea for a case mod (Score:4, Interesting)
"Anyone who considers arithmetical methods of producing random numbers is, of course, in a state of sin."
--John von Neumann
Truly random numbers (Score:2, Funny)
Study Chaos (Score:5, Insightful)
Apple ][ used keypress timing seeds (Score:5, Informative)
ObHHG (Score:2, Funny)
Ford, you're turning into a penguin. Stop it.
123456? (Score:2, Funny)
The random number seems to be... (Score:3, Funny)
Expensive! (Score:2)
Re:Expensive! (Score:2, Informative)
At least an optical system is tougher to interfere with since the local user knows what the camera is looking at.
Paranoid (Score:5, Funny)
pfftt, like there is anyone on Slashdot that is paranoid.
What about double-slit experiment? (Score:4, Interesting)
The phenomena (for those unfamilar with it) is putting two closely-spaced slits in a piece of paper and then shining a light through it. You end up with a spreading fringe of light and dark patterns, as the light waves coming through the slits interfere with each other.
Where it gets spooky is when you drop the light source down to where it emits photons one at a time -- they *still* interfere with each other, even though there aren't any other photons present at any given point to interfere with.
Anyway, I seem to recall that the place where each photon ends up is random. So why not put a low-power, stream-of-single-photons light source on one side of the double-slit, and a pair of sensors on the other side? Label one sensor "0" and the other "1" and interpret the strings as binary numbers. Convert (and optionally send them through a bit blender) and you're done.
I'd think this could be manufactured in a small chip-like package, and made a standard motherboard component.
Has anyone investigated this approach? If so, I'd be curious to hear what their results were (and if it turns out not to be as random as one would like).
Re:What about double-slit experiment? (Score:5, Informative)
Oh, you mean that kind of portable (Score:2)
Spending time in specialized fields really tends to change the meaning of common words.
Portability (Score:2)
No shit, Sherlock! Can you imagine lugging six lava lamps and an SGI box round with your powerbook?
Sounds too complicated (Score:2)
This might sound crazy... (Score:2)
Would it be possible to do something like get a blank CDR, scratch it up with a brillo pad and then have software that would try and read from point A to point B even though there were no files? All the scratchs would render parts of the CD unreflective. The same as seeing a stream of 0s. The part that was not scratched would still be reflective, making it a 1. Cheap, extremely portable, and the chances of doing it the exact same way twice are almost NULL.
When you're done, just microwav
Re:This _is_ crazy... (Score:3, Informative)
Why not use a simple ZENER DIODE (Score:2, Interesting)
Random Favicon? (Score:2)
What's up with the favicon [lavarnd.org] that lavarnd is using? I don't get it...it seems totally random.
I for one.... (Score:2)
Other uses (Score:2)
Randomness based on loss (Score:3, Interesting)
You don't really need a lavalamp for this either, passing an electrical signal over a short arc-gap, perhaps filling with a changing substance would probably also product random voltage fluxation.
Of course, the real issue is making randomness with a large range (1-100% with many many decimal points) and a large enough variability (that is, any decimal number between 1-100% having an equal opportunity for occuring at any particular interval).
I'm thinking that in electrical and biochemical reactions there would also be a lot of randomness, the wide-universe and entropy and all considered?.
Paranoid?? (Score:5, Funny)
Oh, that just what you'd want us to do isn't it???
Different objectives (Score:5, Informative)
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.
Re:Different objectives (Score:3, Informative)
Cryptographic Strong Random Number Generators (Score:3, Informative)
* 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)
Silly overkill (Score:4, Interesting)
Nearly every PC also has a sound interface that could also be used as a rich source of random seed bits. You don't even need a microphone; just crank up the gain and digitize the analog noise in the microphone preamp.
My Way (Score:3, Funny)
I use porn in a dimly-lit room to produce the seed. To each his own.
You call that Pi? (Score:2, Funny)
3.14159265358979323846264338327950288419716939937 5 1058209749445923078164062862 08998628034825342117067982148086513282306647093844 6095505822317253594081284811 17450284102701938521105559644622948954930381964428 8109756659334461284756482337 86783165271201909145648566923460348610454326648213 3936072602491412737245870066 06315588174881520920962829254091715364367892590360 0113305305488204665213841469 51941511609433057270365759591953092186117381932611 7931051185480744623799627
Re:PiPi (Score:2)
3.1415926535...
Re:PiPi (Score:2)
(did you transpose the '6' and '8'? I always remeber Pi ~= 3.14159, not 3.14157)
Re:The bottom line is (Score:2, Insightful)