An Efficient Rainbow Table Structure and Faster Cryptanalytic Time-Memory Trad-off Attack

The time-memory trade-off algorithm is a method for quickly inverting a one-way function using pre-computed tables. Since its first introduction by Hellman, many variants and their analysis results have appeared. Oechslin suggested the so-called rainbow tables which made the method efficient and effective for cryptanalytic attacks. The Checkpoints method is a technique that reduces the number of table lookups performed by the algorithm. In this paper, we propose a new method using a novel design of pre-computed table structure. Compared with the rainbow method, the new design achieves distinct reduction in term of the storage requirement. We apply the method on the example of 8-character possible password composed from a character set of 95 different typeable characters. The number of records stored in the storage can increase with about 70% in our example compared with the rainbow method, which also leads to the increase of 7.8% to 15.6% (for different chain lengths) in terms of the success rate of attack if the storage requirement and the computational complexity remain the same. What’s more, our method can further use Checkpoints technique to reduce the complexity of on line computation with 15% to 20% by setting a checkpoint in the middle position of the chain.