6358704 2001-04-12 08:44 -0400 /100 rader/ Peter W <peterw@USA.NET>
Sänt av: joel@lysator.liu.se
Importerad: 2001-04-12 22:26 av Brevbäraren
Extern mottagare: BUGTRAQ@SECURITYFOCUS.COM
Externa svar till: peterw@USA.NET
Mottagare: Bugtraq (import) <16497>
Ärende: Re: flaw in RH ``mkpasswd'' command (importance of seeds &
------------------------------------------------------------
algorithms)
From: Peter W <peterw@USA.NET>
To: BUGTRAQ@SECURITYFOCUS.COM
Message-ID: <20010412084426.A8850@usa.net>
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.
(6358704) /Peter W <peterw@USA.NET>/------(Ombruten)
6358782 2001-04-12 13:18 +0100 /32 rader/ Shez <shez@MOLIONS.COM>
Sänt av: joel@lysator.liu.se
Importerad: 2001-04-12 22:44 av Brevbäraren
Extern mottagare: BUGTRAQ@SECURITYFOCUS.COM
Externa svar till: shez@MOLIONS.COM
Mottagare: Bugtraq (import) <16500>
Kommentar till text 6358602 av Lee Howard <faxguy@DEANOX.COM>
Ärende: Re: flaw in RH ``mkpasswd'' command
------------------------------------------------------------
From: Shez <shez@MOLIONS.COM>
To: BUGTRAQ@SECURITYFOCUS.COM
Message-ID: <01041213184501.00669@kara>
Hi,
PeterW@usa.net pointed out to me that if the man page for
mkpasswd is correct then this shouldn't be the problem, and that it
may be a seeding problem. The code appears to seed of pid and uses
its own generator: set _ran [pid]
proc rand {m} {
global _ran
set period 259200
set _ran [expr ($_ran*7141 + 54773) % $period]
expr int($m*($_ran/double($period)))
}
Anyhow, writing a perl/any language replacement would be a good move
for anyone who's been using this command.
Cheers
Shez
On Thursday 12 April 2001 00:55, you wrote:
> Although I wonder if they're not outweighing the risk of dropping some of
> those rules over the risk of having fewer possible passwords. (Not to say
> that I agree with that, though.)
>
> Lee.
(6358782) /Shez <shez@MOLIONS.COM>/-------(Ombruten)