11
$\begingroup$

I have read up on rainbow tables and think I understand the idea behind them. However, I find that it would be better for me to actually attempt to implement a (very basic) rainbow table generator in order to get a proper feel to using rainbow tables.

However, I face the problem of there not being descriptions on how to actually generate one. More specifically, I have found no descriptions on what reduction functions to use. Nor have I found out how many hashes a chain contains. Everything I have found has all been "hash then reduce" or "use OphCrack/RainbowCrack".

Is there information that takes me through the actual steps to generate chains and search through them? I want to learn how to make the tables, not how to use other peoples' programs.

Please do not link me to these websites:

http://kestas.kuliukas.com/RainbowTables/
http://project-rainbowcrack.com/tutorial.htm
http://www.ethicalhacker.net/content/view/94/24/
http://www.thetazzone.com/tutorial-rainbow-tables/
http://en.wikipedia.org/wiki/Rainbow_table
Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Most of the time I find it more worthwhile starting to implement something, creating a proof of concept, and then rewrite the thing completely to create a final version. Attempting to perfect it at once only works for relatively small problems fields that you already understand. $\endgroup$
    – Maarten Bodewes ♦
    Jan 5, 2013 at 18:50

1 Answer 1

Reset to default
10
$\begingroup$

Wikipedia shows you how to create a rainbow table.

The information you are looking for is under "Precomputed hash chains"

The reduction function tries to create a new input, the non hashed part which is the password in rainbow tables, from a hash. We want to choose a reduction function that will try to equally reduce the hash into new inputs such that it tries not to create the same input so many times.

Consider the following example. We want to create a rainbow table for all 5 character number combinations for the md5 function.

Lets start out with 12345 as the input. The md5 hash is 827ccb0eea8a706c4c34a16891f84e7b. The reduction function can be as simple as taking the first 5 numbers and using that as the next input. This method will produce reasonably distributed new inputs.

So the hash

"827 ccb 0 eea 8 a706c4c4a16891f84e7b" would create "82708"

The next hash would be 71b8e22700e63c2a0c1bad6506549d3b then would be reduced to 71822 accordingly.

So our current chain will consist of:

12345 -> 827ccb0eea8a706c4c34a16891f84e7b ->

82708 -> 71b8e22700e63c2a0c1bad6506549d3b ->

71822

The chain can go as long as you want, until it his a previous input, after which it enters a cycle - i.e. when it hits that point, it will just repeat itself and it will be useless.

Having a longer chain is going to reduce the space need to store these values but increase the time it needs to recalculate the entire chain.

All that would need to be stored would be the starting and ending point of the chain.

Given a hash, you use your same reduction function on it to get an input and repeats itself until that matches the end of a chain.

If it matches the end of a chain, you can just recalculate those values to determine which input it was.

NOTE: You want to make sure that you have every value from 00000 to 99999 in these chains, otherwise it will be incomplete.

If you need characters a to z instead of 0 - 9, you could just convert the hash to base 26.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ no... it says: The idea is to define a reduction function R that maps hash values back into values in P. any specific function R? Should I just use the ASCII version of a hash output and send it back into the hash? $\endgroup$
    – calccrypto
    Jan 4, 2013 at 4:22
  • $\begingroup$ @calccrypto I can revise my answer to better explain what are you looking for. What kind of language do you want me to provide a sample for? What hashes are looking to store? Do you want to optimize speed or space? Do you want me to explain the generation and look up process? Do you want to know how to use a reduction function?(Different question all together) $\endgroup$
    – ponsfonze
    Jan 4, 2013 at 23:56
  • $\begingroup$ @calccrypto Here is how a reduction function with a rainbow table works. stackoverflow.com/questions/5741247/… $\endgroup$
    – ponsfonze
    Jan 5, 2013 at 0:08
  • $\begingroup$ @ponsfonze I'm not looking for an explanation of what a reduction function is or does. I'm looking for a FUNCTION. I have no idea what a good choice a function (or multiple functions) for a rainbow function is. I will be using c++ or python $\endgroup$
    – calccrypto
    Jan 5, 2013 at 3:16
  • 1
    $\begingroup$ If you mean the first 5 nibbles of the hash function, then yes probably. "Real" rainbow table reduction functions are going to vary from program to program. You can try and look at the source code or the particular rainbow table generation or contact the developers ask them what they use. You're can't be 100% sure that the reduction function is going to generate all the values between 0 and 999999 unless you prove it. So if you dont have 11111 in a chain, you'll have to start a new chain. $\endgroup$
    – ponsfonze
    Jan 5, 2013 at 5:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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