Computers are Lousy Random Number Generators

Note that some of the CPU measurements are taken from the analog world. Intel added a rand instruction to the Pentium 4 which generated a number based on the heat of the chip at the time.

I remember reading that some casin0s use a hardware device as a seed that measures line voltage. Since line voltage is never stable it cannot be predicted. The last thing any casin0 needs is a bettor who knows the next k-e-n-o numbers that are going to hit!

g

I can think of (at least) 3 types of random number generators:

  1. simulation: you do not care if they are predictable but they must have strong statisitical properties (e.g. in n-dimensional space, n-tuples cannot lie in (sets of) hyperplanes)

  2. cryptographic and statistical: e.g. poker web site. need some statisitcal properties so hand odds are correct but also do not want players to be able to predict future outcomes and must generate a large volume of data. something like choose secret key K and init vector V (see 3)

    tmp = AES(K,V)
    out(0) = AES(K,tmp)
    out(n+1) = AES(K,out(n))
    
  3. cryptographic key generation: may be slower but must be harder to crack (see http://csrc.nist.gov/cryptval/rng/931rngext.pdf) Choose secret key K and vector V used only for key generation. For each key to generate

    DT = external input with random component
    (for NIST, system time, but could include accumulated audio noise or mouse movements)
    I = AES(K, DT)  // smears random bits around
    Result = AES(K, I^V)
    new V = AES(K, Result ^ I)
    

If I squint my eyes I can see a face in your image of 10,000 random numbers. It has a slight resemblence to Bill Gates.

I believe that some CPUs include a random number generator on them, using heat or interference to generate the numbers.

Here we go, I’ve grabbed this from Wiki:

The Intel 80802 Firmware Hub chip included a hardware RNG using two free running oscillators, one fast and one slow. A thermal noise source (non-commonmode noise from two diodes) is used to modulate the frequency of the slow oscillator, which then triggers a measurement of the fast oscillator. That output is then debiased using a von Neumann type decorrelation step (see below). The output rate of this device is somewhat less than 100,000 bps. This chip was an optional component of the 840 chipset family that supported an earlier Intel bus. It is not included in modern PCs.

All VIA C3 microprocessors have included a hardware RNG on the processor chip since 2003. Instead of using thermal noise, raw bits are generated by using four freerunning oscillators which are designed to run at different rates. The output of two are XORed to control the bias on a third oscillator, whose output clocks the output of the fourth oscillator to produce the raw bit

Ummm, yo. Every version of Linux and BSD Unix since some arbitrarily long time ago has had a wonderful little interface called /dev/random, which uses an entropy pool seeded from various sources that are both unpredictable and impractical to observe from outside the machine. For example the OpenBSD kernel uses the mouse interrupt timing, network data interrupt latency, inter-keypress timing and disk IO information. Also, if you run it on a machine with a supported hardware RNG, it’ll seed from that, too. This is pretty much a solved problem.

Here’s the result of the ent.exe test on OS X’s /dev/random circa Jan 2005

http://lists.apple.com/archives/Darwinos-users/2005/Jan/msg00033.html

It’s roughly as good as System.Cryptography.RNG, probably because it’s doing the same things. It still falls short of external environment sampling.

I always found it pretty amusing how GamesByEmail.com tried to create ‘true’ random numbrs.

http://www.gamesbyemail.com/dicegenerator

1 Like

A more reasonable first test of your library PRNG would be to plot number(N) vs number(N-1). You’re comparing number versus previous number. For most PRNG, when you do that you see stripes of diagonal numbers, which shows that once you’ve cracked the algorithm, you can predict next number.

‘Randomness’ can only be defined in terms of measurable experience, which for humans is finite. Therefore the best we can do is ‘that is pretty damn random’, or not.

The calculation of PI to a bajillion places has so far indictated that there is no repeating pattern, or perhaps no pattern. But this measurement, even taken against such a beautiful number as PI, can only be assumed based on how much time can be spent trying to measure and investigate. Does a human have enough time in his or her lifetime, even using computers?

Graphs like Jeff’s are nice ways to say “that appears to be pretty random”, and thus decide it is a suitable algorithm.

A famous case of attempts to draw random numbers is the Vietnam war draft:

There are a few criticisms of it, one is using birthdays, the other is the technique they used to mix the tokens (they added batches of tokens month by month IIRC).

Another article on the draft: http://www.amstat.org/publications/jse/v5n2/datasets.starr.html

Are humans any better? Apart from the fact that I don’t believe in truly random, we just do not have clarity or control over all the parameters/dials. That is perhaps getting a bit philosophical, but are prime numbers random? To a preschooler it might as well be, to a high school student a system appears but the brightest of minds still have not come up with a way of predicting them.

Jeff, the analog world is deterministic, the article even states as much - but there’s no way for us to measure every parameter in order to perfectly define the starting conditions, nor could we do anything with all that data in any useful timescale even if we could. So as far as we’re concerned it might as well be random, since there’s no way to feasibly predict it, even though it is theoretically predictable.

What I do, when an encryption program asks me to move my mouse, is that I lift the mousepad and shake it with the mouse on it.

That just has to be random movements :wink: but you never know, someone might be able to put up a model for it.

I don’t know about the .NET System.Random function, but in my experience the argument against standard random functions being random is that they’ll produce the same numbers time and again. So instead of telling your program to produce morer numbers, you should run the program several times. You may find that System.Rand would do something like this:

2,6,4,9,7
2,6,4,9,7
2,6,4,9,7...

While System.Security.Cryptography.RandomNumberGenerator may do something like this:

3,7,6,9,4
8,5,6,3,7
1,3,8,4,3...

Truly random numbers will not follow any distribution (except a flat one), as Tyson suggests, as this would imply that some numbers are more probable than others. If you bin the results by position then you should see a uniform distribution over the entire interval of possible numbers.

Ok well I didn’t read Tyson’s whole post; he is correct in the context of his post. :slight_smile:

It depends what you want to use these numbers for. If it is simulation or homework, then just about any PRNG will do. If it is running an online casin0, then you want hardware random number generators. Even then, the algorithm you use may cripple your organization: http://www.developer.com/java/other/print.php/10936_616221

Some time ago, I was interested in making a hardware RNG. Was going to be USB, so gamers or others could buy it, and price it down around $20-40 where it is almost too cheap not to have one. However, the company I worked for at that time claimed ownership of it, even though it had nothing to do with any line of business they were in, and the prototype had been built in the privacy of my own home with my own money and time. And the most tragic part, after all the hissy fits with lawyers, they didn’t do anything with the gizmo other than confiscate my proto.

Your post got me thinking: maybe the motherboard/processor temperature sensor could be used to add more randomness to number generators.