Re: passwd hashing algorithm

[pcl () foo oucs ox ac uk (Paul C Leyland)]

David Wagner, dawagner () princeton edu, wrote:

> Just one trivial elaboration on an informative message from
> Steve Bellovin:
> >                          There's only one facet of triple DES that's
> > at all useful here:  it provides an easy way to accept longer passwords.
> > But as I've noted, there are other ways to do that.  (Double DES is
> > most likely quite sufficient if you want to pursue that route, though;
> > few people are going to use passwords longer than 16 characters, and
> > the attacks on double DES described in the cryptographic literature
> > require O(2^55) storage, if I recall correctly -- I may be off by a
> > factor or so of 2.)
>
> If anyone actually plans to use double DES (or triple DES)
> for hashing passwords (which I don't recommend), be aware
> that there's a huge difference between:
>
> 1. 25 iterations of DES with the first 8 bytes of the
>    password as key, followed by 25 iterations of DES
>    with the second 8 bytes of password as key.

This is essentially how DEC's C2-security in OSF/1 works for passwords
9-16 characters long.  A further weakness is that the output of
bigcrypt() gives the length of the plaintext password in units of 8
characters!  So if ever you can get hold of the password file, you can
concentrate on the easy cases.  In particular, it might be worth while
making a complete table of all common suffices and then searching the
9-16 character portions for matches.

The old crypt16(), from Ultrix and supported as a migration tool in
OSF/1 was even worse.  It used 20 rounds on one block and 5 on the
second, making password searching even faster than traditional
crypt().  I wrote the mods. for Crack to use crypt16().  The suffix
attack works like a dream -- 5 times faster than regular Crack -- and
concentrating on the <9 char. passwords goes in 80% of the time.  DEC
screwed up badly there.
> 2. repeat 25 times:
>      an iteration of DES with the first 8 bytes of the
>      password as key, followed by an iteration of DES
>      with the second 8 bytes of password as key.
>
> (1) can be broken on a workstation with ~ 2^32 steps (and
> very little in the way of memory); (2) is probably very
> strong.  The same comment goes for triple DES.

But still not strong enough.  Password guessing will work in many
cases because people will still choose guessable passwords, unless you
have a fascist password program.  If you have one of those,
traditional crypt is still adequate, IMO.

> The moral of the story?  If you wanna hash a long string,
> use a hash function (i.e. MD5), not a block cipher; or
> else be very careful. :-)

IMO, you should do both.


Paul