作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2013, Vol. 39 ›› Issue (7): 156-160,164. doi: 10.3969/j.issn.1000-3428.2013.07.035

• 安全技术 • 上一篇    下一篇

基于归约函数数量裁减的彩虹表技术改进

王小鉴,廖晓峰,黄宏宇   

  1. (重庆大学计算机学院,重庆 400044)
  • 收稿日期:2012-08-22 出版日期:2013-07-15 发布日期:2013-07-12
  • 作者简介:王小鉴(1975-),男,硕士研究生,主研方向:信息安全,无线传感器网络;廖晓峰,教授、博士、博士生导师;黄宏宇,副教授、博士
  • 基金资助:
    国家自然科学基金资助项目(60973114, 61003247, 61170249)

Improvement of Rainbow Table Technology Based on Number Cutting of Reduction Function

WANG Xiao-jian, LIAO Xiao-feng, HUANG Hong-yu   

  1. (College of Computer Science, Chongqing University, Chongqing 400044, China)
  • Received:2012-08-22 Online:2013-07-15 Published:2013-07-12

摘要: 彩虹表技术是一种基于时空权衡策略的破解方法,但其破解速度受硬件性能和存储空间限制。针对该问题,提出一种通过适当减少归约函数数量并增加预计算时间来提高破解速度的改进算法。规约函数减少后,查表过程的搜索路径减少,计算负荷相应下降。通过增加预计算时间优化彩虹表结构并减少数据重复,从而提高破解成功率。实验结果表明,改进算法能够在彩虹表容量和硬件性能不变的情况下,节省30%以上的破解时间。

关键词: 彩虹表技术, 破解, 归约函数, 时空权衡策略, 误警, 完美彩虹表

Abstract: Rainbow table method is a time-memory trade-off approach for reversing one-way cryptographic functions. Its cracking time is restricted by hardware performance and storage space. In view of this issue, this paper proposes an updated method which cuts down the number of reduction functions and prolongs the precomputation time so as to shorten the cracking span. By decreasing the number of reduction functions, the amount of the search paths in the process of table look-up drops off and the computation amount decreases accordingly. The increase in precomputation time is used to optimize the table structure for reduction of duplicate data. The success rate of cracking can be ensured. Experimental results show that the work can save over 30% of the cracking time without enlarging storage space or upgrading hardware.

Key words: rainbow table technology, cracking, reduction function, time-memory trade-off strategy, false alarm, perfect rainbow table

中图分类号: