Re: Flaw in commonly used bash random seed method

[Steve VanDevender <stevev () hexadecimal uoregon edu>]

Dave Korn writes:
> Matthijs wrote:
> > I hope nobody generates passwords with ANY kind of pseudo-RNG.
>
>   This is the main point, anyway.
>
> > By the way, if the random function can only generate numbers between 0
> > and 32767, won't 2 bytes be enough then? The algorithm will perform a
> > modulo calculation anyway, so 4 bytes won't really add anything. Of
> > course, it is much better then only one byte.
>
>   You have made the assumption that the size of the seed matches the size of 
> the output values.  In fact, this is highly unlikely to be correct.  In the 
> standard C library (on which this implementation is almost certainly based), 
> the seed is a full 32-bits even though the output is 15.  That's because the 
> seed is the internal state of the generator, and if it only had the same 
> number of bits as the output, then the next output from the generator could 
> be wholly determined by knowing the current output, and the generator would 
> only be able to output 32768 numbers before the sequence repeated.  Think of 
> the extra bits as selecting one of 2^17 different permutations of the 2^15 
> possible output values; if the generator didn't have more internal state 
> than it puts in its output, there would only ever be one constant 
> permutation, the seed would choose your starting point at that permutation, 
> and each output number you see generated would always be followed by the 
> exact same next one every time.

As written:

static int
brand ()
{
  rseed = rseed * 1103515245 + 12345;
  return ((unsigned int)((rseed >> 16) & 32767)); /* was % 32768 */
}

the period of brand() is 2^31 (assuming the constants for the linear
congruential random number generator have been appropriately chosen).
The N low-order bits of a linear congruential random number generator
cycle with a period of at most 2^N.  because higher-order bits can't
affect lower-order bits.  If the low 15 bits of rseed were output by
brand(), not only would brand() alternate even/odd but the effective
period would be only 2^15.  Choosing bits 16-30 of rseed at least avoids
the even/odd problem.  But it's only useful to seed brand() with 31
bits, allowing you to choose where in the period 2^31 output cycle the
random number generator starts.