[1545] in bugtraq
Re: passwd hashing algorithm
daemon@ATHENA.MIT.EDU (David A. Wagner)
Wed Apr 19 19:38:35 1995
From: "David A. Wagner" <dawagner@phoenix.Princeton.EDU>
To: isdmill@gatekeeper.ddp.state.me.us (David Miller)
Date: Wed, 19 Apr 1995 16:34:29 -0400 (EDT)
Cc: dawagner@phoenix.Princeton.EDU, jfh@rpp386.cactus.org, bugtraq@fc.net
In-Reply-To: <Pine.3.89.9504191429.A8533-0100000@gatekeeper.ddp.state.me.us> from "David Miller" at Apr 19, 95 02:25:23 pm
>
> > > > 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
