3

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?

|improve this question
3

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...)

|improve this answer
  • 1
    +1 for the explanation on the rainbow colours. I found it very easy to understand your answer: the reason why I am selecting this answer is because of what you said: "Then, another candidate plaintext password is pulled out of that hash, and so on, creating a long chain". This reads to me as if the main reason for choosing the six number is because if you are trying to guess a six-character numeric-only password, the reduction offers a quick candidate at hand. Thanks so much. – Lex Dec 6 '13 at 21:07
5

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.

|improve this answer
  • I think you are correct until you say "bucket". That word implies that, like a Collections framework, search effort is reduced because the hashes are somehow organized into buckets and the process can narrow down which bucket to search in. I don't think this is how it works. In other words, there are no shortcuts that involve labeling buckets. Sorry if I misunderstand what you wrote. – mcgyver5 Dec 5 '13 at 17:09
  • @Stephane - thanks so much, it has helped filling in the gaps. – Lex Dec 6 '13 at 21:04
1

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.

|improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.