Developing Rainbow Tables

Question

I am currently working on a parallel computing project where i am trying to crack passwords using rainbow tables.

The first step that i have thought of is to implement a very small version of it that cracks password of lengths 5 or 6 (only numeric passwords to begin with). To begin with, i have some questions with the configuration settings.

1 - What should be the size that i should start with. My first guess is, i will start with a table with 1000 Initial, Final pair. Is this is a good size to start with?

2- Number of chains - I really got no information online with what should be the size of a chain be

3 - Reduction function - If someone can give me any information about how should i go about building one.

Also, if anyone has any information or any example, it will be really helpful.

Answer 1

There is already a wealth of rainbow tables available online. Calculating rainbow tables simply moves the computation burden from when the attack is being run, to the pre-computation.

http://www.freerainbowtables.com/en/tables/

http://www.renderlab.net/projects/WPA-tables/

http://ophcrack.sourceforge.net/tables.php

http://www.codinghorror.com/blog/2007/09/rainbow-hash-cracking.html

Answer 2

It's a time-space tradeoff. The longer the chains are, the less of them you need, so the less space it'll take up, but the longer cracking each password will take.

So, the answer is always to build the biggest table you can in the space that you have available. This will determine your chain length and number of chains.

As for choosing the reduction function, it should be fast and behave pseudo-randomly. For your proposed plaintext set, you could just pick 20 bits from the hash and interpret them as a decimal number (choosing a different set of 20 bits at each step in the chain).