The LanMan disaster

By default Windows stores all users passwords with two different hashing algorithms. The historically weak LanMan hash and the more robust MD4. The LanMan hash is based on DES and has been described in Mudge's rant[1] on the topic. A brief recap of the LM hash is below, though those unfamilliar with LM will probably want to read[1].

First of all, Windows takes a password and makes sure it's 14 bytes long. If it's shorter than 14 bytes, the password is padded with null bytes. Brute forcing up to 14 characters can take a very long time, but two factors make this task way more easy. First, not only is the set of possible characters rather small, Microsoft further reduces it by making sure a password is stored all uppercase. That means "test" is the same as "Test" is the same as "tesT" is the same as...well...you get the idea. Second, the password is not really 14 bytes in size. Windows splits it up into two times 7 bytes. So instead of having to brute force up to 14 bytes, an attacker only has to break 7 bytes, twice. The difference is keyspace^14 versus (keyspace^7)*2. That's a huge difference.

Concerning the keyspace, this paper focuses on the alphanumerical set of characters only, but the entire possible set of valid characters is:

ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 %!@\#$%^&*()_-=+`~[]\{\}|\:;"'<>,.?/

The next problem with LM stems from the total lack of salting or cipher block chaining in the hashing process. To hash a password the first 7 bytes of it are transformed into an 8 byte odd parity DES key. This key is used to encrypt the 8 byte string "KGS!@#$%". Same thing happens with the second part of the password.

This lack of salting creates two interesting consequences. Obviously this means the password is always stored in the same way, and just begs for a typical lookup table attack. The other consequence is that it is easy to tell if a password is bigger than 7 bytes in size. If not, the last 7 bytes will all be null and will result in a constant DES hash of 0xAAD3B435B51404EE.

As I already pointed out, LM has been extensively documented. "L0phtcrack" and "John the Ripper" are both able brute force tools to break these hashes, and Philippe Oechslin of the ETH Zuerich was the first to precompute LM lookup tables that allow breaking these hashes in seconds[2].