Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

When Is It Random Enough?

Cliff posted more than 9 years ago | from the chaos-from-order dept.

Encryption 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?

cancel ×

153 comments

Sorry! There are no comments related to the filter you selected.

Windy (2, Funny)

BladeMelbourne (518866) | more than 9 years ago | (#12666384)

I prefer to burp or pass wind. Nobody can do that like I can; and the random number produced helps keep my data safe.

Re:Windy (1)

Cipster (623378) | more than 9 years ago | (#12671242)

I've begun to just chart my wife's moods. It's about as close to true randomness you can get. And it works! Nobody has cracked any of my data yet.

White Noise? (1)

bennyp (809286) | more than 9 years ago | (#12666388)

I'm no expert, but perhaps piping some white noise into the audio-in would do it?

Re:White Noise? (1)

poopdeville (841677) | more than 9 years ago | (#12666431)

That's a good idea, but getting good high entropy white noise is as difficult as coming up with good random number generator. Of course, this depends on the context -- this might be an effective source of entropy if one were just generating a few numbers, but it would be completely inappropriate for, say, a bank.

Of course, that the OP doesn't seem to want to make very many numbers. :-)

Re:White Noise? (2, Interesting)

X0563511 (793323) | more than 9 years ago | (#12667083)

How about randomly sorted slices of randomly-chosen radio frequencies? I was under the impression that was the kind of thing the NSA uses.

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? (2, Insightful)

poopdeville (841677) | more than 9 years ago | (#12667369)

Notice that you require a random sorting of frequencies and samples. You'd need a random number generator to come up with one of those.

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 don't believe me, record a cd of white noise and put a couple of scratches in it. It should be immediately apparent where the scratches are when you listen to it. :-)

Re:White Noise? (1)

X0563511 (793323) | more than 9 years ago | (#12667989)

No, only part of the system needs to be truly random: the radio noise. Randomly sorting and shifting frequencies avoids any patterns that may appear on a particular frequency.

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.

OK. (2, Interesting)

CommanderNacho (887836) | more than 9 years ago | (#12666393)

How about something like motherboard sensor readings?

Mouse (1)

elzurawka (671029) | more than 9 years ago | (#12666396)

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

Re:Mouse (0)

Anonymous Coward | more than 9 years ago | (#12666553)

Exactly!!!!!!! Thats why I use an Athlon64 3500+. It's 3496 better than a Pentium 4 (and I didn't have the money to go with a 4000+, which would've been 3996 better than the P4).

What you say? You can't just compare the numbers together? What do you mean they don't measure the same thing? Geez. I guess I don't know anything about this at all. I should probably spend some time reading on it.

Ok, back. From the context, it looks like you're talking about two different types of encryption: asymmetric and symmetric. The former (also called public key sometimes) uses two keys (thus the asymmetric tag); (when combined with a large number that is the two keys multiplied together in the case of the RSA algorithm) one encrypts data and the other decrypts what the other encrypts. RSA and DSA methods of public key encryption require very large numbers to be secure, usually up around 1024 bits or more (by today's standards).

Symmetric encryption uses one key to encrypt and decrypt data. To be secure, keys in excess of 128 or so bits are required for many of the algorithms in use today. The US government standard encryption algorithm called AES offers key lengths of 128, 192, and 256 bits. More keybits in this case means more security, but even 256 bits is probably overkill. Given a computer made out of all the matter in the universe, it'd still take more time to decrypt one message than the universe is thought to have left in it. The symmetric algorithm is the strongest link in the security chain when chosen properly.

Of course, even though 256 bits is overkill for today, a weakness in the algorithm tomorrow (or more likely an implementation error) could hand an attacker half of the keybits. With a 256 bit key, you've got time to fix your system, because a 128 bit keyspace is still huge. With a 128 bit key, you're totally boned. Whatever it was you were trying to protect will be known to your attackers within a decade.

An idea (1)

Cyphen (677350) | more than 9 years ago | (#12666400)

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.

Re:An idea (1)

elzurawka (671029) | more than 9 years ago | (#12666417)

Are we not looking for a cheap alternative. For some reason, i would think u might need a microscope...some something reletivly expensive to get a machine like this running. But maybe u have a cheap way to view things at a molecular level?

Re:An idea (1)

KDan (90353) | more than 9 years ago | (#12667080)

And how exactly would you propose to track the movements of gas molecules?

Daniel

Re:An idea (4, Funny)

wayne606 (211893) | more than 9 years ago | (#12668068)

I think there's a daemon process you can run that will do that - maxwelld I think :-)

Re: maxwelld (0)

Anonymous Coward | more than 9 years ago | (#12668332)

Ha! Bravo.

What I wouldn't give for a mod point today. Funniest thing I've heard in weeks.

Re:An idea (1)

commanderfoxtrot (115784) | more than 9 years ago | (#12669159)

Don't forget the alternative, browniand!

Digitize Zener noise? (4, Informative)

Futurepower(R) (558542) | more than 9 years ago | (#12666429)


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? (3, Informative)

Anonymous Coward | more than 9 years ago | (#12666665)

You can get manufactured units to do this for a couple hundred dollars(see http://random.com.hr/ [random.com.hr] for one). If you search around you can find plans to make things like this yourself(I've heard of using a smoke detector as a radiation source, or thermal noise from resistors, and so on). One thing to keep in mind in all of this is how fast you need your random bits. The ComScire unit(linked by the poster) claim 1 Mb/s. The homemade unit described at http://www.fourmilab.ch/hotbits/> is doing 240 b/s.

Mix PNG and RNG (4, Informative)

Sara Chan (138144) | more than 9 years ago | (#12668679)

A method that I've used is to download true random bits from
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.

http://www.random.org (3, Informative)

NicoNet (466227) | more than 9 years ago | (#12666442)

http://www.random.org [random.org]

Binary to decimal (0)

Spock the Baptist (455355) | more than 9 years ago | (#12666443)

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!

Biased coins -- not good enough. (4, Interesting)

cryptor3 (572787) | more than 9 years ago | (#12668786)

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

One URL (0, Redundant)

poopdeville (841677) | more than 9 years ago | (#12666446)

Random.org [random.org] .

Define "strong encryption key". (5, Informative)

rjh (40933) | more than 9 years ago | (#12666467)

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.

Re:Define "strong encryption key". (2)

Trepalium (109107) | more than 9 years ago | (#12666578)

Flipping a coin may not be a good idea, either. " A coin is more likely to land on the same face it started out on." [sciencenews.org] Tossed fairly, 51% of the time it'll land on the same face, and 49% of the time it'll land on the opposite face. Tossed unfairly, it may very predictably land on the same face it started on.

Re:Define "strong encryption key". (2, Insightful)

Chess_the_cat (653159) | more than 9 years ago | (#12669598)

So don't start it on its face. Hold it perpendicular to a surface and then flip it.

Re:Define "strong encryption key". (1)

psykocrime (61037) | more than 9 years ago | (#12671178)

So don't start it on its face. Hold it perpendicular to a surface and then flip it.

So then it'll just land on edge, and you'll be able to read minds for the day, until it gets knocked over..

Re:Define "strong encryption key". (1)

TheCamper (827137) | more than 9 years ago | (#12666581)

Thanks for the tips. Anyway, basically, I'm not going for 128 bit, etc, keys here. The text in the original question probably wasn't specific enough. What I need truly random numbers for is a one time pad encryption program I just wrote. Because it is one time pad, I need a MASSIVE amount of TRULY random numbers to use, as my key must be the same length as any file I encrypt. Pseudo random number generators aren't good enough. Also, one time pad encryption is mathematically the strongest form of encryption, but it is only as strong as the randomness of its key.

So basically, I was wondering if noise into my 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. I was planning on placing a fan next to the microphone, or singing a song, etc. Thanks in advance, and good luck with your degree.

So... (1)

Ayanami Rei (621112) | more than 9 years ago | (#12666686)

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?

Re:So... (1)

TheCamper (827137) | more than 9 years ago | (#12666755)

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?

Actually, yes. I only store the key file on CD/DVD, and it is (obviously) in system memory during encryption/decryption. The key is never written to hard disk.

Do you use offsets into a pad and just specify the (secret) offset?

The program allows you to use an offset, so you can use the unused portions of a key file. As of right now, I have no plans of keeping this offset value secret, as doing so would not add to security.

Re:So... (1)

La Camiseta (59684) | more than 9 years ago | (#12669155)

it is (obviously) in system memory during encryption/decryption. The key is never written to hard disk.

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". (1)

John Hasler (414242) | more than 9 years ago | (#12667583)

> So basically, I was wondering if noise into my
> 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 /dev/random on Linux. It does essentially the same thing.

Re:Define "strong encryption key". (1)

JRIsidore (524392) | more than 9 years ago | (#12668938)

As for the need of massive amounts of random numbers, PRNGs will always repeat the sequence after a time. But there are ways to combine two different PRNGs in a way that this period is extended and can easily be of the order of several exa-bytes (10^18). Depending on how many random bytes you want to extract this might be sufficient.

Operating Sytem (1, Informative)

vga_init (589198) | more than 9 years ago | (#12666493)

Since a lot of true randomness comes from I/O--the way users interact with the computer and whatnot--I always thought that it would be a good idea to hand the task of generating random numbers over to the operating system.

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.

Re:Operating Sytem (2, Informative)

Anonymous Coward | more than 9 years ago | (#12666719)

RANDOM(4) . . . . . . . BSD Kernel Interfaces Manual . . . . . . . RANDOM(4)

NAME
random , urandom -- random data source devices. . . .
DESCRIPTION
. . . Addditional entropy is fed to the generator regularly by the SecurityServer daemon from random jitter measurements of the kernel. SecurityServer is also responsible for periodically saving some entropy to disk and reloading it during startup to provide entropy in early system operation. . . .

Re:Operating Sytem (1)

Gilk180 (513755) | more than 9 years ago | (#12666970)

I thought everyone knew about this, but the same are available in linux as /dev/random and /dev/urandom.

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. I can't speak for the BSD implementation, but the linux implementation has been given quite a bit of thought and is well documented (of course I'm not a cryptographic expert, though).

Re:Operating Sytem (1)

elkyle (875715) | more than 9 years ago | (#12667043)


a lot of true randomness comes from I/O--the way users interact with the computer and whatnot

PGP for Windows does this when generating a new public/private keypair - if the process of text entry of the passphrase does not produce enough random data, then it brings up a screen that instucts the user to move the mouse/pound on the keyboard/whatever until enough data has been collected.

Re:Operating Sytem (4, Informative)

John Hasler (414242) | more than 9 years ago | (#12667588)

You just described the Linux kernel's /dev/random.

/dev/random (1)

Mark_MF-WN (678030) | more than 9 years ago | (#12671230)

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.

Some known ways to sample random noise (3, Informative)

Tux2000 (523259) | more than 9 years ago | (#12666494)

* 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

Re:Some known ways to sample random noise (1)

LWATCDR (28044) | more than 9 years ago | (#12667313)

This is what I was going to suggest. You may want to try using a band that is not often used. I call this the Tom Clancey Random number generator.

Re:Some known ways to sample random noise (1)

tekiegreg (674773) | more than 9 years ago | (#12668098)

Well it's crackable if I know that you're using this, I'll just set up my little pirate radio station nearby on your frequency...dooh!

Re:Some known ways to sample random noise (0)

Anonymous Coward | more than 9 years ago | (#12669752)

Read two bits, B1 and B2, from the raw noise source. If B1 == B2, read again. Return B1.
That algorithm will yield "0101010101010101[...]".

Re:Some known ways to sample random noise (0)

Anonymous Coward | more than 9 years ago | (#12670544)

He didn't say B2 was then used as B1. Each cycle uses a different set for B1 and B2.

RFC 1750: Randomness Recommendations for Security (4, Informative)

joelparker (586428) | more than 9 years ago | (#12666507)

Re:RFC 1750: Randomness Recommendations for Securi (0)

Anonymous Coward | more than 9 years ago | (#12667862)

ffs! mod this up! its a bloody rfc and answers every question!

well done Joel! ;)

Intel Motherboards (3, Informative)

JacquesPinette84 (547156) | more than 9 years ago | (#12666526)

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/ [comcast.net] for more info.

What's so expensive? (2, Interesting)

sakusha (441986) | more than 9 years ago | (#12666548)

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/ [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? (1)

Detritus (11846) | more than 9 years ago | (#12666619)

I built one of these with an RM-60, a smoke detector and an old laptop computer. It worked great, although it was a bit slow.

Re:What's so expensive? (2, Insightful)

rjh (40933) | more than 9 years ago | (#12667127)

Radioisotope decay isn't the gold standard of randomness; it's possible to find determinism in it. As it turns out this isn't because of any inherent determinism in whether an atom decays or not, but because of the determinism in the hardware used to measure it. When a Geiger counter trips, it has a certain (finite) refresh time before it will measure another decay event. That means during the refresh time, it will register 0 regardless of whether decay events occur during that time or not.

A perfect Geiger counter plus a radioisotope equals a perfect random number generator. Unfortunately, perfect Geiger counters don't exist. We can get extremely good randomness from radioisotope-based RNGs, but there are limits even to them.

Re:What's so expensive? (1)

sakusha (441986) | more than 9 years ago | (#12667239)

Please elaborate on the specific mathematics of your allegation, so I can submit an application to revoke Werner Heisenberg's 1932 Nobel Prize in Physics, and have it re-awarded to you.

Re:What's so expensive? (1)

menscher (597856) | more than 9 years ago | (#12667300)

You obviously only read the first sentence, and then fired off an idiotic reply. Try reading the remainder of his post -- the answer is in there.

Disclaimer: I'm a physicist, not a cryptographer.

Re:What's so expensive? (1)

sakusha (441986) | more than 9 years ago | (#12667551)

I read your entire reply, and it is meaningless gibberish. You're obviously no physicist, or the concept of determinism in measuring radioactive decay would not be any part of your argument. Go study Heisenberg. And then go study some mathematics and cryptography, and come back with an explanation about why you need deterministic processes to produce randomness. Hint: you don't.

Re:What's so expensive? (1)

Ichoran (106539) | more than 9 years ago | (#12667618)

You need deterministic processes to accurately transmit a random signal. If they are not (nearly) deterministic, you can add structure--i.e. nonrandomness--to your random signal. Having nondeterministic processes that produce pure white noise is also perfectly okay, but it is hard to find a nondeterministic process with that quality. Especially when importing data into a computer for deterministic processing there, you tend to suffer from frequency rolloff, quantization error, and so on.

Re:What's so expensive? (0)

Anonymous Coward | more than 9 years ago | (#12672036)

Disclaimer: I'm a physicist...
Nobody's perfect.

Re:What's so expensive? (2, Informative)

Sparr0 (451780) | more than 9 years ago | (#12667366)

This is why no one generates 1s and 0s directly from the Geiger counter. The simplest safe method is to wait for 4 clicks, calculate the time between 1 and 2, then between 3 and 4, and output a 0 or 1 depending on which is higher (corrected for the logarithmic (inverse exponential? i forget my curves) increase in decay time over time).

Re:What's so expensive? (1)

Paul Crowley (837) | more than 9 years ago | (#12668697)

And here are some strategies that will safely give more bits:
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? (1)

stoborrobots (577882) | more than 9 years ago | (#12667397)

Why wouldn't you set the "reader" module (which is polling the Geiger counter) to only read in increments of 1 refresh interval? Although this reduces the bit-rate which you can get out of the generator, it means that it now fully approximates a "perfect" Geiger counter.

It is simply a matter of knowing the limits of your system, and designing around them.

Re:What's so expensive? (1)

John Hasler (414242) | more than 9 years ago | (#12667638)

Though the random numbers produced by your Geiger counter (or just about any other noise source) are not uniformly distributed they are random in that no matter how many you collect and study you cannot predict the next one.

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? (1)

eightball (88525) | more than 9 years ago | (#12669762)

So, wouldn't be possible to configure your 'reader' to consider time in units of the 'certain (finite) refresh time'? Or some similar ways of disregarding that time, such as throwing away that amount of time after a hit. You should also probably be able to autodetect this lag delay by keeping track of the delay after the one and finding the minimum, at least to a certain degree of certainty.

use /dev/urandom (4, Informative)

harlows_monkeys (106428) | more than 9 years ago | (#12666555)

Your best bet is to use /dev/urandom on Linux or *BSD. If you have to use Windows, there's something equivalent in the crypto API, but I don't recall what it is called.

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.

Why not /dev/random (1)

quickbasicguru (886035) | more than 9 years ago | (#12666939)

Why not /dev/random ?

It is more random than /dev/urandom

Re:Why not /dev/random (4, Interesting)

rjh (40933) | more than 9 years ago | (#12667147)

/dev/random only has a finite number of bits. It harvests believed-random data from events on the PC. When you exhaust /dev/random, you're out of random data until you get more system events. This is potentially a Really Bad Idea if there are other apps on your machine which also need extremely high-quality believed-random numbers.

Re:Why not /dev/random (2, Informative)

harlows_monkeys (106428) | more than 9 years ago | (#12667459)

Why not /dev/random ?

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.

/dev/random and /dev/urandom fail uniformity tests (1)

chongo (113839) | more than 9 years ago | (#12668933)

The /dev/random and /dev/urandom generators appear to not cryptographically strong [lavarnd.org] nor do they appear to be cryptographically sound [lavarnd.org] . In our billion bit test suite [lavarnd.org] (based on the NIST Statistical Test Suite based on the Revised NIST Special Publication 800-22 [nist.gov] ): various /dev/random and /dev/urandom generators showed uniformity flaws [lavarnd.org] in every implementation that we tested. We tested a few other /dev/random and /dev/urandom implementations not listed on the test result table [lavarnd.org] and found a similar level of uniformity failures.

As rjh [slashdot.org] also pointed out, the ANSI-X9.17 pseudo-random number generator (a 3-DES based PRNG) is a high quality PRNG [lavarnd.org] . 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.

a nice hot cup of tea (2, Funny)

tverbeek (457094) | more than 9 years ago | (#12666570)

OK, technically it's brownian motion, but isn't that random enough?

Re:a nice hot cup of tea (1)

Cuthalion (65550) | more than 9 years ago | (#12667076)

Plug the long dangly bit of your atomic vector plotter into the tea, and the small plug into your consumer of entropy, and you're good to go.

Someone should make a... (3, Funny)

rekenner (849871) | more than 9 years ago | (#12666577)

d1,00,000,000 for this...

"Truly Random" (1)

Johnny Mnemonic (176043) | more than 9 years ago | (#12666588)


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

Re:"Truly Random" (2, Insightful)

alienw (585907) | more than 9 years ago | (#12666616)

Apparently, you haven't heard of quantum mechanics and Heisenberg's uncertainty principle, which states that it is impossible to know the exact position AND velocity of an electron, thus making the motion of one unpredictable. There are quite a few sources like this -- radioactive decay, various noise sources. In fact, you could probably have a decent random number generator just by sampling the noise on an unused input on a soundcard (the crappier the soundcard, the better).

Re:"Truly Random" (1)

JRIsidore (524392) | more than 9 years ago | (#12668966)

Slight nitpick: the motion of the electron is fully deterministic, as are the laws of quantum mechanics. If you know the initial state of an electron you can exactly say how it will behave in the future. The randomness comes in when we measure things, i.e. if we disturbe the electron to get its position for example. The outcome of this measurement is not predictable, only the probability of a result can be given.

Re:"Truly Random" (2, Informative)

Malor (3658) | more than 9 years ago | (#12668318)

As I understand it, true randomness only comes from measuring effects at the quantum level, like radioactive decay. (mentioned in other threads here). As nearly as we can determine, individual quantum events are absolutely random and completely unpredictable. We can make fairly precise predictions about groups of events, but we can't predetermine when, say, a given atom will decay. We can tell you about how many will decay in any given second, and this prediction will become more and more precise as events accumulate over time, but we can't tell ANYTHING about an individual event until after it happens. True random number generators depend on this.

A step up from that are events derived from things believed to be random, like user input. However, they are always mediated by other factors, like the circuitry and response time in the keyboard or mouse, for instance. This is probably pseudo-random data at least some of the time. The numbers are still pretty random, but in theory, skilled cryptographers might be able to tease patterns out of the bitstreams. This could potentially allow them to successfully mount mathematical attacks on encrypted data.

Another method of generating numbers is with an algorithm... given a seed number, it will produce a stream of 'random' numbers. If the seed and the algorithm are known, many of these streams can be cracked. Because they aren't really random, but have many of the features of true random numbers, they're called pseudo-random. With a strong enough algorithm, at least in theory, encryption based on pseudo-random numbers should be just about as difficult to crack as encryption based on REAL random numbers.

But even if we can't easily detect it, any number stream generated by an algorithm DOES have a pattern. We may not be smart enough to find it yet, but there's a good chance we may someday be that smart (or have that much computing power). Encryption based on truly random numbers should be crackable only by brute force; no analysis should ever reveal a pattern, since by definition there will be no pattern to find. (If we ever DID find consistent patterns in true random numbers, this would shake our understanding of the universe right down to the foundations... just about to the point of having to start over from scratch.)

Also note that a number stream generated by a Random Number Generator(RNG) can't be *too* random... if the chaos is too perfect, it becomes order, and is attackable. (weird, eh?)

I'm neither a cryptographer nor a mathematician. This is how I understand things to be, but I'm just a layperson and could easily be wrong. Pay attention to replies.

Why not hardware (2, Interesting)

delirium of disorder (701392) | more than 9 years ago | (#12666680)

If you want to go through the effort to get good randomness, why not use a method that is fairly simple and proven secure under some testing? This looks like an easy apparatus to make that also could be pretty secure.
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

ob. dilbert (5, Funny)

syrinx (106469) | more than 9 years ago | (#12666983)

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

LavaRnd (2, Interesting)

kinema (630983) | more than 9 years ago | (#12667013)

If you need entropy on the cheap check out LavaRnd [lavarnd.org] . LavaRnd uses a low cost off the shelf "webcam" with it's lens cap in place as a random number generator.

When it comes to security . . (1)

Leroy_Brown242 (683141) | more than 9 years ago | (#12667235)

. . . It's never random enough.

Not good enough? (1)

Psychor (603391) | more than 9 years ago | (#12667261)

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.

BOFH (1)

Fritzed (634646) | more than 9 years ago | (#12667388)

The BOFH covered this topic yesterday. I think the method he decided on was very secure. -> Fritz

Re:BOFH (1)

Fritzed (634646) | more than 9 years ago | (#12667399)

Oh yeah, I forgot the link. [theregister.co.uk]

-> Fritz

Analog input is good, *IF* (3, Informative)

wowbagger (69688) | more than 9 years ago | (#12667396)

Analog input is a good source of randomness, *IF*.

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

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* (1)

forkazoo (138186) | more than 9 years ago | (#12670615)

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


It is traditional to just take the lowest order bit(s) from an analog source. The DAC on your sound card almost certainly doesn't have 16 real bits of precision. So, make some measurements to verify it doesn't have some systematic error (more likely to be a one or a zero), and sample at relatively "long" intervals, like every quarter second, so that there is no particular corellation between the samples. Do a little testing to verify that something tragic isn't happening, and you should be all set. No real need to crinkle the cellophane, since you are using the noise of the DAC, not the sound itself, but whatever floats your boat...

my favorite random number generator (0)

coaxial (28297) | more than 9 years ago | (#12667657)

I always enjoyed the SGI's use of lava lights. There's an open source implementation [lavarnd.org] available, that was mentioned previously [slashdot.org] .

Anybody want my Araneus Alea I (1)

Eunuch (844280) | more than 9 years ago | (#12667658)

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.

Here: (2, Funny)

boring, tired (865401) | more than 9 years ago | (#12667664)

84213475436342364273642 There's your random number. Use that.

old (nerd) school analog random number generators (1)

imperious_rex (845595) | more than 9 years ago | (#12668496)

Polyhedral dice [paizo.com] by the handful!

Sheeesh, and you call yourselves geeks...

Re:old (nerd) school analog random number generato (1)

proverbialcow (177020) | more than 9 years ago | (#12668563)

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

Re:old (nerd) school analog random number generato (1)

fbjon (692006) | more than 9 years ago | (#12669091)

I was thinking about this the other day..

How to get untraceable random numbers:

  1. Build soundproof, lightproof, disconnected room in the middle of nowhere.
  2. Enter room with nothing but some wood, tools, paper and pen. Seal room from inside.
  3. Make a number of dice out of wood.
  4. Jumble dice, pick one and throw it.
  5. Congrats, your first random number!
  6. Repeat until finished.
  7. Chop all dice into pieces, incinerate.
  8. 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.

Re:old (nerd) school analog random number generato (1)

proverbialcow (177020) | more than 9 years ago | (#12672213)

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.

When is pseudo-random enough? (2, Informative)

dtfinch (661405) | more than 9 years ago | (#12668501)

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.

True Random Numbers (4, Funny)

Ed Almos (584864) | more than 9 years ago | (#12668890)

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

Online Random number generator (0)

Anonymous Coward | more than 9 years ago | (#12669118)

Try http://www.random.org/ [random.org]

Random.org (0)

Anonymous Coward | more than 9 years ago | (#12669147)

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 [random.org] )

audio-entropyd and video-entropyd (1)

flok (24996) | more than 9 years ago | (#12669411)

For the situations where /dev/random can't feed enough random-data there are 2 tools for seeding the kernel PRNG: audio-entropyd [vanheusden.com] (which I'm maintaining) and video-entropyd [vanheusden.com] (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.

OpenBSD (1)

grub (11606) | more than 9 years ago | (#12669624)

OpenBSD makes use of the hardware PRNGs on various hardware cards (and are cheap) and gets entropy from a number of sources.

random.org (0)

Anonymous Coward | more than 9 years ago | (#12669746)

http://random.org/ [random.org]

if you need things like this (1)

XO (250276) | more than 9 years ago | (#12669812)

...the odds are you are way too paranoid.

either that, or you're probably doing something you shouldn't be doing.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>