基于Hadoop的扩展彩虹表生成研究

论文摘要

目前哈希函数已经被广泛应用于计算机科学的各个方面,哈希函数在各个主流的操作系统、通信协议的安全性方面均占据了重要的地位。对主流的哈希函数安全性的研究成为了密码学和信息安全领域的热门研究方向之一。在对哈希算法的原像攻击方面,除了暴力攻击以外,Oechslin提出的彩虹表是目前最为广泛使用同时也是具有最佳效果的一种攻击手段。彩虹表的基础是Hellman提出的时间与空间折中的方法,Oechslin等人对其不断进行改进,提出的彩虹表通过使用不同的Reduction函数,解决了经典表中链重合概率高等问题,能够在短时间内提供极高的破解成功率,成为了目前对哈希函数进行原像攻击的重要手段。本文首先对经典的攻击方式进行了研究,对Hellman的时间空间折中的方法和彩虹表的原理进行了比较分析,并且对现有彩虹表提出了两方面的改进：使用Hadoop和基于生成元的扩展。彩虹表的劣势之一在于支持巨大明文空间的彩虹表的生成时间在目前的硬件条件下是不可接受的。首先,本文提出了以Hadoop作为云计算的基础架构,使用MapReduce框架来进行彩虹表的生成和破解。通过实际搭建群集并且进行测试,得到了具体的性能比较数据。Hadoop平台能够有效地将计算负载分布到群集中的计算节点中,大幅度减少了生成任务的总耗时,并且通过利用HDFS分布式文件系统解决了大文件的存储问题。另外,本文从明文空间上对现有彩虹表进行改进,提出了一种基于生成元的扩展彩虹表,其基础是人为设置长口令过程中的一些普遍规律。扩展彩虹表将原有的明文字符集扩展为生成元(如英文单词、拼音等),并加以模式上的变换(如大小写变换等),核心为扩展R函数,能够将哈希值映射回特定的生成元空间。通过将扩展彩虹表和生成元字典共同存储,大幅度压缩了明文空间,为目前攻击人为长口令提供了一种新的方法。在Hadoop群集中进行三位拼音音节模式的生成与破解测试,成功率超过90%的扩展彩虹表生成时间控制在在3分钟以内,充分表明扩展彩虹表是一种能够支持长口令破解的有效手段。

论文目录

• 摘要
• ABSTRACT
• 第一章 序言
• 1.1 研究意义
• 1.2 国内外研究现状
• 1.3 论文结构
• 第二章 背景知识
• 2.1 哈希函数
• 2.1.1 哈希函数的定义和性质
• 2.1.2 常见的哈希函数
• 2.1.3 主流操作系统的口令加密存储
• 2.2 云计算与Hadoop简介
• 2.2.1 云计算的概念
• 2.2.2 Hadoop项目
• 2.3 本章小结
• 第三章 时空折中方法与彩虹表
• 3.1 时间空间折中方法
• 3.2 经典TMTO方法的发展
• 3.3 彩虹表的原理
• 3.4 完美表
• 3.4.1 完美表的意义
• 3.4.2 完美彩虹表的分析
• 3.5 本章小结
• 第四章 基于Hadoop的彩虹表生成
• 4.1 系统框架
• 4.2 系统具体实现
• 4.2.1 源代码结构
• 4.2.2 哈希算法支持
• 4.2.3 彩虹表生成
• 4.2.4 合并链的处理
• 4.2.5 彩虹表破解
• 4.2.6 MapReduce架构的彩虹表任务流程
• 4.3 实验过程
• 4.3.1 Hadoop群集的搭建
• 4.3.2 测试结果及分析
• 4.4 本章小结
• 第五章 基于生成元的扩展彩虹表
• 5.1 用户口令的研究
• 5.2 扩展彩虹表的设计
• 5.2.1 现有彩虹表的空间划分
• 5.2.2 基于生成元的空间划分方法
• 5.2.3 扩展R函数的设计
• 5.2.4 具体实现
• 5.5 参数与性能分析
• 5.5.1 压缩的明文空间
• 5.5.2 存储空间
• 5.5.3 空间压缩比
• 5.5.4 破解成功率
• 5.6 测试结果及分析
• 5.7 本章小结
• 第六章 总结与展望
• 6.1 全文总结
• 6.2 研究展望
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录