Usage of RNG in applications and libraries

GNU libc

Project website: http://www.gnu.org/software/libc/

Functions

  • rand(), rand_r(), srand()
  • random(), srandom(), initstate(), setstate()
  • random_r(), srandom_r(), initstate_r(), setstate_r()
  • drand48(), erand48(), lrand48(), nrand48(), mrand48(), jrand48(), srand48(), seed48(), lcong48()
  • drand48_r(), erand48_r(), lrand48_r(), nrand48_r(), mrand48_r(), jrand48_r(), srand48_r(), seed48_r(), lcong48_r()
  • strfry(): reuse __initstate_r() and __random_r()

Seed

  • strfry() uses __initstate_r(time(NULL) ^ getpid())

Bugs

Python

Project website: http://www.python.org/

Informations about Python 2.5

Files: Modules/_randommodule.c, Modules/posixmodule.c, Lib/random.py, Lib/os.py

Python 2.5 uses Mersenne Twister engine with os.urandom() as seed. If seed is None, it uses time(&now).

WichmannHill class implements Wichman-Hill random number generator. It was used as Random before Mersenne Twister was implemented (december 2002).

os.urandom()

urandom() has different implementations:

  • Windows: win32_urandom(), in Modules/posixmodule.c, uses CryptGenRandom()
  • vms_urandom(), in Modules/posixmodule.c, uses RAND_pseudo_bytes() from OpenSSL
  • otherwise: urandom(), in Lib/os.py, reads /dev/urandom

Bugs in old Python versions

PHP

Project website: http://www.php.net/

Informations about PHP5

Files: main/reentrance.c, ext/standard/php_rand.h, ext/standard/rand.c, ext/standard/lcg.c

PHP has two main functions: php_rand()->long and php_srand(long). It has four different methods to generate numbers depending on PHP compilation options:

  • (ZTS mode) php_rand_r() + internal seed: The standard LCG (m=1103515245, a=12345)
  • or random() + srandom(): libc best LCG
  • or lrand48() + srand48(): libc 48 bits LCG
  • or rand() + srand(): libc 32 bits LCG

The first method (Standard LCG) is used if PHP is compiled in Thread Safe mode (ZTS).

php_rand() setups the seed at the first call if php_srand() was not called, using GENERATE_SEED(). This macro uses:

  • on Windows: time(), GetCurrentProcessId(), php_combined_lcg()
  • on Linux: time(), getpid(), php_combined_lcg()

And php_combined_lcg() is seeded using: gettimeofday() and getpid() (or thread id in ZTS mode).

rand() has two prototypes: rand() or rand(min, max). If the range is specified, it uses: min + (long)((double)x * (max - min + 1.0) / (randmax + 1.0))

But PHP also includes Mersenne Twister! See functions: mt_rand(), mt_srand() and mt_getrandmax(). If mt_rand() is not seeded, it uses the same entropy than php_rand().

Bugs in old PHP versions

Older versions didn’t call srand() for rand(), shuffle(), etc.

Parrot

BIND

Project website: http://www.isc.org/software/bind

Files

  • lib/dst/prandom.c
  • lib/cylink/rand.c
  • lib/dst/dst_api.c
  • bin/named/ns_main.c

PRNG

BIND uses multiple PRNG depending on the program, and the PRNG depends on the version of BIND.

Seed:

  • the best seed is in prandom.c: it uses /dev/random or a LCG
  • some generators use getpid() and gettimeofday()

PRNG:

  • one LCG in prandom.c
  • two mixed LCG in ns_main.c

Bugs

glib

Project website: http://www.gtk.org/

File: glib/grand.c

Use Mersenne Twister. glib 2.0 uses the following code to seed with an 32 bits unsigned integer:

/* setting initial seeds to mt[N] using         */
/* the generator Line 25 of Table 1 in          */
/* [KNUTH 1981, The Art of Computer Programming */
/*    Vol. 2 (2nd Ed.), pp102]                  */
if (seed == 0) /* This would make the PRNG procude only zeros */
    seed = 0x6b842128; /* Just set it to another number */
mt[0]= seed;
for (mti=1; mti<N; mti++)
    mt[mti] = (69069 * mt[mti-1]);

whereas glib 2.2+ uses:

/* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
/* In the previous version (see above), MSBs of the    */
/* seed affect only MSBs of the array mt[].            */
mt[0]= seed;
for (mti=1; mti<N; mti++)
    mt[mti] = 1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti;

To create the seed, g_rand_new() reads 128 bits (4 uint32) from /dev/urandom on UNIX. If the device can not be used or not available (eg. on Windows), it uses:

g_get_current_time(&now);
seed[0] = now.tv_sec;
seed[1] = now.tv_usec;
seed[2] = getpid();
#ifdef G_OS_UNIX
seed[3] = getppid();
#else
seed[3] = 0;
#endif

where g_get_current_time() is GetSystemTimeAsFileTime() on Windows and gettimeofday() on other OS.

g_rand_double() uses two Mersenne Twister ticks but a strange hack:

/* The following might happen due to very bad rounding luck, but
 * actually this should be more than rare, we just try again then */
if (retval >= 1.0)
    return g_rand_double (rand);

g_rand_int_range() has two versions: 20 (glib 2.0) and 22 (glib 2.2). Read the source code for the details...

pw_gen

File: randnum.c

Seed: use /dev/urandom, or open /dev/random in non blocking mode on failure, or drand48 on failure. drand48 is replaced by random() if drand48() is not available.

pw_random_number(max_num): read bytes into an unsigned int from /dev/(u)random and use (rand_num % max_num). If reading bytes fails, it uses:

#ifdef HAVE_DRAND48
    return ((int) ((drand48() * max_num)));
#else
    return ((int) (random() / ((float) RAND_MAX) * max_num));
#endif

libgcrypt

Project website: http://www.gnupg.org/

Files: cipher/random.c, cipher/rnd_*.c

Support:

  • EGD: try in non blocking mode and then in blocking mode
  • Linux: use /dev/random (level >= 2) or /dev/urandom
  • UNIX: hash output of many programs like “vmstat”, “w”, “netstat”, etc.
  • W32: hash output of many variables (processes, threads, modules, netstat, disk performance, performance data, etc.

gcry_create_nonce()

  • Initialization using time(NULL), getpid(), and a “private key” of 8 bytes generated by gcry_randomize(GCRY_WEAK_RANDOM)
  • hash the internal state using SHA1() for each block of 20 bytes

OpenSSL

Project website: http://www.openssl.org/

Files

  • crypto/rand/md_rand.c
  • crypto/rand/rand_*.c

Functions

  • RAND_bytes(), RAND_pseudo_bytes(): get random bytes
  • RAND_add(), RAND_seed(), RAND_screen(), RAND_event(), RAND_egd(), RAND_egd_bytes(), RAND_query_egd_bytes(): add entropy
  • RAND_status()
  • RAND_file_name(), RAND_load_file(), RAND_write_file()
  • RAND_cleanup()

By default, RAND_bytes() uses ssleay_rand_bytes().

ssleay_rand_bytes()

  • call RAND_poll() at first call
  • use SHA-1 hash
  • use getpid() entropy (maybe to generate different numbers for each process)

RAND_poll()

  • NetWare
    • GetProcessSwitchCount()
    • RunningProcess: current process address
    • RDTSC
    • GetSuperHighResolutionTimer()
  • OpenBSD:
    • arc4random(): call it 8 times (to get 256 bits)
  • OS/2:
    • DosTmrQueryTime()
    • DosQuerySysInfo()
    • DosPerfSysCall()
    • DosQuerySysState()
  • UNIX
    • read 32 bytes from /dev/urandom, /dev/random, /dev/srandom, or EGD
    • getpid()
    • getuid()
    • time(NULL)
  • VMS
    • sys$getjpiw(): processes
    • sys$gettim(): time
  • VxWorks:
  • nothing
  • Windows:
    • CryptGenRandom(): read 64 bytes
    • GetForegroundWindow(): window handle
    • GetCursorInfo(): cursor position
    • GetQueueStatus(): message queue status
    • Heap32ListFirst()
    • Heap32First()
    • Process32First(), Process32Next(): processes
    • Thread32First(), Thread32Next(): threads
    • Module32First(), Module32Next(): modules
    • GlobalMemoryStatus()
    • GetCurrentProcessId()
  • Windows CE (replace CryptGenRandom()):
    • netstatget(L”LanmanWorkstation”)
    • netstatget(L”LanmanServer”)
    • CryptGenRandom(): read 64 bytes
    • CryptGenRandom(), poll the Pentium PRG: read 64 bytes

RAND_bytes() and fork()

After many fork(), if two processes get the same identifier, RAND_bytes() generates the same bytes.

Bugs

  • CVE-2008-0166: OpenSSL 0.9.8c-1 up to versions before 0.9.8g-9 on Debian-based operating systems uses a random number generator that generates predictable numbers, which makes it easier for remote attackers to conduct brute force guessing attacks against cryptographic keys. http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2008-0166

GSL

Project website: http://www.gnu.org/software/gsl/

Files: rng/*.c, rng/gsl_rng.h

Implement many many PRNG.

gsl_rng_uniform_int(n) with n in [1; tick_max]:

scale = tick_max / n;
do {
    result = tick() / scale;
} while (result >= n);

Worst case: n = (tick_max/2 + 1), the while will fails 50% of the time.

gsl_rng_uniform_pos():

do {
    x = get_double();
} while (x == 0);

libcrypto++

Project website: http://www.cryptopp.com/

Files: osrng.cpp, rng.cpp

Classes: AutoSeededX917RNG, MicrosoftCryptoProvider, AutoSeededRandomPool

Engines:

  • MicrosoftCryptoProvider: use CryptGenRandom() from Windows API
  • NonblockingRng: /dev/urandom or MicrosoftCryptoProvider
  • X917RNG: ANSI X9.17 Appendix C. Based on time(NULL), clock(), XOR and a block cipher (eg. DES-EDE3)
  • LC_RNG: Linear Congruential Generator with m=2147483647 and a=16807, or m=2147483647 and a=48271 (original numbers)
  • AutoSeededX917RNG: initialize X917RNG using SHA-256 of OS random (default: non blocking OS device)

Other:

  • MaurerRandomnessTest: the class implements Maurer’s Universal Statistical Test for Random Bit Generators it is intended for measuring the randomness of PHYSICAL RNGs. For more details see his paper in Journal of Cryptology, 1992.

Notes:

  • X917RNG raises an exception if two sequences of bytes are identical

GMP

Project website: http://gmplib.org/

Files:

  • randmt.c, randmt.h: Mersenne Twister (no seed)
  • randmts.c: Mersenne Twister (with seed)
  • randlc2s.c: linear congruential generator (2^32..2^256)

SPRNG

  • SRC/makeseed.c: make_new_seed() uses time() + localtime()

libuuid

Files: gen_uuid.c

Funtions: get_random_bytes(), get_random_fd()

get_random_fd()

  • try to open /dev/urandom or /dev/random

  • on success, set FD_CLOEXEC flag on the file descriptor

  • initialize srand() using:

    • getpid()
    • getuid()
    • gettimeofday() (use seconds and microseconds)
  • initialize jrand_seed (array of 3 unsigned short) using:

    jrand_seed[0] = getpid() ^ (tv.tv_sec & 0xFFFF);
    jrand_seed[1] = getppid() ^ (tv.tv_usec & 0xFFFF);
    jrand_seed[2] = (tv.tv_sec ^ tv.tv_usec) >> 16;
    
  • calls rand() a random numbers of times: 0..31 times. Use gettimeofday() to generate the random number

rand() and jrand48() are initialized using the same timestamp.

jrand is used on Linux if gettid system call and jrand48() function are available.

get_random_bytes()

  • read bytes from /dev/urandom or /dev/random, if the file is available. Stop after 16 consecutive read() errors.

  • always mix the buffer with:

    for (cp = buf, i = 0; i < nbytes; i++)
        *cp++ ^= (rand() >> 7) & 0xFF;
    
  • if jrand is enabled, mix also the buffer with:

    #ifdef DO_JRAND_MIX
        memcpy(tmp_seed, jrand_seed, sizeof(tmp_seed));
        jrand_seed[2] = jrand_seed[2] ^ syscall(__NR_gettid);
        for (cp = buf, i = 0; i < nbytes; i++)
            *cp++ ^= (jrand48(tmp_seed) >> 7) & 0xFF;
        memcpy(jrand_seed, tmp_seed,
               sizeof(jrand_seed)-sizeof(unsigned short));
    #endif
    

get_clock()

Use:

THREAD_LOCAL uint16_t clock_seq;
get_random_bytes(&clock_seq, sizeof(clock_seq));
clock_seq &= 0x3FFF;

uuid__generate_time()

Create node_id once using:

static unsigned char node_id[6];
get_random_bytes(node_id, 6);
node_id[0] |= 0x01;   /* Set multicast bit */

uuid__generate_random()

Use:

get_random_bytes(buf, sizeof(buf));
... and set fixed bits (version, variant) ...

uuid_generate()

Use random UUID if /dev/urandom or /dev/random was opened correclty. Otherwise, generates an time based UUID.

Linux kernel

Project website: http://www.kernel.org/

Files

  • drivers/hw_random/*.c
  • drivers/char/random.c

Hardware RNG drivers

  • AMD chipsets
  • AMD Geode LX CPUs
  • Intel chipsets
  • Intel IXP4xx family of NPUs
  • TI OMAP CPU family
  • PA Semi processor
  • VIA chipsets

Bugs

Gnome keyring

Project website: http://live.gnome.org/GnomeKeyring

Files: /daemon/keyrings/gkr-keyring-binary.c

Functions: init_salt(), gkr_keyring_binary_generate()

Code to generate the hash iterations:

keyring->hash_iterations = 1000 + (int) (1000.0 * rand() / (RAND_MAX + 1.0));

Code to generate the salt:

static void
init_salt (guchar salt[8])
{
    gboolean got_random;
    int i, fd;

    got_random = FALSE;
#ifdef HAVE_DEVRANDOM
    fd = open ("/dev/random", O_RDONLY);
    if (fd != -1) {
        struct stat st;
        /* Make sure it's a character device */
        if ((fstat (fd, &st) == 0) && S_ISCHR (st.st_mode)) {
            if (read (fd, salt, 8) == 8) {
                got_random = TRUE;
            }
        }
        close (fd);
    }
#endif

    if (!got_random) {
        for (i=0; i < 8; i++) {
            salt[i] = (int) (256.0*rand()/(RAND_MAX+1.0));
        }
    }

}

OpenBSD

A vulnerability was introduced in the random device the 13 April 2000. It was discovered and fixed the 23 january 2001:

Most important change of the commit:

- for (; n--; buf++) {
+ while (n--) {

Because of this change, only 8 bits (the first byte of the buffer) was used, instead of the whole buffer.