Palisade Magazine

February 2006

Rainbow Cracking and Password Security

by Sam Varughese, CISSP, SCSA |  Discuss this article »»

Passwords are often stored hashed on the premise that significant time is required to brute force a hashed password. The value of password hashes, however, has been undermined by the Rainbow Cracking attack. Rainbow tables readily available today reduce the time required for cracking hashed passwords to minutes. This article presents this recent attack on password hashes.

Password Hashes 101

Let us look at how hashing works before we get to the details of the attack itself. Hashing is a cryptographic technique: a mathematical function takes a text input and convert that to a fixed size output - usually 128, 192, or 256 bits.

Rainbow Table Hashes

Fig.1 Hashing of Passwords

A good hash function has two important properties:

  1. It should be computationally infeasible to determine the input from the hash output
  2. It should be extremely difficult to find another input that produces the same hash output.

In a brute force attack, the attacker tries all password combinations as input and compares the output with the hash stored in the database to get a match. Password hashes are considered secure when it is not feasible to brute force the password in reasonable time.

The strength of the passwords is a function of the length of the password and its character set. The total number of combination is C^L where C is the possible characters that can be used, and L is the length of the password. It takes hundreds of years to brute force a password of eight characters with a character set of upper, lower, numerals and special characters1 – this after considering machines that are hundreds of times faster than the ones we have today. That thought provided us assurance that even if the password hash was compromised, it wasn’t too much of a threat.

Time Memory Trade Off - Tilting the Balance

Enter Time Memory Trade Off attacks. Time memory trade off (TMTO) techniques use pre-computed databases to reduce the time required to do the brute force attack. For example, generate hashes of all possible passwords and store them sorted in a database. Once the database is created - probably taking a few years with parallel computers - an attacker can just lookup the database and find the password. There is a problem, however. The database would be hundreds of gigabytes to do this simplistic pre-computed attack. Thus this is not very realistic.

That was the case until recent optimizations enabled the attack to be conducted by reducing the memory requirements. Hellman2 first came out with a method that reduced the time and memory requirement. Philippe Oechslin3 then optimized the methodology to further decrease the computation and memory requirements. The exact math is beyond the scope of this article – we’ll look at the essential concept.

A rainbow table stores a fraction of the total numbers of hashes. The keys are organized in chains where only the first and the last element of the chain are stored in the table. A word is selected and hashed; the result is “reduced” so that it represents another possible password by converting each character into a printable ASCII character. The reduced word is hashed again. And the process is repeated over a few thousand times. The final value is stored in the second column of the table against the first word. None of the intermediate hashes are stored. The storage requirement is thus reduced heavily. A large number of such rows are pre-computed and stored in a database: these are called “rainbow chains”.

To obtain the password from the hash, the hash is looked up in the second column of the rainbow table. If no match is found, the hash is reduced and hashed. The resulting hash is again looked up in the second column of the table. This is repeated until a lookup succeeds. Once a match is obtained, it means the password is present somewhere in that chain. The chain is then recomputed forwards from the word in the first column to obtain the password.

This method is probabilistic and it is possible that a specific password is not in any of the chains. The technique has been successfully applied to popular hashing algorithms, including SHA1 and MD5.

Protecting against Rainbow Cracking

The solution to rainbow cracking is quite simple – salt the hashes. A salt is a non-secret, random piece of data that is provided to the hashing function. A different salt creates a different hash. When a large set of salts are used, rainbow cracking fails.
The salt need not be kept a secret: it should be stored along with the userid so that the hash value can be recreated during authentication.

This solution, interestingly, is not a new one: it is used in most UNIX platforms. Thus most rainbow cracking attacks are effective only against Windows systems.

Applications require only incremental changes to protect against rainbow cracking. Instead of just hashing the password, a random salt needs to be used for every user during hashing.  The process of using salting for web application is explained in the article “Salted Hashing Demystified”, available on OWASP.
What about applications that were already using random salts to hash passwords during transmission? Well, they now need to apply a per-user salt.

Otherwise, all other password protection principles remain the same: longer, more complex passwords, strong password policies and user awareness are cornerstones of safeguarding passwords.


Discussion is open for this article — there are no reader comments yet. Add yours.