User Tools

Site Tools


random_numbers

# $EPIC: random_numbers.txt,v 1.2 2007/02/17 18:33:25 jnelson Exp $

About pseudo-random numbers:

Psuedo-random number generators (RNG) always have tension between three opposing forces:

1) Entropy
2) Coverage
3) Repeatability

Entropy:

Entropy is the tendancy of a RNG to avoid revealing what the next random number is going to be. Entropy can be roughly measured by asking this question: If I see <N> numbers from the random number generator, can I guess what the possible values of the <N+1>th value is? As N grows increasingly larger, does the possible values of N+1 grow increasingly smaller?

High entropy can be imaged as deck of cards where you select a card, and then re-shuffle the deck before you select the next card.

Coverage:

Coverage is the tendancy of an RNG to select each value approximately the same number of times. Coverage can be roughly measured by determining whether the selections-per-number is flat (more coverage) or bell shaped (less coverage),

High coverage can be imagined as a deck of cards where you select a card, and then remove that card from the deck, until all the cards have been used, and then you re-shuffle.

Repeatability:

Repeatability is the tendancy of an RNG to be able to generate the same values each time it is used. Repeatability is determined by observation.

Repeatability can be imagined as a deck of cards where the order is predetermined, and you select each card in order.

Why are these forces in opposition?

Any psuedo-random number generator that uses an algorithm has to have a starting value (“seed”). Most RNGs are fully repeatable, given the same initial seed. The quality of the entropy is therefore only as good as the secrecy of the seed.

Any psuedo-random number generator that uses a mathematical formula to decide what the next value is, bases the next number in part on the previous number. The best RNGs create values that are very very large (arc4random creates values [0..2^170]) and then give you only a few bits of that number. This hides from the viewer what the number is, and hinders the calculation of the next number.

Any psuedo-random number generator that uses an external data source does not have to be seeded, but the quality of the entropy depends on the external source.

Enough blathering! What about EPIC?

The client has four random number generators:

SET RANDOM_SOURCE Type Entropy Coverage Repeatability Seeded
0 /dev/urandom High Medium Low No
1 Classic ircII RNG None High High Yes
2 gettimeofday() Medium Low Low No
3 Arc4random High Medium Low No

Urandom:

The /dev/urandom RNG reads 32 bits from /dev/urandom and returns them to you. This requires that the client hold open /dev/urandom, which will reduce the number of file descriptors available. If /dev/urandom is not available, this RNG falls back to the classic ircII RNG. You cannot seed this RNG.

Classic ircII:

This is the RNG used by all versions of ircII. It is always available, and it is fully portable across all ircII clients. Based on a 32 bit seed, it generates a 32 bit number and returns it. Given one number, it is possible to generate all the random numbers that succeed it. This RNG must be seeded, and is fully repeatable with the same seed.

gettimeofday():

This is the RNG historically used by EPIC. It is usually available on all epic and bx clients. It works by calling gettimeofday() twice in succession and using the low 16 bits of each call to generate a 32 bit number. Given faster computers and faster syscalls these days than 10 years ago, this RNG doesn't give very good coverage, but it's hard to predict the exact time. You cannot seed this RNG.

Arc4random:

This is the RNG currently recommended for all-purpose use. This RNG generates numbers between 0 and 2^170 and returns the lowest 32 bits. Not knowing what the high 138 bits are makes it unreasonably difficult to calculate the next value, since it's understood that all 2^32 values are possible within the 2^138 different paths. The Arc4random RNG is auto-seeding from /dev/urandom so it is not repeatable.

History:

The classic ircII RNG first appeared in ircII. The gettimeofday() RNG first appeared in EPIC3. The /dev/urandom RNG first appeared in EPIC4pre2.001. The arc4random RNG first appeared in EPIC4-1.1.8.

random_numbers.txt · Last modified: 2007/02/17 18:33 (external edit)