OpenBSD bug in the random() function

on 20 Mar 2012 by Mukund (@muks)

I now work for ISC through Banu (which handles my payroll and some other stuff in India). These days, among other things, we're trying to get BIND 10 to work on OpenBSD. Yesterday, I stumbled upon a bug in random() on OpenBSD (tested with OpenBSD 5.0 on amd64). The bug is that if you call srandom(0) to initialize the RNG, random() will always return 0. Here is a testcase:

#include <stdio.h>
#include <stdlib.h>

int
main (int argc, char *argv[])
{
  int i;

  srandom (0);

  for (i = 0; i < 32; i++)
    printf ("%ld\n", random ());

  return 0;
}

Download random.c. This should print 32 zeroes on OpenBSD and 32 random numbers on correct implementations.

POSIX describes the output of random():

This does not seem to be deliberately introduced behavior. The OpenBSD code for srandom() looks like this:

void
srandom(unsigned int x)
{
  int i;
  int32_t test;
  div_t val;

  if (rand_type == TYPE_0)
    state[0] = x;
  else {
    state[0] = x;
    for (i = 1; i < rand_deg; i++) {
      /*
       * Implement the following, without overflowing 31 bits:
       *
       *	state[i] = (16807 * state[i - 1]) % 2147483647;
       *
       *	2^31-1 (prime) = 2147483647 = 127773*16807+2836
       */
      val = div(state[i-1], 127773);
      test = 16807 * val.rem - 2836 * val.quot;
      state[i] = test + (test < 0 ? 2147483647 : 0);
    }
    fptr = &state[rand_sep];
    rptr = &state[0];
    for (i = 0; i < 10 * rand_deg; i++)
      (void)random();
  }
}

(Taken from lib/libc/stdlib/random.c and modified to fit.)

In this scope, rand_type is TYPE_3 by default. When srandom(0) is called, state[0] is set to 0 and it follows that state[1]...state[rand_deg-1] are set to 0 inside the for loop. random() then will always return 0. The bug is technically in the srandom() implementation, but the output of random() is where it is visible to a libc user.

The FreeBSD implementation of srandom() looks like this:

01: static inline uint32_t good_rand (x)
02:      int32_t x;
03: {
04: #ifdef  USE_WEAK_SEEDING
05:   /*
06:    * Historic implementation compatibility.
07:    * The random sequences do not vary much with the seed,
08:    * even with overflowing.
09:    */
10:   return (1103515245 * x + 12345);
11: #else   /* !USE_WEAK_SEEDING */
12:   /*
13:    * Compute x = (7^5 * x) mod (2^31 - 1)
14:    * wihout overflowing 31 bits:
15:    *      (2^31 - 1) = 127773 * (7^5) + 2836
16:    * From "Random number generators: good ones are hard to find",
17:    * Park and Miller, Communications of the ACM, vol. 31, no. 10,
18:    * October 1988, p. 1195.
19:    */
20:   int32_t hi, lo;
21: 
22:   /* Can't be initialized with 0, so use another value. */
23:   if (x == 0)
24:     x = 123459876;
25:   hi = x / 127773;
26:   lo = x % 127773;
27:   x = 16807 * lo - 2836 * hi;
28:   if (x < 0)
29:     x += 0x7fffffff;
30:   return (x);
31: #endif  /* !USE_WEAK_SEEDING */
32: }
33: 
34: void
35: srandom(x)
36:      unsigned long x;
37: {
38:   int i, lim;
39: 
40:   state[0] = (uint32_t)x;
41:   if (rand_type == TYPE_0)
42:     lim = NSHUFF;
43:   else {
44:     for (i = 1; i < rand_deg; i++)
45:       state[i] = good_rand(state[i - 1]);
46:     fptr = &state[rand_sep];
47:     rptr = &state[0];
48:     lim = 10 * rand_deg;
49:   }
50:   for (i = 0; i < lim; i++)
51:     (void)random();
52: }
53:

(Taken from lib/libc/stdlib/random.c and modified to fit.)

Here, successive state[i]s in the for loop are set to the output of good_rand(), and good_rand() checks if a 0 is passed (line 23 above) and uses a different value if that's the case. Because of this check, FreeBSD doesn't have this bug.

The glibc implementation of __srandom_r(), which srandom() wraps, looks like this:

01: int
02: __srandom_r (seed, buf)
03:      unsigned int seed;
04:      struct random_data *buf;
05: {
06:   int type;
07:   int32_t *state;
08:   long int i;
09:   int32_t word;
10:   int32_t *dst;
11:   int kc;
12: 
13:   if (buf == NULL)
14:     goto fail;
15:   type = buf->rand_type;
16:   if ((unsigned int) type >= MAX_TYPES)
17:     goto fail;
18: 
19:   state = buf->state;
20:   /* We must make sure the seed is not 0.  Take arbitrarily 1 in this case.  */
21:   if (seed == 0)
22:     seed = 1;
23:   state[0] = seed;
24:   if (type == TYPE_0)
25:     goto done;
26: 
27:   dst = state;
28:   word = seed;
29:   kc = buf->rand_deg;
30:   for (i = 1; i < kc; ++i)
31:     {
32:       /* This does:
33:            state[i] = (16807 * state[i - 1]) % 2147483647;
34:          but avoids overflowing 31 bits.  */
35:       long int hi = word / 127773;
36:       long int lo = word % 127773;
37:       word = 16807 * lo - 2836 * hi;
38:       if (word < 0)
39:         word += 2147483647;
40:       *++dst = word;
41:     }
42: 
43:   buf->fptr = &state[buf->rand_sep];
44:   buf->rptr = &state[0];
45:   kc *= 10;
46:   while (--kc >= 0)
47:     {
48:       int32_t discard;
49:       (void) __random_r (buf, &discard);
50:     }
51: 
52:  done:
53:   return 0;
54: 
55:  fail:
56:   return -1;
57: }
58:

(Taken from stdlib/random_r.c and modified to fit.)

This code checks if seed is 0 (line 21 above) and uses a different value if that's the case. So, even glibc doesn't have this bug. srandom(0); and srandom(1); with glibc have the same effect. Note that srandom(0); and srandom(123459876); on FreeBSD don't have the same effect as state[0] is still 0 on FreeBSD when the seed is 0.

I don't think this bug is severe, but the OpenBSD developers will likely want it to be fixed for the sake of correctness. Yesterday, I mentioned it in the #openbsd IRC channel on Freenode. I've requested my colleague to report it to the OpenBSD mailing lists as he's already subscribed.

Licenses: OpenBSD and FreeBSD code above are covered by BSD licenses. glibc code is covered by the GNU Lesser General Public License version 2.1 or above. As these are just minor fragments for the sake of illustrating the bug, I'm not including the full licenses here.

Update: The OpenBSD developers have fixed the bug quickly! And it has also been assigned CVE-2012-1577.