基于彩虹表的时间-存储折中攻击改进算法  

Faster Cryptanalytic Time-memory Trade-off Using Rainbow Table

作　　者：郑中翔 吉庆兵 于红波[1] 

机构地区：[1]清华大学计算机系密码理论与技术研究中心,北京100084 [2]保密通信重点实验室,成都610041

出　　处：《密码学报》2014年第1期100-110,共11页Journal of Cryptologic Research

基　　金：国家重点基础研究发展计划(973计划)(2013CB834205);国家自然科学基金(61133013;61373142);清华大学自主科研计划(20111080970);保密通信重点实验室基金项目(9140C110404110C1106)

摘　　要：杂凑函数是将任意长度的字符串映射到固定长度输出的函数,由于其具有单向性而被广泛的应用于口令认证.许多网站或服务器都使用杂凑函数来保存用户口令.时间-存储折中攻击是1980年由Martin Hellman提出的,它能够在有限的存储和计算能力的限制下,在可接受的时间内计算出常用的计算机口令.而Philippe Oechslin在2003年提出的彩虹表法极大地提升了时间-存储折中攻击的效率,此后在彩虹表法的基础上,大量改进算法被纷纷提出.本文提出了一种基于彩虹表的时间存储-折中攻击改进算法,它应用了概率统计的方法,能够在基本保证成功率的基础上大大提升搜索效率.即当成功率降低4.12%时,搜索时间降低86.21%,它是一种效率与成功率折中的算法.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.

关 键 词：时间-存储折中 彩虹表 LM-Hash NT-Hash 概率函数 

分 类 号：TN918.1[电子电信—通信与信息系统]