bugtraq - Re: Flaw in commonly used bash random seed method

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date: Wed, 5 Apr 2006 10:32:16 -0700
From: Steve VanDevender <stevev@...adecimal.uoregon.edu>
To: bugtraq@...urityfocus.com
Subject: 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.