Bug 9920 - use of `long int' in srandom_r changes results under 64bit
Summary: use of `long int' in srandom_r changes results under 64bit
Status: RESOLVED FIXED
Alias: None
Product: glibc
Classification: Unclassified
Component: libc (show other bugs)
Version: 2.8
: P2 normal
Target Milestone: ---
Assignee: Ulrich Drepper
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2009-03-03 22:42 UTC by Ben Jackson
Modified: 2014-07-01 20:39 UTC (History)
2 users (show)

See Also:
Host: x86_64-redhat-linux
Target: x86_64-redhat-linux
Build: x86_64-redhat-linux
Last reconfirmed:
fweimer: security-


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Ben Jackson 2009-03-03 22:42:59 UTC
srandom_r (random_r.c) initializes a state vector for random_r using a LCRNG
based on a primitive root of 2^31-1 (a Mersenne prime).  The root is 7, and the
LCRNG uses 7^5 (16807).  16807^n % (2^31-1) touches every number in 1..(2^31-1)
as you iterate along n.  srandom_r uses this property to take the input seed
plus 30 more numbers to make a state vector which is subsequently used by
random_r().  The curious case is the first step, where a full 32-bit value is
used as the starting seed.

srandom_r takes an unsigned int seed, but does most of its work in int32_t. 
Somewhere in the distant past someone came up with a trick for the modular
multiply by 16807:

      long int word;
      ...
      word = seed; /* seed is unsigned int */
      ...
      /* This does:
           state[i] = (16807 * state[i - 1]) % 2147483647;
         but avoids overflowing 31 bits.  */
      long int hi = word / 127773;
      long int lo = word % 127773;
      word = 16807 * lo - 2836 * hi;
      if (word < 0)
        word += 2147483647;
      *++dst = word;

The problem is that 'long int' changes size between 32bit and 64bit builds. 
When 'long int' is 64 bit, the entire unsigned seed value fits, so a seed above
2^31-1 does not fold into a negative.  So 'srandom(0xFFFFFFFFul); x = random()'
produces different results if glibc is built 64bit than if it is built 32bit.

The reason has to do with the multiply under modulo 2^31-1.  0xFFFFFFFFul
smashed into an int32_t acts like -1 which is congruent to 2147483646 (under mod
2^31-1).  When it's smashed into int64_t (long int under the 64 bit build) it
FITS so it's 4294967295 which is congruent to 1.  The seed itself is still
smashed into a 32 bit signed int *in the state vector* so you still get
different random output for a seed of -1 than for 1, just not what you'd get on
a 32 bit system.

I left severity at "normal" because some users of random() really care about
reproducibility with a given seed.  Any who do will be greatly surprised when
moving to 64 bit!

(this bug exists at glibc < 2.8, probably back at least to 2.5 and maybe
forever.  bsd libc has code clearly inspired by the same origins but calls out
the bit widths explicitly and avoids this problem)
Comment 1 Ulrich Drepper 2009-04-24 03:59:27 UTC
I've changed the code to have the same results on 32 and 64 bit.