DES密码算法的彩虹攻击技术及其GPU实现

摘要

以DES为代表的对称密码是信息安全领域一种重要的密码体制,与公钥密码相比,对称密码计算代价低,算法相对简单,因此在工业界得到了广泛的应用。目前,针对对称密码的攻击方法除穷尽搜索外,主要包括差分分析和线性分析。然而,由于实际中很难在相应密钥失效前,收集到大量的明-密文对,上述攻击极难在实际中得到应用。面对这些问题,学者们尝试各种方法。1980年,Hellman提出了著名的时空折中算法。从平均分析成本和现实可行性来看,时空折中比以往的方法有更大的威胁。2003年,Oechslin在原算法的基础上提出了彩虹表(Rainbow table)密钥分析算法,获得了更好的分析性能。但是由于受当前PC机计算能力所限,彩虹表算法针对多比特数密钥(如大于等于56比特)的分析时间,仍然很难满足现实的需求。基于以上问题,我们设计了一种在图形处理器(GPU)上的彩虹表(Rainbow table)密钥分析算法,主要是通过结合GPU单指令多线程的特点改进了Oechslin的彩虹表算法,将预处理中彩虹链的计算分别映射到GPU的单个线程,并发地完成彩虹表的生成；并首次引入了预计算链这种新的数据结构,显著地提高了在线分析的效率。所使用的硬件平台GPU Tesla C1060相对于CPU Core2 Duo 2.8GHz,在运行速度方面,预处理(Pre-computation)提高了41.2倍(110M次DES加密每秒),在线分析(Online Attack)提高了3.52倍。在此系统的基础上,用1.3GB的磁盘空间,平均2.73s的在线分析时间以及46%的概率,成功获得了加密选择明文的40比特DES密钥。为充分利用有限的内存空间,我们在GPU彩虹表算法的基础上,设计了一种新的彩虹表存储结构(简称瘦表),其原理是通过给每个EP增加一个ID的方式,使得SP能够在分析时生成,从而为每条彩虹链节约近(SP-ID)比特的空间。应用占位问题,我们进一步给出了较Hellman假警估算公式更为逼近的新方法,用于分析瘦表及相应单张彩虹表的假警增长趋势。实验表明,ID长度k取24比特长时,较单张彩虹表平均31%的成功率提高了14%,同时在假警数方面要比单纯地通过增加彩虹链长t的方法要低30%。

目录

摘要

ABSTRACT

第一章 绪论

1.1 研究背景

1.2 国内外研究进展

1.3 研究内容及主要成果

1.4 论文结构

第二章 时空折中方法

2.1 HELLMAN 时空折中算法

2.1.1 预计算

2.1.2 在线分析

2.1.3 TMTO 曲线

2.1.4 分析成功率

2.2 彩虹表算法

2.2.1 非完美彩虹表

2.2.2 完美彩虹表

2.3 统一折中方法

2.3.1 时空数据折中方法

2.3.2 时空密钥折中方法

2.4 本章小结

第三章 GPU 并行编程相关知识

3.1 GPU 并行编程概述

3.2 GPU 体系结构

3.2.1 线程模型

3.2.2 微架构

3.3 GPU 性能优化方法

3.3.1 硬件特性相关优化

3.3.2 软件特性相关优化

3.4 本章小结

第四章 彩虹表算法的GPU 优化设计与实现

4.1 GPU 彩虹表算法的设计

4.1.1 预计算

4.1.2 在线分析

4.2 彩虹表算法的GPU 优化

4.2.1 并发线程数

4.2.2 存储层次

4.2.3 优化的实验结果

4.3 DES 40 比特密钥分析实验

4.4 DES 56 比特密钥分析代价估计

4.5 本章小结

第五章 瘦表及其性能分析

5.1 瘦表生成算法

5.2 瘦表性能分析

5.2.1 在线搜索深度

5.2.2 存储空间

5.2.3 假警代价估计及分析

5.3 与等规模单表的性能比较实验

5.4 本章小结

第六章 全文总结

6.1 主要结论

6.2 研究展望

参考文献

致谢

攻读硕士学位期间已发表或录用的论文