SHA-3标准Keccak算法的安全性分析与实现

摘要

Hash函数作为现代密码学的重要分支，被广泛应用于密码技术中的消息完整性检验、数字签名和鉴别协议等中，其安全性会直接影响到加密认证和通信网络的安全性，并成为许多密码体制和密码协议安全的前提条件。
　　Hash函数的安全性质主要体现在碰撞抵抗、原象抵抗和第二原象抵抗这三个方面。由于近年来对传统常用 Hash函数如 MDx、SHA等出现大量有效的分析方法，美国国家标准和技术研究所（NIST）于2007年发起了新Hash函数标准的征集活动。经过3轮评选过程，Keccak算法最终于2012年10月在评选中获胜并成为新的Hash函数标准SHA-3。Keccak采用不同于传统MD结构的新型海绵结构，具有可证明的良好安全性与实现性能。目前针对缩减轮数Keccak的攻击是当前对于Keccak算法的一个热点研究方向。而已知的对于Keccak算法的实际碰撞也仅限于很低轮数的攻击。
　　本文内容主要分为两个部分：第一部分首先介绍了密码学Hash函数的概念、结构与基本攻击方法，并重点介绍了针对迭代型分组密码的差分分析法。然后在对SHA-3迭代函数置换性质研究的基础上，提出从 Keccak算法本身的统计特性和Keccak算法所采用海绵结构中轮函数的对称性两个方面来对算法进行安全性分析。分析测试结果表明，Keccak算法具的良好的雪崩性能和抗统计攻击的能力。同时由于?运算的引入，使得算法在轮数较高时抵抗内部差分攻击的性能非常优异。最后对Keccak算法进行了软件设计实现，并分析了其在通用PC平台上的软件实现性能，结果表明Keccak算法具有与SHA-2相近的实现性能，能够高效地用于各类应用中。
　　论文的第二部分，在 Naya-Plasencia等人对缩减轮数的 Keccak算法研究的基础上，给出了一种改进的缩减轮数Keccak算法的实际攻击方法。从已知的2轮和3轮低汉明重量的差分特征出发，先进行后向扩展一轮差分特征并保持其高概率。然后再利用目标差分算法额外扩展一轮。并结合差分分析与代数分析技术，成功地在一台PC机上实现了针对4轮Keccak算法的碰撞攻击，以及5轮Keccak算法近似碰撞攻击。这是一种可以实际实现的针对缩减轮数Keccak算法的攻击方法。当尝试对更高轮数的算法进行攻击时，由于差分路径的比特扩散急剧升高，导致其概率迅速下降，使得碰撞的寻找非常困难，从而体现出Keccak算法的核心安全性在较高轮数的状态下并未受到威胁，其安全性目前来说十分可靠。

目录

声明

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1.1 Hash函数的历史与发展

1.2 Keccak算法的安全性与攻击现状

1.3论文的研究内容与主要工作

第二章 密码学Hash函数与差分分析法

2.1 Hash函数相关定义

2.2 Hash函数基本结构简介

2.3 Hash函数的基本攻击方法

2.4差分分析法

2.5本章小结

第三章 SHA-3的安全性分析与软件设计

3.1 SHA-3迭代函数及其性质

3.2 SHA-3函数族与填充规则

3.3 SHA-3的安全性分析

3.4 SHA-3的软件设计及实现性能分析

3.5本章小结

第四章 缩减轮数Keccak算法的攻击

4.1低汉明重量差分特征的搜索

4.2对Keccak算法差分路径进行扩展

4.3目标差分算法的实现

4.4对缩减轮数Keccak应用目标差分算法

4.5本章小结

第五章 结束语

5.1全文总结

5.2不足与展望

参考文献

致谢

作者简介