Re: passwd hashing algorithm

[dawagner () phoenix Princeton EDU (David A. Wagner)]

> > > > 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.
>
> 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:)

Ok, here's the explanation.  I'd love to hear feedback about
whether this is on charter for bugtraq; if it's not, email me
and I'll avoid spamming y'all in the future.

The hash function (1) above takes the all 0 plaintext block,
encrypts it 25 times under 8 bytes of password W, and then
encrypts that 25 times under the other 8 bytes of password W',
producing the ciphertext C = Encrypt^25(W', Encrypt^25(W, 0)).

The conceptually simplest attack works like this:

1. Generate ~ 2^32 random 8 byte keys K_i and store
        A_i = Encrypt^25(K_i, 0)
   in a hash table.
2. Generate ~ 2^32 random 8 byte keys K'_j and store
        B_j = Decrypt^25(K'_j, C)
   in the same hash table.
3. Find any match where A_i = B_j; then K_i, K'_j
   will work as a valid 16 byte password, since
        Encrypt^25(K'_j, Encrypt^25(K_i, 0))
                = Encrypt^25(K'_j, A_i) = Encrypt^25(K'_j, B_j) = C.

[Note that in all probability (K_i, K'_j) != (W, W');
but with this hash we don't need to find the exact
password the user picked, just any one which gives
the same hash output.]

By the birthday paradox, there will be a match in step 3
above with probability about 1/2 [since each A_i, B_j
block is 64 bits wide and we generated ~ 2^32 values of
each].  If we try twice we'll probably succeed.

This requires ~ 2^38 DES ops and ~ 2^35 bytes of memory.
As you noted, the memory requirements are a bit high here
[unless you use an Exabyte tape or somesuch, blech].  Also,
it doesn't parallelize very nicely.

Fortunately, the algorithm can be improved.  Wiener and
Oorschot have discovered an (elegant!) algorithm which
will do the birthday attack with ~ 2^38 DES ops and
negligible amounts of memory; it also works great in
parallel.  It's a nifty method for detecting cycles
in periodic functions.  See below for a reference.

I have implemented their new algorithm, so I can say
with experience that it really is a damn efficient
piece of machinery.  For example, I used it to find 
this non-trivial collision in Unix's crypt(3) hash:

crypt("2NGGMda3", "Hx") = "yX8CL2luKyI"
crypt("gnB9Gw1j", "s8") = "yX8CL2luKyI"
[after removing the salt which crypt(3) prepends to its output]

This does *NOT* break crypt(3)!  It's a totally useless
result, but it proved to me that the algorithm works well.

It took a total of 6.1 billion trial crypt()s using the
spare CPU time on 27 Sun workstations (LXs and Sparc 2s).
I got about 1310 crypts per second, so I figure it took
about 1290 CPU hours, total.

Thus, from this experience, I estimate one can run the
birthday attack I described earlier to break the double-DES
hash (1) with about 2600 CPU hours.  This is far too small
an amount: if a college student like me can put together
enough compute power to invert the hash over a week or
two with spare CPU cycles, the hash function is clearly
insecure.

I'm interested in hearing more information about the
OSF/1 or Ultrix hash function -- is there any place where
I can get source or anything?  I have access to one OSF/1
box, but it doesn't have any man pages or anything on a
crypt16().

% I'm not sure if I've got the reference 100% correct;
% I got the conference title by email from Wiener, but
% haven't been able to find it in our library.
@inproceedings{parallel-cycle-search,
        author = {Paul C. van Oorschot and Michael J. Wiener},
        title = {Parallel Collision Search with Application to Hash Functions
                        and Discrete Logarithms},
        booktitle = {2nd {ACM} Conference on Computer and Communications
                        Security},
        year = {1994}
}

I have a postscript version of this paper from the authors;
if you can't find it in your library, you can probably get
a copy from them.  Better still, if they okay-ed it, I'd put
the paper up for anonymous ftp somewhere...

-------------------------------------------------------------------------------
David Wagner                                             dawagner () princeton edu