Handling password hashes

Many of today's computer passwords are stored and transmitted in a cryptographic hashed form. A strong password hash algorithm ensures that if the password hash is obtained by unauthorized parties that it is non-trivial to convert the hash back to the original plain text password (assuming the password is not trivial to guess at in the first place).

Microsoft Windows has two types of password hashes: LM (LAN Manager) and the newer NT (or NTLM) hashes. When you type in a Windows logon password for the first time, the password is stored twice by default in the authentication database (local security accounts manager file or Active Directory database) -- once for each type of hash.

In Windows, LM hashes are weak and much easier to crack than the NT hash. Other platforms have the same sort of problem; earlier, weaker password hashes are now superseded by stronger hashes. Linux, Unix, and BSD use various password hash algorithms, including weak crypt, stronger MD-5 style encryption, and the strongest, known as Bcrypt.

Passwords can be compromised in many ways, including social engineering, key logging, guessing, and cracking. Cracking implies that the password hacker was able to obtain the password's hash value. In the old days, the password cracker would run a program that would consider every possible likely password, hash it, and compare it against the stolen hash. This type of attack is fairly successful for passwords up to about six characters long. Beyond that, the passwords begin to take too long to crack using traditional methods.

Enter the rainbow table . Rainbow tables are closely related to a cracking technique pioneered by Philippe Oechslin. Essentially, the captured password hash is mathematically converted into an intermediate form. From there, you can generate large tables (called rainbow tables) containing hash values that represent a likely subset of all possible passwords the cracker wants to use.

The captured password hash's intermediate form is compared to the values stored in (or calculated from) the rainbow table. The intermediate forms and new comparison technique allow password crackers to crack larger or more complex passwords in a much shorter period of time than they could by using traditional methods.

The key to rainbow table cracking is to use a program that implements the newer cracking techniques, and to have a large precomputed rainbow table containing all the possible password values needed for the comparison. Oh, yeah, and it takes lots of memory and CPU power.

The best password rainbow table would include all possible passwords and their hashes. With enough hard drive space, memory, and time, no password hash would be safe. But in real life, complete rainbow tables are infeasible.

For example, Windows log-on passwords can be as long as 127 characters and be comprised of 65,000 (minus a few dozen) Unicode characters. There is absolutely no way to make a rainbow table that contains all the possible passwords that large a dataset would need to contain. I don't have the real numbers available to me at the moment, but it's easy to say that the resulting database would take billions of years to calculate and take more hard drive space and memory than is available in the world now or in the next 100 years.

Instead, today's rainbow tables are made up of the most popular types of passwords. In Windows, most passwords are one to eight characters long and made up of lowercase letters. Many password hash tables go further to "capture" more passwords and contain all the uppercase and lowercase letters, plus numbers (0-9) and other keyboard symbols.

Windows LM hashes are limited to a maximum length of seven characters, and all characters are uppercase (because LM is not a good hash). Hence, the Internet is full of free, downloadable LM password hash tables capable of cracking most Windows passwords, if the attacker can get the LM hash.

But more and more often, Windows administrators are disabling the LM hashes to prevent password hash cracking. And LM hashes are disabled by default in Windows Vista, leaving only the much harder to crack NT password hashes. Couple that with longer and more complex passwords, and yesterday's LM rainbow tables just aren't up to snuff anymore.

Page Break

If you want to stay up on password cracking (for auditing purposes), you need to get your hands on some very large NT password hash tables. We're talking multigigabyte tables, sometimes hundreds of gigabytes. The problem is that generating large NT rainbow tables is beyond the scale of a single computer, or even a hundred computers.

Enter the Free Rainbow Table's new distributed client. Download and install it, and your computer(s) become part of a large distributed computing project to generate larger rainbow tables. There are clients for Windows, Linux, and FreeBSD for now. Windows is the only GUI client, and you will need the latest Microsoft .Net Framework [client] installed beforehand.

Everyone's effort will be collected together into free, downloadable large rainbow tables, representing LM and MD-5 passwords. MD-5 hashes are useful for auditing many other Linux-based security appliances and distributions.

If you are a Windows or security administrator, you can (and should) use rainbow tables to find and eliminate weak passwords in your environment. Me, I love the idea of distributing computing. I've been a SETI@home participant for years. I don't really believe we will find aliens using it, but I love the idea of being involved in something bigger than myself. And what's a few billion extra CPU cycles that I'm not using?

I also participate in some of the distributed crypto challenges, trying to break small key sizes. Now, I'm adding another distributed computing project to my computers with Free Rainbow Tables. Wonder how they will compete with each other for CPU cycles?