第一章 绪论
1.1 研究背景与意义
在互联网高速发展的今天，口令作为保护个人信息安全最主要的手段之一，具有重要的意义[1, 2]。然而，随着互联网信息的共享和传递越来越普及，口令受到的安全威胁也越来越严重。使用口令散列函数将口令映射为无法逆向推算的散列值，是保护口令的常用而且有效的方式[3]。但是，当用户忘记密码后，同样无法从加密后的口令中获得重要的信息。此时，需要对密文口令进行破解以恢复明文口令[4]。在另一方面，口令的破解是安全、情报、军事等部门获取各类情报的有效途径之一。例如，对口令脆弱性进行评估、破解犯罪通信加密文件等。因此，口令破解具有实际的应用场景和重要的意义。
口令破解最直接和最常用的方式是暴力破解，即尝试各种可能的字符组合，直到找出正确的口令。在实际应用中，通常使用两类方法提高暴力破解的实用价值。第一种方式是通过字典树、彩虹表等数据结构，提高暴力破解的效率[5, 6, 7]。这种方式预先将待枚举的明文进行加密，并把计算结果以线性表的形式存储起来。在后续的口令破解过程中，只需要对该线性表进行查找对比，从而避免加密的计算时耗。另一种方式则是基于口令的规律性，减少待尝试的明文口令数量，这种方式称为字典破解[4, 8]。在实际生活中，口令通常由有意义的字符串组成，例如姓名、生日、兴趣爱好等。通过对这些真实口令进行分析，可以从中提取出常见的热词结构。在进行口令破解时，优先根据频率最高的热词表达式生成待尝试的明文口令，能够极大地提高破解的准确率
................................
1.2 国内外研究现状
1.2.1 口令规律
早在 1979 年，Morris 和 Thompson 就发现用户喜欢根据自己的个人信息构造口令[11]。其后的研究表明，使用个人信息构建的口令中，生日的含有率最高，其次为用户名、姓名、电子邮箱前缀等[4, 8, 11]。在 2012 年以前，由于缺乏大规模的真实口令数据集，学术界普遍假设口令的分布是均匀的。但是，自从 2009 年第一个千万级口令集 Rockyou泄露以来，数以百计的知名网站被攻陷，为口令分布的研究提供了充足的原始数据[12]。为了验证口令是否和人类自然语言一样满足 Zipf 分布，Malone 和 Maher 在 2012 年分析了大量真实口令后，发现拟合出来的参数不能通过 Kolmogorov-Smirnov (KS)检验[13, 14]。同年，Bonneau 使用类似的方式对 Yahoo 的 7000 万条口令进行分析后，也否定了口令Zipf 分布的可能性[15]。而在 2014 年，Wang 等人根据大数定律，在去掉低频次口令、利用高频次口令进行 Zipf 分布拟合，通过了 KS 检验，证明了口令频次呈多项式下降，满足 Zipf 分布[16]。这一发现从根本上说明了漫步猜测攻击有效的原因，同时被广泛应用于多个场合，例如评估口令哈希函数的强健性、评估基因保护系统的抗攻击能力等[17, 18]。
1.2.2 口令破解
当前，主流的口令破解方法可以分为两类，即暴力破解和字典破解[19, 20]。暴力破解利用计算机强大的计算能力，尝试所有的口令组合。在这个过程中，由于缺少对口令规则的利用，往往无法在有限的时间和空间内成功破解。字典破解通过分析口令的特征和频次，构建一个能够覆盖尽可能多的真实口令的生成字典，从而提高破解的准确率。在2005 年，Narayanan 和 Shmatikov 通过对现有的口令字典攻击成功率分析后认为，字典攻击的命中分布与用户设置口令的倾向分布是正相关的，两者满足马尔科夫分布模型[21]。2014 年，Ma 等人首次将平滑技术和正规化技术运用到马尔科夫模型中，以消除数据集中过度拟合的问题[10]。基于概率上下文无关模型（PCFG）的口令生成，最早是由 Weir等人提出[22]。和马尔科夫模型一样，PCFG 也需要对口令集进行训练，只是 PCFG 引入了更多的规则使得口令生成的概率分布更加合理。在 2014 年，Veras 等人针对基于概率上下文无关模型和马尔可夫模型都没有利用口令中深层次语义信息的问题，在 PCFG 模型基础上提出了融合语义的 NLP 算法[23]。为了使口令生成具有定向性，Wang 等人在2016 年首次提出基于马尔科夫链的定向攻击猜测算法，将个人信息与马尔科夫结合[24]。同年，Li 等人利用攻击对象相关的个人信息，首次提出了基于 PCFG 的定向攻击猜测算法[25]。
第二章 相关知识与技术
2.1 ARMv8 架构
ARMv8 是 ARM 推出的支持 64 位指令集的处理器架构，同时向后兼容 ARMv7 架构。
如图 2-1 所示，ARMv8 引入了两种执行状态，分别是 AArch32 和 AArch64。AArch64执行状态针对 64 位处理技术，引入了一个全新的指令集 A64。在该执行状态下，系统的虚拟地址和通用寄存器都是 64 比特。AArch32 执行状态使用 32 比特的虚拟地址和通用寄存器，其主要目的是为了向后兼容已有的 ARM 指令集，即 A32 和 T32。除此之外，ARMv8 还进行了一些功能扩展，支持 TrustZone、虚拟化技术和 NEON Advanced SIMD技术[42, 43]
...........................
2.2 口令散列函数
口令散列函数是一种单向散列函数，可以将任意长度的二进制明文串映射为较短的固定长度的二进制串（消息摘要），并且不同的明文很难映射为相同的消息摘要，对应的模型为：h = H(M)。其中，M 是待处理的明文，可以是任意长度；H 是单向散列函数；h 是生成的固定长度的散列值，本文称为报文摘要，不同的散列函数生成的摘要长度不同。因为优秀的口令散列函数难以由一个已知的散列值，去推算出原始的明文信息，因此在信息安全中有许多重要的应用都使用了口令散列函数来实现，例如数字签名，消息认证码。本文主要以 MD5、SHA-1 加密算法为研究对象。
2.2.1 分组加密与明文扩展
现代密码体系对明文的加密过程都不以明文作为整体进行处理，而是将明文按一定大小进行分组，每次对明文的一个分组进行处理，常见的分组大小有 64 比特、128 比特等。在现代计算机体系结构中，通常把字节作为最小可寻址单位，而每个字节由 8 比特组成，因此将字节或者比特作为最小的可处理单元。当分组大小等于一个字节或者一个比特时，分组密码退化为流密码。流密码将明文作为字节流或者比特流，每次加密数据流的一个字节或者一个比特。本文主要研究和讨论分组密码。
.......................
3.1 批量分组加密 .............................................. 17
3.1.1 批量 MD5 加密 ..................................... 17
3.1.2 批量数据读写 ....................................... 18
第四章 高吞吐率的密文匹配 ......................................... 29
4.1 密文匹配过程 .......................................... 29
4.1.1 线程级并行 ................................. 30
4.1.2 原子位设置 ......................................... 30
第五章 实验结果与分析 ..................................... 40
5.1 实验平台与环境 ...................................... 40
5.2 散列加密测试 ............................................ 40
第五章 实验结果与分析
5.1 实验平台与环境
本章实验使用的服务器硬件信息如表 5-1 所示：
.........................
总结与展望
本文主要研究了在 ARMv8 架构上优化口令加密阶段中口令散列的计算，以及密文匹配阶段中布隆过滤器的构建和探寻过程。本文的主要工作及成果如下：
(1) 提出了口令散列函数的多种优化方案。对于口令散列加密计算，由于各轮逻辑运算之间具有很强的数据依赖，使其不能充分利用 NEON 指令集实现数据级并行。本文根据口令破解过程中需要加密大量明文口令的特性，以及现代处理器系统结构中的流水线原理，依次提出了三种优化方案，分别是：单批量加密、指令编排优化和多批量加密。此外，对于 SHA-1 加密，CRYPTO 提供了相应的硬件加速指令。本文在使用这些硬件加速指令的基础上，实现了吞吐率更高的批量 SHA-1 加密。与 OpenSSL 中的最优实现对比，本文提出的批量 MD5 加密吞吐率提高了 2.35 倍；批量 SHA-1 加密吞吐率提高了41.3%。
(2) 提出了针对布隆过滤器访存性能的多种优化方案。在布隆过滤器的构建阶段，使用简单的互斥锁机制并不利于线程扩展。本文基于 ARMv8 的独占访问机制，实现了原子位设置操作，避免了构建过程频繁的加锁/解锁操作。在此基础上，提出了缓存友好的分段布隆过滤器实现。通过将分段设为缓存行的大小，并结合数据预取进行优化，构建阶段的吞吐率提高了 1.1~4.1 倍、探寻阶段的吞吐率提高了 6%~102%。然后，利用软件缓冲机制，将访问同一分段的多个口令集中进行处理，优化访存性能。同时，结合分段布隆过滤器的设计优点，提出了两轮分段的优化实现。在本文的实验中，对不同大小的布隆过滤器，构建阶段的吞吐率能够提高 1.2 到 4.5 倍，探寻阶段能够提高 11%到105%。
参考文献（略）