Date: Mon, 29 Jul 1996 23:08:32 +0200 From: Poul-Henning Kamp <phk@critter.tfs.com> To: Nathan Lawson <nlawson@kdat.csc.calpoly.edu> Cc: freebsd-security@freebsd.org Subject: Re: Crack 4.1 patches for FBSD Message-ID: <1430.838674512@critter.tfs.com> In-Reply-To: Your message of "Mon, 29 Jul 1996 12:01:38 PDT." <199607291901.MAA00753@kdat.calpoly.edu>
next in thread | previous in thread | raw e-mail | index | archive | help
>I'm curious as to whether FreeBSD's crypt has come under any scrutiny from
>the crypto community, and would perhaps like some justification for the
>choices in the hashing loop. It's very difficult when arbitrary choices are
>made in crypto to determine their validity or possible problems.
Well, let me tell you the story:
We couldn't use DES, since it couldn't be distributed abroad and
all that jazz.
Somebody, I can't remember who, (Nate Williams ?) made a replacement
that was kind of a hash. It was not very good. It was not at all
good. This is not meant to attack Nate, he didn't mean it to be
that good, he just didn't want clear-text passwords in /etc.
We had our 2.0 release comming up, and we had this sore thumb
popping up all the time, so finally I sat down and I wrote the md5
based one as a replacement.
Since the study of MD5 was and still is inconclusive, wrt to chaining
MD5's, I made up a sequence of actions (almost what you see in the
code now), that was based on a general theory of frustrating the
bits as much as possible.
In particular I tried a couple of places to do something that would
make the length of the input to the MD5 algorithm variable in
relation to the local context, in an attempt to frustrate HW assisted
attacks (which seems to have come quite in fashion with DES hackers
these days).
I timed it, found it to be pretty much fine, but way too fast, so
I added the second half of it, merely as something that will take
a lot of time to execure. the result being what we have today.
I then applied all the various kinds of analysis I could think of.
frequency, correlation, FFT and so on, on all bits of the output,
and on all combinations of two and three bits, and on the bytes.
I didn't find any correlations, (not that I expected to) that could
even come close to be called significant, so I was pretty happy
with the result.
(Later I even ran the stuff into a neural net, just to see if it
could find any patterns, I left a machine toying with this for about
a month. I got a very confused neural network as the only result.)
The most interesting three features from a security point of view
of this particular algorithm is the longer salt, longer output
string and longer runtime of the code. I would expect each of
these to contribute a factor of two to the security improvement
over the DES based stuff.
I have never, until now, heard from anybody who have even attempted
to analyse it. You are from all I know the first person to scrutinize
the code at all.
I must say though, I also don't think it is interesting to do so.
My attitude to the security of it is probably reflected by the fact
that I put a version number in the "salt". (``$1$'').
This is where I see the importance of my contribution. Not in
the inherent strength of the present code, but in the fact that
you can plug in a new algorithm almost on the fly.
(And I have actually already thought about it a couple of times
already. And on a couple of critical machines, I have even
installed a couple of slightly modified crypt() functions.)
Remember, passwords are as a rule both lousy >and< easy to change.
A new algorithm based on something else could be distributed,
peoples passwords expired and there you are: hole closed.
For a while at least. We will never get a password mechanism that
is resistant to attack. The best we can do is make it possible to
change it, in response to increasing pressure from the guys in
black hats.
The most common attack that I have seen is dictionary attacks.
The fact that the salt is bigger now, makes your precomputed
dictionary attack more bulky to deal with, that improves the odds
of "stupid" passwords a little bit.
Having said all that, I would like to thank you a lot for your
kind interest, and apologize for the slightly snappy answer
I sent you to your last email.
I would also kindly encourage your continued attention to the
subject if at all possible.
I'm actually very worried about the fact that nobody before you
have even asked me these questions, (I presume that MD5 crypt is
running on a lot of FreeBSD's out there, but I don't think we have
any idea of finding out how many), but there is of course the option
that people have looked at the source and decided that "it looked
ok and that we probably know what we're doing, so why even ask".
That would of course be even more disturbing from a security point
of view.
yours,
Poul-Henning
PS:
Here are some of the ideas that I have toyed with for future versions:
Move encryption into kernel. That way a system secrect
salt, or maybe even a hardware-contained salt could be used
that would be well protected from everybody. This would
mean that even if you discovered this salt, you would have
to make a dictionary for each of these salts.
Make a VERY slow crypt with very long output. Something
in the order of 10s of seconds on a P6/200. It is of
course annoying that things take that long, but dictionaries
would be practically impossible.
Make a public/private key version.
...
--
Poul-Henning Kamp | phk@FreeBSD.ORG FreeBSD Core-team.
http://www.freebsd.org/~phk | phk@login.dknet.dk Private mailbox.
whois: [PHK] | phk@ref.tfs.com TRW Financial Systems, Inc.
Future will arrive by its own means, progress not so.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?1430.838674512>