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.
   [ ... 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 *) &in;
        for (i=0; i<8; i++)
                printf("%2X ", *p++);
        printf("\n");

        return(0);
}