Re: Brute force against /etc/passwd?

Duane T Williams (duane@cmu.edu)
Tue, 17 Jun 1997 08:50:18 -0400


Seth D. Shoen wrote:
>In other words, how much longer does a crypt(3) take than a single encryption
>the DESCHALL client is doing now? My (Linux) man pages indicate that crypt(3)
>is a 56-bit DES hash, which would suggest to me that if 56-bit DES is broken,
>Unix password security is broken, too, and it's time for Unix in general to
>move to a much longer or slower hash.

The plain fact is that we do not need to carry out a project like DESCHALL
in order to know that a DES message can be broken by means of an exhaustive
search. We already know that. We also do not need to carry DESCHALL
through to completion to have a good estimate of how long such an
exhaustive search would take. (Rocke's most recent estimate of a probable
completion date is a little over a month from now.)

Finding the key to decrypt a single DES encrypted message obviously does
not mean that you have the key to every DES encrypted message. You have to
do the months of work all over again for each message you want to decrypt.
Finding the key to the DES challenge message also does not mean that you
can decrypt every DES message in the same amount of time. We searched 4.8%
of the key space in the past 7 days. At that rate it takes 146 days to
search the entire space and an average of 73 days to decrypt a message.
The time per key is going to vary randomly between 0 and 146 days with an
effort like the current DESCHALL effort.

Should our solving the DES challenge make me worry about my Unix password?
I don't think so. It is vastly more likely that a friend who knows me very
well will guess my password than it is that Rocke is going to be able to
persuade thousands of people to volunteer their computer time to illegally
break into my Unix account in a DESCHALL-like effort. Would Unix passwords
be greatly improved if they were based on an encryption algorithm that no
one could currently break? Most would not. I would still be able to guess
my friends and colleagues passwords just as easily as I do now.

The DESCHALL effort is giving us some real-world numbers to use in our
estimates of how fast a DES key can be found with various hardware. The
DESCHALL effort has motivated some people to greatly improve algorithms for
finding a DES key and they may even have some publishable results. The
DESCHALL effort is showing that thousands of volunteers can be persuaded to
cooperate in a large-scale internet-wide computing effort. (There are
other types of internet computing efforts with different motivations, e.g.,
the Mersenne prime search.) The DESCHALL effort may be useful in sending a
message to the public and to politicians about the level of security of
DES. But, we don't have to do something like DESCHALL to know that DES is
vulnerable to exhaustive search with existing hardware.

__________
-------------------------------------------------\ /
Duane Thomas Williams (mailto:duane+@cmu.edu) \ /
Carnegie Mellon University, DH 4307F, 412-268-7896 \ /
http://www.cs.cmu.edu/~dtw/ \ /
-----------------------------------------------------\/