Rainbow Tables: What is the Reduction Used for?

Question

This is a follow up from this answer.

The answer is very good, and it put me to thinking and doing some research. I have found another good explanation on this site.

At some point, the author says:

If the set of plaintexts is [0123456789]{6} (we want a rainbow table of all numeric passwords of length 6), and the hashing function is MD5(), a hash of a plaintext might be MD5("493823") -> "222f00dc4b7f9131c89cff641d1a8c50". In this case the reduction function R() might be as simple as taking the first six numbers from the hash; R("222f00dc4b7f9131c89cff641d1a8c50") -> "222004". We now have generated another plaintext from the hash of the previous plaintext, this is the purpose of the reduction function.

However, I don't seem to have grasped the use of the reduction as it seems pretty arbitrary. How does reducing a hash to its first numbers help retrieving the plaintext. Is the choosing of the reduction (that is selecting the first few number of the hash) really arbitrary? Could I instead of taking the first six numbers use, say, the last six numbers?

Answer 1

The reduction function helps by storing more plaintext candidates inside the hashes themselves. The article gives a really simple reduction example: taking the first six numbers of your hash "222f00dc4b7f9131c89cff641d1a8c50". The result of the reduction is another possible six digit password (222004) which is hashed. Then, another candidate plaintext password is pulled out of that hash, and so on, creating a long chain. The rainbow table stores only the end of that long chain. It doesn't need to store all the hashes because it can pull each hash back out of the reduction function as it travels back up the chain.

when you give it a hash you want cracked, it first looks in the first set of hashes it has stored (which are the end result of this long chain). If by chance the hash is there, it returns the plaintext and exits. Otherwise, it goes up one step in the chain and checks that hash against the one you provided. and so on.

At first I thought that some kind of bucket operation was at work, that reduced the number of places required to look for the hash, but I don't think the chain gives any hints about where to start based on the original hash. It simply is trading memory intesive work for a reduction in storage requirements.

As the article says, there is no guarantee that every plaintext will have a corresponding hash in this scheme. Rainbow tables get as many as possible by changing the reduction function in each column (that is why they are called rainbow tables, each column is imagined to have a different color...)

Answer 2

It's a way of making a compromise between storage and computational requirement.

It's an implementation of a hash table: instead of storing all possible unique values in the table (which will result in real problem for storing indexing and searching the result), you simply reduce the number of computation needed to find a valid hash.

Basically, when you build the rainbow table, you create a hash (here called a reduction function because it reduces the size of the key space) of the result for each entry you try. You then store the original value in a bucket that is labeled with the result of the reduce function.

When you use the rainbow table, you do the following: you take the hash value you want to reverse, pass it trough the reduce function and look what inside the bucket that has that tag: you then try to hash each of the elements in that bucket and see if it matches your original value.

As to how to pick a proper reduce function, you will want one that will let you regroup all the data you see in manageable chunks: you don't want to have just a few large buckets or too many small ones. That's where a balance must be found. Other than this, exactly how you select that reduce function is not really important: you should try to use something easy to compute, that will split your data in statistically equal buckets and that will be easy to handle for your environment so, if you'd rather pick the last 6 numbers instead of the 6 first, it wouldn't matter in the end.

Answer 3

There is a very good tutorial that illustrates on how rainbow table works here: https://www.youtube.com/watch?v=rv06bwwAQqM

A reduction table is a table that maps from hashcode to plaintext. An example would be taking the first 6 digits of hashcode (e.g., 134503 from hashcode abcd13450d3...).

The reduction function will try to distribute to the plaintext equally, and try not resulted in many hashcodes maps to a plaintext. That will result in collision as described in the video.

When a reduction and hash function intertwined, it allows to form a long chain that maps between the domain of hashcode and plaintext repeatedly.