13

Okay, I guess this is entirely subjective and whatnot, but I was thinking about entropy sources for random number generators. It goes that most generators are seeded with the current time, correct? Well, I was curious as to what other sources could be used to generate perfectly valid, random (The loose definition) numbers.

Would using multiple sources (Such as time + current HDD seek time [We're being fantastical here]) together create a "more random" number than a single source? What are the logical limits of the amount of sources? How much is really enough? Is the time chosen simply because it is convenient?

Excuse me if this sort of thing is not allowed, but I'm curious as to the theory behind the sources.

2

15 Answers 15

19

The Wikipedia article on Hardware random number generator's lists a couple of interesting sources for random numbers using physical properties.

My favorites:

  • A nuclear decay radiation source detected by a Geiger counter attached to a PC.
  • Photons travelling through a semi-transparent mirror. The mutually exclusive events (reflection — transmission) are detected and associated to "0" or "1" bit values respectively.
  • Thermal noise from a resistor, amplified to provide a random voltage source.
  • Avalanche noise generated from an avalanche diode. (How cool is that?)
  • Atmospheric noise, detected by a radio receiver attached to a PC

The problems section of the Wikipedia article also describes the fragility of a lot of these sources/sensors. Sensors almost always produce decreasingly random numbers as they age/degrade. These physical sources should be constantly checked by statistical tests which can analyze the generated data, ensuring the instruments haven't broken silently.

3
  • 2
    Project idea: USB hamster wheel
    – Ates Goral
    Feb 7, 2009 at 15:47
  • 1
    technically a couple of those aren't random, they're just a few hundred orders of magnitude too complex for anything to simulate in he next, oh say 100 years...
    – RCIX
    Nov 26, 2009 at 9:02
  • avalanche noise isn't as cool as you might think. It refers to free electrons building up in non-conducting materials: en.wikipedia.org/wiki/Avalanche_breakdown
    – Andreas
    Aug 16, 2017 at 17:02
9

SGI once used photos of a lava lamp at various "glob phases" as the source for entropy, which eventually evolved into an open source random number generator called LavaRnd.

5

I use Random.ORG, they provide free random data from Atmospheric noise, that I use to periodically re-seed a Mersene-Twister RNG. Its about as random as you can get with no hardware dependencies.

4

Don't worry about a "good" seed for a random number generator. The statistical properties of the sequence do not depend on how the generator is seeded. There are other things, however. to worry about. See Pitfalls in Random Number Generation.

As for hardware random number generators, these physical sources have to be measured, and the measurement process has systematic errors. You might find "pseudo" random numbers to have higher quality than "real" random numbers.

3

Linux kernel uses device interrupt timing (mouse, keyboard, hard drives) to generate entropy. There's a nice article on Wikipedia on entropy.

3

Modern RNGs are both checked against correlations in nearby seeds and run several hundred iterations after the seeding. So, the unfortunately boring but true answer is that it really doesn't matter very much.

Generally speaking, using random physical processes have to be checked that they conform to a uniform distribution and are otherwise detrended.

In my opinion, it's often better to use a very well understood pseudo-random number generator.

2

I've used an encryption program that used the users mouse movement to generate random numbers. The only problem was that the program had to pause and ask the user to move the mouse around randomly for a few seconds to work properly which might not always be practical.

2

I found HotBits several years ago - the numbers are generated from radioactive decay, genuinely random numbers.

There are limits on how many numbers you can download a day, but it has always amused me to use these as really, really random seeds for RNG.

2

Some TPM (Trusted Platform Module) "chips" have a hardware RNG. Unfortunately, the (Broadcom) TPM in my Dell laptop lacks this feature, but many computers sold today come with a hardware RNG that uses truly unpredictable quantum mechanical processes. Intel has implemented the thermal noise variety.

Also, don't use the current time alone to seed an RNG for cryptographic purposes, or any application where unpredictability is important. Using a few low order bits from the time in conjunction with several other sources is probably okay.

A similar question may be useful to you.

1

Sorry I'm late to this discussion (what is it 3 1/2 years old now?), but I've a rekindled interest in PRN generation and alternate sources of entropy. Linux kernel developer Rusty Russell recently had a discussion on his blog on alternate sources of entropy (other than /dev/urandom).

But, I'm not all that impressed with his choices; a NIC's MAC address never changes (although it is unique from all others), and PID seems like too small a possible sample size.

I've dabbled with a Mersenne Twister (on my Linux box) which is seeded with the following algorithm. I'm asking for any comments/feedback if anyone's willing and interested:

  1. Create an array buffer of 64 bits + 256 bits * number of /proc files below.
  2. Place the time stamp counter (TSC) value in the first 64 bits of this buffer.
  3. For each of the following /proc files, calculate the SHA256 sum:

    • /proc/meminfo
    • /proc/self/maps
    • /proc/self/smaps
    • /proc/interrupts
    • /proc/diskstats
    • /proc/self/stat

      Place each 256-bit hash value into its own area of the array created in (1).

  4. Create a SHA256 hash of this entire buffer. NOTE: I could (and probably should) use a different hash function completely independent of the SHA functions - this technique has been proposed as a "safeguard" against weak hash functions.

Now I have 256 bits of HOPEFULLY random (enough) entropy data to seed my Mersenne Twister. I use the above to populate the beginning of the MT Array (624 32-bit integers), and then initialize the remainder of that array with the MT author's code. Also, I could use a different hash function (e.g. SHA384, SHA512), but I'd need a different size array buffer (obviously).

The original Mersenne Twister code called for one single 32-bit seed, but I feel that's horribly inadequate. Running "merely" 2^32-1 different MTs in search of breaking the crypto is not beyond the realm of practical possibility in this day and age.

I'd love to read anyone's feedback on this. Criticism is more than welcome. I will defend my use of the /proc files as above because they're constantly changing (especially the /proc/self/* files, and the TSC always yields a different value (nanosecond [or better] resolution, IIRC). I've run Diehard tests on this (to the tune of several hundred billion bits), and it seems to be passing with flying colors. But that's probably more testament to the soundness of the Mersenne Twister as a PRNG than to how I'm seeding it.

Of course, these aren't totally impervious to someone hacking them, but I just don't see all of these (and SHA*) being hacked and broken to in my lifetime.

1
  • I know I'm 6 years late to your reply, but I think your approach is overly complex. If you don't want to use /dev/urandom to seed your PRNG (which you ALWAYS should), then you could just read /proc/sys/kernel/random/uuid three times, hash the three results with SHA-256, and use that as your seed. Each is a type 4 UUID, which provides 122-bits entropy. Thus, two UUIDs only provide 244-bits, so that's why you would collect three, and hash with SHA-256. This is a better approach, because /proc/sys/kernel/random/uuid is generated with /dev/urandom which is cryptographically secure. Aug 9, 2018 at 16:27
0

Some use keyboard input (timeouts between keystrokes), I heard of I think in a novel that radio static reception can be used - but of course that requires other hardware and software...

0

Noise on top of the Cosmic Microwave Background spectrum. Of course you must first remove some anisotropy, foreground objects, correlated detector noise, galaxy and local group velocities, polarizations etc. Many pitfalls remain.

0

Source of seed isn't that much important. More important is the pseudo numbers generator algorithm. However I've heard some time ago about generating seed for some bank operations. They took many factors together:

  • time
  • processor temperature
  • fan speed
  • cpu voltage
  • I don't remember more :)

Even if some of these parameters doesn't change much in time, you can put them into some good hashing function.

How to generate good random number?

Maybe we can take into account inifinite number of universes? If this is true, that all the time new parallel universes are being created, we can do something like this:

int Random() {
    return Universe.object_id % MAX_INT;
}

In every moment we should be on another branch of parallel universes, so we should have different id. The only problem is how to get Universe object :)

0

How about spinning off a thread that will manipulate some variable in a tight loop for a fixed amount of time before it is killed. What you end up with will depend on the processor speed, system load, etc... Very hokey, but better than just srand(time(NULL))...

0

Don't worry about a "good" seed for a random number generator. The statistical properties of the sequence do not depend on how the generator is seeded.

I disagree with John D. Cook's advice. If you seed the Mersenne Twister with all bits set to zero except one, it will initially generate numbers which are anything but random. It takes a long time for the generator to churn this state into anything that would pass statistical tests. Simply setting the first 32 bits of the generator to a seed will have a similar effect. Also, if the entire state is set to zero the generator will produce endless zeroes.

Properly written RNG code will have a properly written seeding algorithm that accepts say a 64 bit value and seeds the generator so it will produce decent random numbers for each possible input. So if you are using a reliable library then any seed will do. But if you hack together your own implementation then you need to be careful.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.