Re: SHA-1 in libcrypt

[Geoff Keating <geoffk at cygnus dot com>]

> Date: Mon, 17 Jul 2000 21:40:13 -0700
> From: RoboHak <RoboHak@protovision.org>
> Cc: kettenis@wins.uva.nl, libc-alpha@sourceware.cygnus.com
> Content-Disposition: inline
> 
> On Mon, Jul 17, 2000 at 01:14:18PM -0700, Geoff Keating wrote:
> > You haven't said why you want SHA...

> First of all, it's 160-bit which makes it more resistant to attacks
> than MD5 which is 128-bit.  Second, MD5 has attacked successfully,
> producing collisions.  Third, it is considered the most secure
> one-way hash function by many of the top cyptographers, including
> Bruce Schneier.  He also recommends SHA over MD5 and his own
> blowfish cipher, which is what OpenBSD uses.  Also, SHA is required
> to be used by the U.S. government, so using SHA in glibc would allow
> Linux systems to be used in those enviroments.

Aah.  Happily, none of these (except possibly the last) are good
reasons.  I don't believe that anyone knows how to perform 2^127
calculations, so increasing this to 2^159 is not particularly helpful.
Finding a collision in MD5 only means that if you choose one very
special password, then there are actually two very special passwords
you can login with, and is a much easier task than reversing the hash
(you could do it by brute force in 2^64 computations).  The way MD5 is
used in the algorithm makes it much more resistant to cryptanalytic
attacks than just MD5, because it is repeated many times.  Bruce
doesn't make this recommendation for password hashing, but for digital
signatures, and for that I completely agree.  Finally, US government
people who absolutely must use an approved cipher can use the
DES-based password hashing.  It'd be silly, but if they must then they
can.

The reasons -not- to make your proposed change are that, firstly, it
increases glibc bloat; secondly, it wouldn't be compatible with other
systems (at least now we're compatible with most of the BSDs);
thirdly, it provides no features for users (unlike the MD5-based
hashing which allowed unlimited length passphrases, a very useful
feature that fixes one of the worst security problems of the DES-based
crypt); and fourthly, any security improvement that it does make is
made in the wrong place.  

The best attack on the MD5-based hashing is not trying 2^128 passwords
at random, but instead performing searches with dictionary words and
short passwords.  To make this harder, you would want to adjust the
algorithm, like the OpenBSD blowfish algorithm, so that it can be made
to run for a variable number of iterations, and ensure that it runs
for a `substantial fraction of a second', say 0.1 seconds.  That way a
million-word dictionary attack would take more than a day (and who
uses a plain dictionary word as their password?), and checking all
6-character lowercase passwords would take about a year on a single
processor.

-- 
- Geoffrey Keating <geoffk@cygnus.com>