2

To be sure I well understood the Rainbow Tables, I've decided to make a little project in Java, but I"m stuck on a question : how to choose the size of the chain ? And this will give the number of lines to get a good percentage of coverage

Imagine I use password size =6 and space 0123456789, the possibilities are 1 000 000 (size and space are low because it's easier to train on and debug, on a big space it would be harder, I wait to have something that work to try on bigger)

How do I choose between :

  • 4000 chains of size 250
  • 1000 chains of 1000
  • 400 chains of size 2500
  • ...

I'm using sha1 to hash, and to reduce I take the 6 first digits and add an index value (comes from the chain's loop) 

public static String reduce(String hash, BigInteger spaceSize, int passSize, int indexFunction) {
    int v = BigInteger.valueOf((Long.parseLong(hash.replaceAll("\\D", "").substring(0, passSize), 10) + indexFunction)).mod(spaceSize).intValueExact();
    DecimalFormat format = new DecimalFormat("000000");
    return format.format(v);
}
azro
  • 121
  • 3

2 Answers2

1

The choice of chain size,t, effects the storage size and look up time. At the and you have to calculate the 1000000 chain element.

  • 4000 chains of size 250; 8000 storage size of the hash result, sorting 4000 elements, lookup time at most 250 chain time and 250*log_2(4000) search time.
  • 1000 chains of size 1000; 2000 storage size of the hash result, sorting 1000 elements; lookup time at most 1000 chain time and 1000*log_2(1000) search time.
  • 400 chains of size 2500; 800 storage size of the hash result, sorting 400 elements; lookup time at most 2500 chain time and 2500*log_2(400) search time.

Use can use this site to calculate the parameters.

kelalaka
  • 5,474
  • 4
  • 24
  • 47
0

The chain length is basically time. A longer chain takes longer to compute. To recover a password when it was found in a chain, the chain length determines how many computations you have to perform to compute the original.

The chain count is basically coverage. If you have more chains, assuming all else stays equal, you have better coverage. You can also get better coverage using longer chains, though, but then you're increasing time.

For more information on rainbow tables, see this question: What are rainbow tables and how are they used? I think my answer on that page also answers your question about how to choose chain count and length, under the heading "Scaling properties".

Luc
  • 32,378
  • 8
  • 75
  • 137