基于完美彩虹表的检查点算法改进研究

Improved Cryptanalysis on Checkpoints in Perfect Rainbow Table

本文对完美彩虹表下的检查点算法进行了研究和改进.时间存储折中攻击是由Hellman于1980年提出的一种适用于分组密码和哈希函数的算法.该算法具有可以用空间复杂度来换取时间复杂度的特点,然而由于链之间的碰撞,算法具有较高的误报率.其一个变种,Oechslin于2003年提出的彩虹表算法可以大幅减少碰撞的数量,从而提升效率.2005年,Avoine等人提出了另一种名为"检查点"的改进,该算法从另一个角度,即降低误报的影响来提升效率.然而,检查点的设置问题(数量和位置)仍未得到完全的解答.在本文中,我们对检查点算法在基于完美彩虹表的条件下进行研究,对检查点的设置进行理论分析,推导出最佳位置的计算式,并构造实验来检验最优选择的结果.在空间复杂度相当的条件下,相较于没有设置检查点的彩虹表,攻击时间可以减少10%到30%.

This paper improves checkpoints method in perfect rainbow tables. Time-memory tradeoff attack was introduced by Hellman in 1980, and it applies to cryptanalysis on block ciphers and hash functions. The time-memory trade-off attack can trade data memory for computation time,while the rate of false alarms remains at a high level because of collisions between chains. As one of its variants, rainbow table proposed by Oechslin in 2003 can make cryptanalysis more efficient by greatly reducing the number of colliding chains. In 2005, Avoine et al. proposed another improvement named"Checkpoints" from a different perspective, which can lower the influence of false alarms to improve efficiency. However, the problem of checkpoints setting(number and position) still has not been fully solved. This paper studies checkpoints in time-memory trade-off based on perfect rainbow tables,gives theoretical analysis of checkpoints setting, derives a formula of optimal positions and conducts experiments to examine the effect of optimal checkpoints selection. As a result, the cryptanalysis time can be reduced from 10% to 30% compared to rainbow tables without checkpoints under data memory of the same level.