From:	 Peter W 
To:	 BUGTRAQ@SECURITYFOCUS.COM
Subject: Re: flaw in RH ``mkpasswd'' command (importance of seeds &
	 algorithms)
Date:	 Thu, 12 Apr 2001 08:44:26 -0400

On Wed, Apr 11, 2001 at 04:32:38PM +0100, Shez wrote:
> 	The mkpasswd password generator that ships in the ``expect'' package of (at
> least RedHat 6.2) generates only a relatively small number (2^15 for the
> default password length) of passwords.  Presumably this is a result of
trying
> to apply too many rules of what is a ``good'' password to the generation
> process.

The 'man' page suggests it should be more like 2^46 in default mode.
In default mode you have >= 2 lowercase chars (26**2), >= 2 uppercase
chars (26**2), >= 2 digits (10**2), and three others (62**3), for
10891017612800 possible passwords. It would probably be nice to make the
script support characters like ~!@#$%^&*()-+, for serious use, don't you
think?

I expect (sorry!) this, like PalmOS/Strip, is a seeding/PRNG problem
at its core. 'mkpasswd' is basically a Tcl script, right? Let's take a look:

set _ran [pid]
proc rand {m} {
        global _ran

        set period 259200
        set _ran [expr ($_ran*7141 + 54773) % $period]
        expr int($m*($_ran/double($period)))
}

The seed is the process ID, so naturally the number of passwords is limited
to the size of your process table (and even worse, is highly predictable).

Use this code for better results:

proc srand {} {
        global _ran
        set seedsource /dev/urandom    ;# faster
        ;#set seedsource /dev/random      ;# better
	;# 'od' is used as an easy way of converting
	;# /dev/random data to decimal numbers; suggestions welcome
        if {[file readable $seedsource] && [file executable /usr/bin/od]} {
                set _ran 1
                ;# 5 iterations is enough for 2130706432 possibilities, and
                ;# srand() cannot handle a seed larger than the largest
                ;# integer, which is          2147483647 on x86
		set modval 127
                for {set i 0} {$i < 5} {incr i} {
                        regsub {^0*} [lindex [exec od -N 1 -t d2 $seedsource]
1] {} bval
                        if {[string length $bval] == 0} {set bval 0}
                        set bval [expr ( $bval % $modval ) + 1]
                        set _ran [expr $_ran * $bval]
			set modval 64
                }
        } else {
                puts stderr "Error: unable to get good random seed!"
                exit 1
        }
        expr srand($_ran)
}
;#srand		;# if we only wanted to seed once
proc rand {m} {
        srand         ;# re-seed every time for more random passwords
        return [expr int($m * rand())]
}

This requires Tcl 8, since I'm using its rand() function. Tcl 8 defaults
to using the system clock for the seed of its PRNG, which is why I'd go
to the trouble of getting a better seed. Still, with srand() only accepting
some 2.1e9 seed values, there are at most "only" 2.1e9 possible passwords
if you use the Tcl 8 rand() function and only seed it once. But testing
suggests that seeding only once is a bad idea...

How effective is the code? Using /dev/urandom and a single seeding, in
120000 invocations I had some 88,000+ unique passwords w/ mkpasswd's default
mode; clearly breaking the 2^15 barrier, but a large number of duplicates.
With /dev/random things move much more slowly, but after some 22000
runs, it's showing about as many dupes as it did after 22000 runs with
/dev/urandom. So the rand() routine in Tcl 8.x seems not very desirable
for security applications, not that this is a big surprise.[0] On the
other hand, with the faster but "weaker" /dev/urandom as the random source
but re-seeding with every use of the rand function (as shown above), I've
made over 45000 passwords with no duplication.

In any case, this is yet another nice study of the importance of both
good seeding *and* good PRNG algorithms for security applications.

-Peter

[0] The algorithm used in Red Hat's mkpasswd looks like one I first
encountered in Brent Welch's book, and was an attempt to add a PRNG
to Tcl 7.6. In that routine, you can clearly see that the size of
$period limits the number of possible random values. Tcl is mostly
a string-based language, so it's not surprising that we run into
trouble getting strongly random numbers out of it; though it's also
a language that it easily extended via DLL/so libraries, so it's
not a fatal problem. But it is important to understand if you're
writing security-related applications, or running a casino.