Re: Flaw in commonly used bash random seed method
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.