[1537] in bugtraq
Re: passwd hashing algorithm
daemon@ATHENA.MIT.EDU (David A. Wagner)
Wed Apr 19 03:49:07 1995
From: "David A. Wagner" <dawagner@phoenix.Princeton.EDU>
To: jfh@rpp386.cactus.org (John F. Haugh II)
Date: Wed, 19 Apr 1995 00:21:09 -0400 (EDT)
Cc: dawagner@phoenix.Princeton.EDU, bugtraq@fc.net
In-Reply-To: <9504190252.AA26972@rpp386.cactus.org> from "John F. Haugh II" at Apr 18, 95 09:52:19 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.
[ ... 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]
If not, I issue you a challenge. I've included a small
program at the end which implements (1) using libdes:
$ ./newcrypt abcdefgh 12345678
E7 B3 AF 1E D5 A8 34 10
$ ./newcrypt xxxx yyyy
5D 4F 2F 99 F4 1 69 B3
Compile it with libdes.a and make sure you get the same
output for the test data above (for portability). Pick
your own two password strings (at most 8 bytes long each)
and send or post the output of the program.
I'll find two password strings of my own which give the
same output (but they're *not* necessarily the same as your
two strings: they just produce the same hash!).
Gimme a week or so to whip up the program and find the
spare CPU cycles -- I'll need 2^36 DES ops, which is just
large enough to be a small pain in the ass for me.
This should be enough to convince you that it's useless
as a password hashing scheme (I hope!).
If I'm mistaken here, I'm sure someone will inform me,
and all the egg will be on my face :-)
>
> SecureWare uses a mechanism similar to this and it is part of one of
> their security offerings. I've used a slightly different, but similar,
> approach for several years
>
Good lord! Can anyone give more details? [ The details
tend to matter in this business: something similar but
slightly different might be safe. :-) ]
Sorry to the rest of you bugtraq folks: I would be taking
this to personal email, except for the fact that someone
actually uses the broken scheme -- yikes! -- that's my ObBug.
-------------------------------------------------------------------------------
David Wagner dawagner@princeton.edu
/* newcrypt.c -- Dave Wagner dawagner@princeton.edu */
#include <stdio.h>
#include "des.h"
#define ITERS 25
do_onekey(in, k)
des_cblock *in;
unsigned char *k;
{
des_cblock out, key;
des_key_schedule sched;
int i;
bzero((unsigned char *) &key, sizeof(des_cblock));
strncpy((unsigned char *) &key, k, sizeof(des_cblock));
des_set_odd_parity(&key);
des_set_key(&key, sched);
for (i=0; i<ITERS; i++) {
des_ecb_encrypt(in, &out, sched, /* encrypt */ 1);
bcopy(&out, in, sizeof(des_cblock)); /* in := out; */
}
}
main(argc, argv)
int argc;
char **argv;
{
des_cblock in;
unsigned char *p;
int i;
if (argc != 3) {
fprintf(stderr, "Usage: %s key1 key2\n", argv[0]);
exit(1);
}
bzero(&in, sizeof(des_cblock));
do_onekey(&in, argv[1]);
do_onekey(&in, argv[2]);
p = (unsigned char *) ∈
for (i=0; i<8; i++)
printf("%2X ", *p++);
printf("\n");
return(0);
}
