密码口令破解彩虹表查找系统设计与实现

来源：核心期刊咨询网时间：12

摘要：摘 要：当前网络犯罪越来越严重，破解犯罪嫌疑人计算机中的的密码信息则需要技术支持。文章研究了彩虹表的构造原理、破解密码口令的过程，并结合MIC众核协处理器强大的计算能力，设计实现了密码口令破解彩虹表查找系统，并行化的设计提高了彩虹表的生成速度

　　摘 要：当前网络犯罪越来越严重，破解犯罪嫌疑人计算机中的的密码信息则需要技术支持。文章研究了彩虹表的构造原理、破解密码口令的过程，并结合MIC众核协处理器强大的计算能力，设计实现了密码口令破解彩虹表查找系统，并行化的设计提高了彩虹表的生成速度，归约函数的设计提高了明文查找成功率。

　　关键词：密码破解;彩虹表;众核协处理器;并行化

　　1 引言

　　哈希算法可以將任意长度的二进制值串通过一定的映射规则映射为固定长度的二进制值串。被广泛应用于密码学领域。对于一个优秀的哈希算法需要具备三个特点：(1)单向性—通过哈希值无法反向推到出原始数据;(2)对输入数据极其敏感—两个即使只有1bit差异的输入数据，其对应的散列值会有很大的不同;(3)碰撞几率极小—如果两个散列值不同，那么其对应的原始数据也是不相同的。哈希算法有非常多的应用，比如安全加密、唯一标识、数据校验、分布式存储等。

　　穷举法和查表法通常被用于破解哈希函数。穷举法，顾名思义，就是需要将所有可能的结果进行列举，具体地说，遍历明文空间，然后使用哈希算法求出明文空间中的每一个密码的哈希值，最后将哈希值与密文进行比对，其计算量非常大，破解密码口令的时间非常久。查表法是从预先保存好的明文组合与哈希值的映射中，通过密文查找对应的明文来破解密码口令。虽然查表法的破解速度高于穷举法，但其对存储空间的要求极大。结合穷举法和查表法存在的特点，Hellman[1]和Oechslin[2]等人提出了彩虹表(Rainbow Table)，这种方法既保证了密码口令的破解速度，又降低了存储空间，是一种实用且有效的技术。为有效且高效地破解密码口令，本文提出了彩虹表查找系统的设计与实现方案。

　　2 相关工作

　　Hellman于1980年首次提出了基于时空权衡(Time-Memory Trade-Off，TMTO)的表方法。这种方法分为两个阶段，即预计算阶段和在线阶段。为了建立密文空间与明文空间的映射，引入了可以用于交替地计算明文和密文的规约函数从而形成一个链表，链表的首节点和末尾节点被记录存储，而大量的首节点-末尾节点又组成了一张表，但由于规约函数与密文-明文映射非一一对应，会导致哈希碰撞问题的出现[1]。Rivest于1982年改进了Hellman的方法，为了降低链的重合率，他引入了区分点(Distinguished Points)[3]。Oechslin于2003年，在Hellman的方法的基础上提出了彩虹表(Rainbow Table)，他将Hellman方法中每次计算都使用相同的规约函数，改为每次计算时采用不同的规约函数，显著地降低了链的重合率[2]。2009年Thing在彩虹表的基础上，改进了TMTO方法，将存储首节点和末尾节点改为只存储末尾节点值，通过相应的数学运算来获得首节点，因此减少了表的存储空间[4]。2012年，梁艳等人提出了基于生成元的彩虹表，该方法根据常用的口令设置方法减少长口令的生成空间过滤掉不满足要求的口令，从而降低了表的存储空间[5]。2015年张悦等人设计了基于HBase的彩虹表MD5哈希密码解密系统，其引入Map/Reduce框架与HBase，为完成计算与存储，MD5彩虹表的生成和查找分配给集群节点，并使用HBase实现彩虹表的存储，明显地提高了彩虹表的生成速度和破解密码的效率[6]。2017年王伟兵等人在经典彩虹表的算法基础上，提出了构造分布式完美彩虹表的思路，通过MPI了并行编程接口，将彩虹表分布存储于集群中的每台计算机中。在破解阶段，通过集群中的多台计算机并行计算，可以明显地加快和提高密码破解的速度和有效率[7]。

　　3 彩虹表算法

　　彩虹表(Rainbow Table)技术可以理解成一种针对哈希算法的破解技术。其核心思想是按一定的规则将密文映射为明文空间中的口令，这个规则称之为归约函数()。

　　3.1 彩虹表的生成

　　在彩虹表的构造阶段，首先使用哈希算法将明文空间中的一个口令映射为密文，然后再使用规约函数，将密文映射为另一明文，使用哈希函数、规约函数依次迭代，得到，，，，…，，，，和分别是该条链的首节点和末尾节点，将这两个节点都存储下来。多条彩虹链构成了彩虹表：

　　推荐阅读：网络故障论文发表的核心期刊

转载请注明来自：http://www.qikan2017.com/lunwen/lig/18432.html