Home page logo

bugtraq logo Bugtraq mailing list archives

Re: passwd hashing algorithm
From: isdmill () gatekeeper ddp state me us (David Miller)
Date: Wed, 19 Apr 1995 14:25:23 -0400 (EDT)

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 

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

  By Date           By Thread  

Current thread:
[ Nmap | Sec Tools | Mailing Lists | Site News | About/Contact | Advertising | Privacy ]