Can DES-based hashed password be recovered if salt is known?

Question

Can a hashed password be recovered if the hashing is done with DES based crypt function in PHP and both the hash and salt are known by the attacker?

Consider the following example:

$salt = 'mysalt';
$pass = 'mypass';
$hashed_pass = crypt($pass, $salt);
// $hashed_pass = myDUAMR/WMo7.

I know that John the Ripper can break this, however it's not going to return the password, but instead it will return a string that can be used to create the same hash value. Can the real password be recovered in the given scenario?

Answer 1

John the Ripper works by trying out possible passwords, very quickly. It will not always break a DES-based crypt, or at least not easily.

With the DES-based hashing function, passwords may have up to 8 characters, and only 7 bits are used for each character (the upper bit is ignored). Considering that the password is typed at some point by a user on a keyboard, one can assume that there are 95 possible values for each character (ASCII characters from space [32] to tilde [127]), hence 6704780954517121 potential passwords (that's 1 + 95 + 95² + 95³ + ... + 95⁸). It is quite a lot; enumerating all possibilities on a PC will take at least a few weeks. But it is still technologically feasible.

DES is an encryption function, but the DES-based crypt is not DES; the internal function is altered (by the salt, namely), executed 25 times, and, more importantly, the roles of the key and the message are swapped. The end result is that the name "crypt" is improper (though traditional): this is no longer an encryption function; it should be called the "DES-based hash". What this means is that there could be (and indeed there are) two distinct passwords which hash to the same value (even if they use the same salt). For instance, this blog post shows that with the salt "hi", both "cqjmide" and "ifpqgio" hash to the same value "hiH9IOyyrrl4k" (the blog post claims this to be the first publicly known such collision, which shows how much the problem is interesting since it is not hard: these are 64-bit values, so the cost of finding a collision is about 2³² invocations of crypt(); that the first published collision appeared only in late 2010 just proves that nobody actually tried before that).

(Note: contrary to what the blog post says, the possibility of finding collisions has no influence whatsoever on the security of the password hashing system. The DES-based hash should not be used any longer not because of the ease of producing such collisions, but because it has too small input and output spaces, and is too fast.)

Consequently, from the salt and hash alone, there is no way to pinpoint "the" password, because the information is just not there. Through enumeration of all possible passwords, one can build the list of matching passwords, but there is no way of telling which is the one the user thought about. However, and that's the important point here, the machine which uses the result of the DES-based hash in a password verifying system cannot tell either: any password which matches the salt and hash value is a good password, as real as any other. If the salt and hash are "hiH9IOyyrrl4k", then both "cqjmide" and "ifpqgio" are accepted: even if you thought your password was "cqjmide", I can still log in under your name by using "ifpqgio" as password.

Note, though, that the vast majority of possible hash values have a single matching password, hence exhaustive search will find that password and none other.

On a similar note, since only the first eight characters are used, you could have a 40-character long password, out of which the last 32 characters will be totally ignored by the DES-based hash. There is no way to recover those from the hash value since they are simply dropped and have no influence whatsoever on the computed hash.

Answer 2

You cannot possibly compute all the collisions of a given password (using your hash algorithm), they are infinite. If John can give you a password that matches the hash digest, then you can theoretically recover the real password. But you cannot :

1. Ensure that a found match is the original password
2. Ensure you will find the original password (should it be known) in a decent time.

The best you can do to find the password would be to try a dictionary attack and making assumption the user used one word of this dictionary (or variations you are willing to compute). You are less likely to find two collisions from two distinct dictionary word. So this would give you a good certainty of having the original password. But of course this is only statistics.