Home page logo
/

bugtraq logo Bugtraq mailing list archives

Re: Flaw in commonly used bash random seed method
From: Steve VanDevender <stevev () hexadecimal uoregon edu>
Date: Wed, 5 Apr 2006 10:32:16 -0700

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.


  By Date           By Thread  

Current thread:
[ Nmap | Sec Tools | Mailing Lists | Site News | About/Contact | Advertising | Privacy ]