From owner-freebsd-security Mon Jul 29 14:08:52 1996 Return-Path: owner-security Received: (from root@localhost) by freefall.freebsd.org (8.7.5/8.7.3) id OAA22852 for security-outgoing; Mon, 29 Jul 1996 14:08:52 -0700 (PDT) Received: from critter.tfs.com ([140.145.230.177]) by freefall.freebsd.org (8.7.5/8.7.3) with ESMTP id OAA22800; Mon, 29 Jul 1996 14:08:25 -0700 (PDT) Received: from critter.tfs.com (localhost.tfs.com [127.0.0.1]) by critter.tfs.com (8.7.5/8.7.3) with ESMTP id XAA01432; Mon, 29 Jul 1996 23:08:33 +0200 (MET DST) To: Nathan Lawson cc: freebsd-security@freebsd.org Subject: Re: Crack 4.1 patches for FBSD In-reply-to: Your message of "Mon, 29 Jul 1996 12:01:38 PDT." <199607291901.MAA00753@kdat.calpoly.edu> Date: Mon, 29 Jul 1996 23:08:32 +0200 Message-ID: <1430.838674512@critter.tfs.com> From: Poul-Henning Kamp Sender: owner-security@freebsd.org X-Loop: FreeBSD.org Precedence: bulk >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.