基于高效彩虹表存储的快速时空折中攻击.pdfVIP

计算机研究与发展 ISSN 1000-1239/CN 11-1777/TP Journal of Computer Research and Development 基于高效彩虹表存储的快速时空折中攻击 顾纯祥，祝跃飞，郑永辉，李峥 (信息工程大学 河南郑州 450002) (gcxiang5209@) 摘要 自从Oechslin提出彩虹表，时空折中方法已成为实现密码攻击的最常用方法之一。论文在彩虹表技术基础上，提出一种新 的预计算表计算方法和存储结构。将该方法用于攻击95个全可打印字符表上、最大口令长度为8的口令，和彩虹表方法相比，存 储空间中的记录数增加了约70% ，从而使得在存储和计算复杂度相同的条件下，论文方法的成功概率提高了7.8% ～15.6% （针对 不同的链长）。该方法还可进一步与Checkpoints方法相结合，从而使在线分析阶段的计算代价降低10% ～20% 。 关键词 时空折中；彩虹表；密码分析；口令破解 中图法分类号 TP309 An Efficient Rainbow Table Structure and Faster Cryptanalytic Time-Memory Trad-off Attack Gu Chunxiang, Zhu Yuefei，Zheng Yonghui ，Li Zheng (Information Engineering University, Zhengzhou 450002, China) Abstract Since Oechslin suggested the so-called rainbow tables, the time-memory trade-off attack has become an efficient and effective method for cryptanalytic attack. In this paper, we propose a new method which uses a novel design of pre-computed table structure. We apply the method on the example of 8-character possible password composed from a character set of 95 different typeable characters. Compared with the rainbow method, the number of records stored in the storage can increase with about 70% in our example, 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 are to remain the same. What’s more, our method can further use Checkpoints technique to reduce the complexity of on-line computation by 15%~20%. Keywords time-memory trade-off; rainbow table; cryptanalysis; password recovery 穷举有哪些信誉好的足球投注网站密钥空间实现对密码的暴力破解是密 算法。 码分析最有效方法之一。为了使破解的时间复杂度 自Hellman 的工作之后，学术界对该方法进行 和空间复杂度都保持在实际应用可以接受的范围 了一系列的优化改进[2-7]，2003 年 Oechslin[4]提出 内，1980 年 Hellman[1]提出了时空折中方法，并将 一种快速的时空折中方法并