Follow Slashdot stories on Twitter

 


Forgot your password?
Close
typodupeerror
×
Encryption Math Security

When Is It Random Enough? 153

Posted by Cliff from the chaos-from-order dept.
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?
This discussion has been archived. No new comments can be posted.

When Is It Random Enough? More

When Is It Random Enough?

Comments Filter:

  • Windy (Score:3, Funny)

    by BladeMelbourne ( 518866 ) on Saturday May 28, 2005 @06:35PM (#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.
    • 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.
  • I'm no expert, but perhaps piping some white noise into the audio-in would do it?
    • 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? (Score:3, Interesting)

        by X0563511 ( 793323 ) *
        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? (Score:3, Insightful)

          by poopdeville ( 841677 )
          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 d
          • 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.
            • You said:
              How about randomly sorted slices of randomly-chosen radio frequencies?

              Then I explained why that was a bad idea. More to the point, we wouldn't need the setup you suggested if we had a source of random electromagnetic radiation! A simple low-noise reciever and analog-to-digital converter would be sufficient. But finding random terrestrial signals is nearly impossible.

              I also don't see why you sant to avoid "patterns" in the signal. All this does is lower entropy. Say we each flip a perfect
              • [click] NOW I get it! That does make sense.

                As for a source of random EM radiation, why not aim a small/cheap radio telescope at the sun and use that? That should be random, right?
                • [click] NOW I get it! That does make sense.

                  I'm glad. :-) If you're interested in this sort of stuff, I recommend reading about Information theory before doing cryptography. The basic mathematical idea behind cryptographic functions is that they represent encodings from one alphabet to another with the property that encoding is far easier than decoding. Moreover, these encodings must be recursive (in the mathematical logic sense) and bijective. (Bijectivity might be too strong in some contexts -- cha
                  • I do know that cosmic rays are random, and I wouldn't be surprised if some government agency put a detector on some satellite and is beaming down a stream of random numbers. Frankly, I'd be surprised if this isn't being done

                    I don't recall which book it was, but one of the opening scenes in a Tom Clancy novel has Jack Ryan discussing a process to verify that the random numbers generated from the reception of cosmic radiation are actually random. They were planning to use this for encryption...

                    • Gee, and here I was thinking that without a brain, you didn't make any sense either.

                      I'm pretty sure that it would be possible to convince a judge that a sequence was random to a degree of certainty that it would be admissible as evidence. Unless I missed it, we haven't fingerprinted and validated the uniqueness of individual fingerprints of the entire human race. Fingerprints are - at least on occasion - admitted as evidence.

                      No, of course there would be no realistic way to prove the data were comple

    • Kind-of, I'm sure you meant to say it, but you still have characteristics in your microphone, a2d converter and the noise source which will lead toward patterns in the numbers, so you still have to do some mathematical trickery to analyze the ways in which your source is random and then exploit those random aspects and nothing else.

  • Lava Lamps for Random numbers (Score:3, Insightful)

    by zhiwenchong ( 155773 ) on Saturday May 28, 2005 @06:35PM (#12666391)
    Lava Lamps:
    http://www.lavarnd.org/what/index.html [lavarnd.org]

  • OK. (Score:2, Interesting)

    by CommanderNacho ( 887836 )
    How about something like motherboard sensor readings?

  • Digitize Zener noise? (Score:5, Informative)

    by Futurepower(R) ( 558542 ) on Saturday May 28, 2005 @06:41PM (#12666429) Homepage

    Zener diode noise is random. Zener diodes cost less than a dollar. What about digitizing Zener noise? Amplify it with an op amp. Digitize it by feeding it into an Analog to Digital converter.

    • Re:Digitize Zener noise? (Score:3, Informative)

      by Anonymous Coward
      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 (Score:5, Informative)

        by Sara Chan ( 138144 ) on Sunday May 29, 2005 @03:53AM (#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.

      • I *believe* some VIA motherboards/chipsets have an entropy source built into the hardware.

        The real problem like you say is speed. I have been doing research which requires megs of randomn data per second. However, I can't really get that, so 99% of the computation is wasted :)

        • Read the post [slashdot.org] immediately above yours. If you can feed your application with random data stored on a file, then you can use a cheap but slow RNG if you buffer it's output via a simple (but huge) data file. If you go this route, then you can cut the time in half by adding another cheap but slow RNG. Halve the time and double the cost recursively until you run out of money or reach a reasonable time. The side effect of this is that you also get twice the files at half the size, which could allow you to spread

  • Define "strong encryption key". (Score:5, Informative)

    by rjh ( 40933 ) <rjh@sixdemonbag.org> on Saturday May 28, 2005 @06:49PM (#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.

  • Operating Sytem (Score:2, Informative)

    by vga_init ( 589198 )
    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 som

    • Re:Operating Sytem (Score:2, Informative)

      by Anonymous Coward
      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. . . .

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

    • Re:Operating Sytem (Score:5, Informative)

      by John Hasler ( 414242 ) on Saturday May 28, 2005 @10:48PM (#12667588) Homepage
      You just described the Linux kernel's /dev/random.
      • 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 prov

        • /dev/random is pretty slow, if exhausted, would it just spew data more slowly?

          • Yes, that's what I mean. It would presumably slow down to a crawl as it slowly gathered more entropy. Of course, it might deliberately stop functioning, as an entropy daemon in such a state is almost certainly more open to manipulation.

            Speaking from experience, Java's SecureRandom slows down a few bytes a second, because it has to wait for sufficient context switches to take place within the JVM.
  • * 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

  • Intel Motherboards (Score:3, Informative)

    by JacquesPinette84 ( 547156 ) <jacques.pinette@gma i l . c om> on Saturday May 28, 2005 @07:01PM (#12666526) Homepage
    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? (Score:3, Interesting)

    by sakusha ( 441986 ) on Saturday May 28, 2005 @07:06PM (#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.
    • 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? (Score:3, Insightful)

      by rjh ( 40933 )
      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 Gei
      • 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.
        • 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.

          • 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.
            • Hello,

              Science is difficult and one may find that there doesn't exist definite answers on anything, hence it is very hard to be authoritative.

              In your case, perhaps you would benefit from reading some litterature on Random Number Machines [ciphersbyritter.com].

              Hint: the grandparent is correct. Radioactive sources are deemed truly random according to QM, but not the way we can measure decay. This is enough to generate some autocorrelation and spoil the randomness.

              An excerpt:

              Santha, M. and U. Vazirani. 1986. Generating Qua

      • Re:What's so expensive? (Score:3, Informative)

        by Sparr0 ( 451780 )
        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).
      • 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.
      • 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.
      • 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 (Score:5, Informative)

    by harlows_monkeys ( 106428 ) on Saturday May 28, 2005 @07:07PM (#12666555) Homepage
    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.

  • a nice hot cup of tea (Score:3, Funny)

    by tverbeek ( 457094 ) on Saturday May 28, 2005 @07:10PM (#12666570) Homepage
    OK, technically it's brownian motion, but isn't that random enough?
    • OK, technically it's brownian motion, but isn't that random enough?

      In H2G2 Logic: As every object in the universe exerts an influence on every other object in the universe it is in fact possible to extrapolate all of creation from a small fairy cake. Hence it would be a simple extension of the principle used in the total perspective vortex for anyone to know the exact state of your brownian motion producer at any point so long as they have easy access to the necessary baked good.

      In the real world: I

  • Someone should make a... (Score:3, Funny)

    by rekenner ( 849871 ) on Saturday May 28, 2005 @07:12PM (#12666577) Homepage
    d1,00,000,000 for this...

  • Philosophical question: what's meant by truly random? Everything can be predicted if you know the variables that go into it's creation; you could predict the roll of a die, for instance, if you could precisely measure it's velocity when hitting the table and the amount of friction that results.

    So while the OP wants to draw a distinction between "pseudo-random" and "truly random", at what point does a generator change from one to the other?

    That said, I would suppose that a "truly random" generator would

    • Re:"Truly Random" (Score:3, Insightful)

      by alienw ( 585907 )
      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" (Score:3, Informative)

      by Malor ( 3658 )
      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 even
    • 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

      Surely not. You're positing that the universe is deterministic, which seems like Einstein vainly trying to argue that "God does not play dice" with the universe.

      The

      • the universe is not, in fact, deterministic and at a quantum level things do behave probablistically.

        If that's in fact true, I'm afraid it blows my mind. I guess I have good company.

        That an isotope will not decay one moment, but will the next, for truly no reason at all...if there is no reason that precipitates the decay, then why does it at all?

        Well. I guess it'd take more math than I know to have it proved to me, but I can see why it made Einstein uneasy. It's almost like ascribing a will to quantu

        • It's almost like ascribing a will to quantum components.

          In fact, some modern philosophers (e.g. Roger Penrose, The Emperor's New Mind) have quantum randomness as a defense of free will. Although it may (as, e.g., Dennet) by more of a proof of random will.

  • Why not hardware (Score:3, Interesting)

    by delirium of disorder ( 701392 ) on Saturday May 28, 2005 @07:31PM (#12666680) Homepage Journal
    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

  • http://www.via.com.tw/en/initiatives/padlock/hardw are.jsp [via.com.tw]

    Hardware, and cheap. And, built-in.

    -bzj

  • Comment removed (Score:5, Funny)

    by account_deleted ( 4530225 ) on Saturday May 28, 2005 @08:27PM (#12666983)
    Comment removed based on user account deletion

  • LavaRnd (Score:3, Interesting)

    by kinema ( 630983 ) on Saturday May 28, 2005 @08:32PM (#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.
  • . . . It's never random enough.

  • Analog input is good, *IF* (Score:4, Informative)

    by wowbagger ( 69688 ) on Saturday May 28, 2005 @09:51PM (#12667396) Homepage Journal
    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?

    • 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 autocorrel

  • Here: (Score:2, Funny)

    by boring, tired ( 865401 )
    84213475436342364273642 There's your random number. Use that.

  • When is pseudo-random enough? (Score:3, Informative)

    by dtfinch ( 661405 ) * on Sunday May 29, 2005 @02:29AM (#12668501) Journal
    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 (Score:5, Funny)

    by Ed Almos ( 584864 ) on Sunday May 29, 2005 @05:44AM (#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
  • Comment removed based on user account deletion
  • ...the odds are you are way too paranoid.

    either that, or you're probably doing something you shouldn't be doing.

  • Use and Entropy Pool RNG (Score:3, Informative)

    by kentborg ( 12732 ) on Sunday May 29, 2005 @07:20PM (#12672630)
    Historically, there are two kinds of random number generators. Pseudo
    random number generators (PRNGs) and hardware random number
    generators.

    The PRNGs started out terrible and ended up being, essentially,
    cryptography. Supply them with a good (and unknown!) seed, and they
    produce excellent output.

    The "true" RNGs are, indeed, random, but frequently have biases (like
    the purported coin that might land 51% of the time on the starting
    face--it has a bias, but it is otherwise a valid random number
    source), these RNGs will need some post processing to clean up these
    biases.

    But you don't really want to use either of them.

    Rather, a modern RNG uses a hybrid "entropy pool" model. The pool is
    the unknown seed, and is used to feed a PRNG algorithm. If the pool
    starts out unknown, the PRNG algorithm will produce good output. On
    the other end, a hardware entropy source is used to mix the pool in on
    going basis. Go ahead and feed biased coin tosses into the pool, the
    PRGN algorithm will remove any biases.

    Where can you get such an RNG? The Linux /dev/urandom works really
    well. Feed your favorite entropy sources into /dev/urandom, pull as
    much random data as you want out of /dev/urandom. I think BSD has a
    similar feature.

    Religious note: /dev/random will block when it computes it is out of
    entropy, /dev/urandom will continue producing output. Some will say
    you must use /dev/random, others will point out that the entropy
    estimation is really hard to do, and /dev/random will block at the
    wrong time and open you up to a denial of service risk. I say use /dev/urandom, but make up your own mind.

    -kb

  • Tap the fluctuations of the stock market.

    If anyone breaks your product due to lack of randomness, get a detailed description and laugh all the way to the bank.

  • To verify a stream of random numbers is truely random, pump the random stream (/dev/random) into gzip and look at the byte distribution. If the count of each byte value (0x00 - 0xff) is even, it should be random. If it is not "even", there may be a problemo.

    For example, Linux has a good PRNG distribution based, but *BSD has (or used to have last year--hopefully it is fixed) a poor distribution. The high 2 bytes of are god, but the 2 low bytes are not good (not evenly distributed).

  • In addition to the aforementioned Intel chips there are also AMD MIPS based solutions that you may look into.
    The Au1550 Security Engine runs seperately from the processor (albeit using the same memory) and has a RNG built in. The RNG uses entropy by letting enough noise build up in a pair of ring oscillators and then querying from them.
    The throughput for the RNG is also fairly high and you can get 412.5K words per second.

    More info.
    http://www.amd.com/us-en/ConnectivitySolutions/Pr o ductInformation/0,,50_ [amd.com]

Slashdot Top Deals

He has not acquired a fortune; the fortune has acquired him. -- Bion

Close