Re: passwd hashing algorithm

[isdmill () gatekeeper ddp state me us (David Miller)]

On Wed, 19 Apr 1995, David A. Wagner wrote:

> > > 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.
>    [ ... better version deleted ... ]
> > > (1) can be broken on a workstation with ~ 2^32 steps (and
> > > very little in the way of memory);
> >
> > I've never seen anything resembling a convincing argument for this point.
>
> Hrmm, well, I could give you the crypto explanation...do you
> want me to?  [Keywords: meet-in-the-middle, birthday attack]

Meet in the middle?  You have enough space to make that practical?
Correct me if I'm wrong, but meet-in-the-middle means that you're going 
to do the first part *and save all the output* , then do the last part 
(backwards) to check if it matches any of the stored strings.

Check my math here, cause I often slip up.....

You're going to store 2^56 strings of 8 bytes, then compare the result of 
2^56 operations to those 2^56 stored strings?

Can I have a workstation like that? :) :)

You've obviously got something else in mind.  By all means, please tell 
me how you're going to do it in 2^32 DES steps (still 2^35 (32 GB) bytes of 
storage, a non-trivial sum.)  Details and crypto-babble welcome:)


> If not, I issue you a challenge.  I've included a small
> program at the end which implements (1) using libdes:

[challenge deleted]

I'll be happy to try it if you're serious about throwing that many 
resources at it.  First, tho, I'd kind of like to hear the theory behind 
it:) 

--- David
----------------------------------------------------------------------------
                It's *amazing* what one can accomplish when 
                    one doesn't know what one can't do!