Getting a grip on better 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).

[ Roger Grimes's column is now a blog! Get the latest IT security news from the Security Adviser blog. ]

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.