5

I was wondering if somebody could explain in detail, how chains work in rainbow tables as you would to a complete novice, but with relevance to programming.

I understand that a chain is 16 bytes long. 8 bytes mark the starting point and 8 mark the end. I also understand that in the filename we have the chain length i.e. 2400. Which means that between our starting point and end point in just 16 bytes we have 2400 possible clear texts, what? How does that work? In those 16 bytes how do I get my 2400 hashes and clear texts, or am I misunderstanding this?

Your help is greatly appreciated.

Thanks.

P.S.: I have read the related papers and googled this topic a fair bit. I think im just missing something important to make these gears turn.

James Moore
  • 253
  • 1
  • 6
  • 14
  • You want help cracking passwords? – bmargulies Apr 02 '10 at 22:22
  • no, i would like to understand how start and end points are used to generate clear texts and hashes. Adding I also understand how the 64-bit int gets converted to a string. Just wanted to understand where 2400 hashes come from. – James Moore Apr 02 '10 at 22:26

1 Answers1

3

Knowing the start point for a hash chain, you can compute all the intermediates and the end-point by repeatedly applying the hash-and-reduce function.

The end point comes in when you want to search the chain for a hashed password. Apply hash-and-reduce up to the chain-length number of times; at each stage, look to see if your intermediate matches the endpoint of any chain that you have computed. If so, then you've found the chain that includes the password. You then know where the chain starts because you've stored its start point, and so you can trivially walk forwards through the chain from there to find the password which, when hashed once, yields the hash value.

The full rainbow table process applies this sort of searching but with a family of different reduction functions to avoid hash collisions; I'm not well versed in the details.

crazyscot
  • 11,819
  • 2
  • 39
  • 40
  • Does this mean that hash is never calculated for the endpoint of the chain? My understanding is: as it ends the chain hash function is never applied to it, as on [illustration](https://upload.wikimedia.org/wikipedia/commons/thumb/7/78/Rainbow_table1.svg/1200px-Rainbow_table1.svg.png) from [Wikipedia article](https://en.wikipedia.org/wiki/Rainbow_table). Or I am missing something here? –  Nov 22 '17 at 07:24
  • Here is a good [answer on crypto.stackexchange](https://crypto.stackexchange.com/a/5901/53497), explaining how, exactly, chains are calculated. –  Nov 26 '17 at 12:59