I am implementing an assignment where I'm given 1000 SHA1 digests and their corresponding passwords (each 24bit or 6Hex digits long). I have to build a rainbow table <2MB on disk and in Java, I see that having chain lengths > 192 makes the search process too slow.
The requirement is that this rainbow table should solve at least 45% (or 450) hashes and return the password. The Reduction function is simply - take the most significant 32 bits from the hash (lets say d0, d1, d2), add the current length of the chain (i goes from 0 to 191) only to d0 (like below), and then:
d0 = (d0+i)%256 //8bits
d1 = d1%256 //8bits
d2 = d2%256 //8bits
I am sure the code (hash and reduce) functions are correct. But I'm only able to solve about ~250 hashes (25% accuracy) to their corresponding passwords, this way.
If I increase the number of chains, I am seeing diminishing returns in the corresponding number of hashes solved. As in if I double the number of chains, the accuracy does not double, but the size of the rainbow table is already >2MB (its like 8MB).
For the starting words - I've tried just starting from 0 (the full range would be 0 to 2^24) and incrementing by one, or I've even tried making it random between this range. Rainbow tables have no loops and even though some collisions occur in the reduction function (at the same depth as reduction functions are different as described above), I'm not accepting chains where the endpoint is already in the table.
Would appreciate any advice on what I could do to increase the accuracy to 45%.