Cryptographic attacks | Hash based data structures | Search algorithms | Cryptographic hash functions
Rainbow table
A rainbow table is an efficient way to store data that has been computed in advance to facilitate cracking passwords. To protect stored passwords from compromise in case of a data breach, organizations avoid storing them directly, instead transforming them using a scrambling function – typically a cryptographic hash. One line of attack against this protection is to precompute the hashes of likely or possible passwords, and then store them in a dataset. However, such a dataset can become too big as the range of possible passwords grows. Rainbow tables address this problem by storing chains of possible passwords to save space. Undoing the chains takes significant computation time, but overall this tradeoff makes certain classes of attacks practical. Rainbow tables partition a function (the hash), whose domain is a set of values and whose codomain is a set of keys derived from those values, into chains such that each chain is an alternating sequence of values and keys, followed by a final value. Each item in the chain is derived from the previous item so that the chain may be algorithmically reproduced from the first value in the chain: A key derivation function produces a key from a preceding value, and a reduction function produces a value from a preceding key. The first value and last value of each chain are precomputed and stored, making the chain a row in a virtual table where each even-numbered field contains a value and each odd-numbered field contains the corresponding key. Such a table may be used to discover a secret value (password) given its associated key. It is a practical example of a space–time tradeoff, requiring less processing but using more storage than a brute-force attack which calculates a key on each iteration, but requiring more processing and less storage than a simple table. Use of a key derivation function that employs a salt makes rainbow tables infeasible for recovering a secret value from a key. Rainbow tables were invented by Philippe Oechslin as an application of an earlier, simpler algorithm by Martin Hellman. (Wikipedia).
