Gourt Home::Gourt :: Rainbow table
A rainbow table is a special type of lookup table offering a time-memory tradeoff used in recovering the plaintext password from a ciphertext generated by a one-way hash. A common application is to make brute force attacks against hashed passwords more feasible.
A rainbow table is constructed by building chains of possible plaintext passwords. Each chain is developed by starting with a randomly selected "guess" of the plaintext password and then successively applying the one-way hash followed by a reduction function. The reduction function takes the results of the hash-function and turns it into another plaintext password guess. The intermediate password guesses are then discarded and the first and last are stored in the rainbow table. This table takes time and memory to build, but must only be built once at which point, it can then very quickly recover unknown passwords.
Recovery of plaintext passwords is then done by taking the hash password, applying the reduction function, and looking-up the result in the rainbow table. If no match is found, then the hash and reduction functions are applied again and that result is then looked-up. This is repeated until a match is found. Once a match is found, the chain that resulted in the match is reconstructed to find the previously discarded intermediate value, which is then a plaintext password for the given hash.
The end result is a table that contains statistically high chance of revealing a password within a short period of time, generally less than a minute. The success probability of the table depends on the parameters used to generate it. These include the character set used, password length, chain length, and table count.
Success probability is defined as the probability that the plaintext can be found for a given ciphertext. In the case of passwords, the password is the plaintext, and the hash of the password is the ciphertext, so the success probability is the probability that the original password can be recovered from the password hash.
Tables are specific to the hash function they were created for e.g., MD5 tables can only crack MD5 hashes. The theory of this technique was first pioneered by Philippe Oechslin as a fast form of time-memory tradeoff [http://lasecwww.epfl.ch/~oechslin/publications/crypto03.pdf (PDF), which he implemented in the Windows password cracker Ophcrack. The more powerful RainbowCrack program was later developed that can generate and use rainbow tables for a variety of character sets and hashing algorithms, including LM hash, MD5, SHA1, etc.
Defense against rainbow tables
A rainbow table is ineffective against one-way hashes that include salts. For example, consider a password hash that is generated using the following function (where "+" is the concatenation operator):
hash = MD5(password + salt)
To recover the password, a password cracker would have to generate every possible salt for every possible password — a rainbow table would not necessarily give any benefit.
Salts will, in effect, extend the length and potentially the complexity of the password. If the rainbow tables do not have passwords the length (e.g. 8 bytes password, and 2 bytes salt, is effectively a 10 byte password.) and complexity (if the salts aren't alphanumeric, but the database only has alphanumeric passwords) then it will not be found. If found, one will have to remove the salt from the password before it could be used.
Common uses
Nearly all distributions and variations of Unix, Linux, and BSD use hashes with salts, though many PHP web applications use just a hash (typically MD5) with no salt. The Windows NT/2000 family uses the LAN Manager and NT LAN Manager hashing method and is also unsalted, which make it one of the more popularly generated tables.
External links
- Ophcrack page by Philippe Oechslin The original rainbow table research with online demo
- Project RainbowCrack
- oxit.id Contains winrtgen, a GUI for rtgen
- rainbowcrack.com Community-based distributed rainbow table generation
- Large rainbow tables from the Shmoo Group, creators of AirSnort
"Rainbow table"