Faster Cryptanalytic Time-memory Trade-off Using Rainbow Table
ZHENG Zhong-Xiang1, JI Qing-Bing2, YU Hong-Bo1
1. Center for Cryptology Study, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
2. Science and Technology on Communication Security Laboratory, Chengdu 610041, China
Abstract：A cryptographic hash function is a function that takes an arbitrary-length data and returns a fixed-size digest. Hash functions are widely used in password authentication based on the one way property. Many websites or servers save user passwords using a hash function. Time-memory trade-off attack was presented by Martin Hellman in 1980. With limited storage and computing capacity, the attacker can get the passwords in an acceptable period of time. In 2003, Philippe Oechslin proposed a more efficient method by introducing a new table structure called rainbow table. Then, a number of improvements have been proposed based on rainbow table. In this paper, we propose a faster cryptanalytic time-memory trade-off using rainbow table based on probability statistics, which can greatly improve the searching efficiency with small losses of success rate. The searching time will be reduced 86.21% compared with the original algorithm when the success rate has a loss of 4.12%. The algorithm is a trade-off between efficiency and success rate.