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

于红波, 何 乐, 程子杰,2

1. 清华大学 计算机科学与技术系, 北京100084

2. 宾夕法尼亚州立大学 计算机科学系, 大学城, PA 16802

1 引言

哈希函数是一种可以将任意长度的私有数据映射为固定长度的哈希值的函数. 哈希函数在密码学领域中被广泛应用, 其中最为重要的应用场景之一就是口令认证. 为保障安全性, 哈希函数在设计上应具有单向性的特点: 即得到输入的哈希值十分容易, 而通过哈希值恢复对应的输入十分困难. 后者就是所谓的原像攻击, 在信息安全领域一直是一个热门的问题.

对于原像攻击, 最直接的解法就是穷举搜索. 假设目标哈希值的长度为n, 那么在期望上, 每2n次随机检索中就会出现一个对应的原像. 然而, 这种解法需要相当庞大的攻击时间以及计算能力. 为解决这一问题, Hellman[1]于1980 年提出了时间存储折中攻击方法, 该方法将预计算与穷举搜索相结合, 可以用额外的空间开销来换取攻击时间. 算法分为两个阶段: 预计算阶段和线上检索阶段. 在预计算阶段中, 攻击者进行大量的迭代计算以得到一系列的哈希链, 对每一条链仅仅保留链头和链尾两点, 舍弃所有中间节点(为节省空间). 当预计算工作结束后, 所得到结果即一张链表, 可以在多次检索中被重复利用. 对于一次线上检索(目标为分组密码的密钥或者哈希函数的原像), 攻击者只要完成相同的迭代操作, 直至目标与某一个链尾节点相匹配为止. 当二者匹配时, 攻击者就……