shep@mit-eddie.MIT.EDU (Tim Shepard) (07/31/86)
There is a flaw in the Berkeley 4.3 Unix passwd program that makes a
tape attack on a password feasible. (We haven't looked at any other
versions of Unix.) From passwd.c:
time(&salt);
salt = 9 * getpid();
saltc[0] = salt & 077;
saltc[1] = (salt>>6) & 077;
for (i = 0; i < 2; i++) {
c = saltc[i] + '.';
if (c > '9')
c += 7;
if (c > 'Z')
c += 6;
saltc[i] = c;
}
pw = crypt(pwbuf, saltc);
What does the salt depend on? Well, the paper on unix password
security by Morris and Thompson states that the choice of seed is based
upon the time of day clock and that there are 4096 different possible
seeds. (See "Password Security: A Case History" CACM, v 22, n 11,
November 1979, p. 594. That paper is often distributed with Unix
manuals.) On first glance at the above code, we were surprised to
find a call to getpid() in addition to the expected call to time(). A
close inspection of the first two lines of the above code reveals that
result of the call to time() is completely thrown out in the next line
of code. The salt depends only on the process ID number of the passwd
program!
But, lets go ahead and assume that a call to getpid() produces a
sufficiently random 16 bit number. What's the effect of multiplying
by 9? Well, since on the next two lines, only the low 12 bits of the
variable "seed" are used, the multiplying by 9 reduces the number of
possible seeds by a factor of nine. For example, after the second
line of code above, the variable "seed" could be 0, 9, 18, 27, etc,
but it could never be any value that is not a multiple of 9. Thus the
passwd program can only produce 4096/9 (= 456) of the 4096 possible
salt values. (It's amusing to note that without the second line, or
if the operator was "+=" instead of just "=" in the second line, the
code would generate all 4096 different seeds with about evenly
distributed probabilities.)
So what? Well, imagine taking a dictionary of 30,000 likely passwords
and producing 456 different files, one for each different salt, and
each containing 30,000 hashed passwords, each on a separate line, and
in the same order as the words in your dictionary. Each file would be
about 270 thousand bytes long (including line-feeds) and all the files
together could be kept on two 6250bpi tapes (which hold about 100
megabytes each). Now, to determine somebody's password from their
entry in the password file (assuming that their password is in your
original dictionary), position the appropriate tape at the start of
the file corresponding to the that user's salt and grep -n the tape
for the hashed password. (This will be vastly faster than 30,000
calls to crypt(), even the faster versions described in an earlier
message.)
If the salt could take on all 4096 possible values, you would need
instead need around 15 tapes to hold all the files.
All this underlies the importance of choosing a password which is not
in any dictionary and which is long enough.
Bob Baldwin
BALDWIN@XX.LCS.MIT.EDU
...!ihnp4!mit-eddie!baldwin
and
Tim Shepard
SHEP@XX.LCS.MIT.EDU
...!ihnp4!mit-eddie!shepshep@mit-eddie.MIT.EDU (Tim Shepard) (08/02/86)
The original message posted by Bob Baldwin and I contains an error. We forgot to take into account the fact that only the low 12 bits of the salt are used after the multiplication by 9. The effect of only using the low 12 bits effectively makes the salt equivalent to salt = (9 * getpid()) % 4096 which can take on 4096 different values since 9 is relatively prime to 4096 and assuming that getpid() will return any value. Tim Shepard SHEP@XX.LCS.MIT.EDU ...!ihnp4!mit-eddie!shep