漫谈SHA-3函数

摘

要

       用于生成数据指纹的哈希函数（又称Hash函数、杂凑函数、散列函数等）已经应用于经济生活的各个领域，时时刻刻保护着大家的数据安全。SHA-3（Keccak）是美国标准技术研究院确认的第三代哈希函数标准，是将来若干年内最重要的哈希函数。本文就来介绍一下SHA-3函数的前世今生，及其最新的研究进展。

哈希函数——生成消息的“指纹”

“用你的放大镜看看吧，福尔摩斯先生。”

“我正用放大镜看着呢。”

“你知道大拇指的指纹没有两个同样的。”

“我听说过类似这样的话。”

“那好，请你把墙上的指纹和今天早上我命令从麦克法兰的右手大拇指上去来的蜡指纹比一比吧。”

——柯南道尔《诺伍德的建筑师》

雷斯垂德警官与夏洛克福尔摩斯的一段对话

《神探夏洛克》剧照

不管在文艺作品还是现实生活中，比对指纹都是判断人物与犯罪现场是否有关联的重要手段之一。同样地，对应于计算机系统中的消息，也可以通过对比“指纹”的方式判断两个消息是否一致。尤其是当两个消息文件非常巨大时，对文件本身进行保存、拷贝和对比操作都将会变得十分耗时，从效率的角度考虑，会避免直接比较文件的内容，而是选择对较短的“指纹”进行比对。此外，如果一个消息被修改，即使只有1 比特是不同的，那么这两个消息的“指纹”都会呈现天壤之别。因此，可以通过比对“指纹”来判断消息文件是否被篡改过。消息的“指纹”，就是单向散列函数。

Hash原意为打碎

单向散列函数，也称为哈希（Hash）函数或者杂凑函数。Hash一词源于法语，在中文中直接音译为哈希。在法语中，steak hashé就是打碎混合好的牛肉饼的意思。去肉店买肉也会有师傅问，是否要hasher（要不要打碎）。相同的含义体现在计算机中，就是把输入的消息文件，打的越碎越好。这里输入的消息，可以是图像、声音、文字等各种形式，单向散列函数不需要知道这些消息的含义，而是把它们作为单纯的比特序列来处理，通过多次复杂的混合扩散操作，计算出相应的散列值（Hash Value）。散列值的长度和消息无关，而是由具体的单向散列函数算法所决定。和实际的打碎过程一样，针对消息文件的Hash过程也是“破镜难圆”，通过散列值恢复消息值几乎是不可能的。

MD家族和SHA家族

从哈希（Hash）函数这一概念诞生至今，已经提出了几十种哈希算法，每类算法对应不同的参数又会形成不同的算法实现。众多的哈希函数如同一个江湖，其中MD家族和SHA家族是“哈希江湖”中最具声望的两大家族。

MD5加密过程图

 MD家族代表：MD4、MD5

MD4和MD5是由Rivest分别在1990年和1991年设计的哈希函数，能够产生128比特的散列值。其中随着Dobbertin提出的碰撞攻击方法，MD4已经不再安全。2004年，王小云团队提出了MD5的碰撞攻击方法，也对MD5的安全性产生巨大影响。

SHA-1加密过程图

  SHA家族代表：SHA-1、SHA-2

SHA-1是由NIST（National Institute of Standards and Technology, 美国国家标准技术研究院）设计的一种能够产生160比特散列值的哈希函数。1993年被作为美国联邦信息处理标准规格（FIPS PUB 180）发布的是SHA，1995年发布的修订版中称为SHA-1。SHA-256/384/512 也是NIST设计的哈希函数，长度值分别为256、384和512比特，这些函数统称为SHA-2，于2002年发布。SHA-1的强抗碰撞性在2005年被攻破，2017年Marc Stevens和Google团队完成了完整轮数SHA-1的一个实际碰撞攻击，SHA-1已经彻底不再安全。虽然SHA-2尚未被攻破，但是由于SHA-2采用的是与SHA-1同样的结构，因此SHA-2也存在着潜在安全隐患。

SHA家族

SHA-3的崛起

随着MD家族衰落和SHA-1前辈即将退出历史舞台，为了选出新的武林盟主，NIST在2007年公开征集第三代哈希函数标准，举办了SHA-3竞赛。NIST一共征集到64个算法，经过三轮的激烈角逐，2012年，Keccak算法赢得了SHA-3竞赛的最终胜利，成为新一代的哈希标准算法SHA-3。

Keccak团队：Michaël Peeters, Guido Bertoni, Joan Daemen,Ronny Van Keer and Gilles Van Assche（从左至右）

Keccak算法由Guido Bertoni, Joan Daemen, Michaël Peeters,Gilles Van Assche 和 Ronny Van Keer团队提出，具有不同于MD和SHA-1/2的海绵结构，使得传统攻击方法无法直接应用于SHA-3的攻击中。为了扩大Keccak算法的影响力，同时也为了促进SHA-3安全性分析研究，Keccak团队广发英雄帖，发起Keccak原像挑战和碰撞挑战竞赛（https://Keccak.team/crunchy_contest.html），鼓励研究人员对Keccak算法的安全性发起冲击。

海绵结构示意图

现在，SHA-3除了Keccak算法本身，也逐渐形成一支庞大的家族。Keccak的衍生算法包括Kejte、Keyak、KangarooTwelve和Kravatte，这些算法都将会被广泛应用于经济生活的各个领域。

哈希函数的安全性分析

一个安全的哈希函数必须能够抵抗碰撞攻击和第二原像攻击（Second-Preimage）。

哈希函数的碰撞攻击和（第二）原像攻击

碰撞攻击旨在找到两个不同消息，其哈希值相同，哈希值可以为任意值；给定一个确定的哈希值，原像攻击旨在找到一个消息，使得该消息的哈希值与给定的哈希值相等；给定一个消息及其哈希值，（第二）原像攻击旨在找到另一个不同的消息，使得两者的哈希值相同。

一个输出n比特哈希值的哈希函数H针对碰撞攻击和（第二）原像攻击的安全性通常是n/2和n比特，也就是说任何碰撞攻击的复杂度至少是2的n/2次方，任何（第二）原像攻击的复杂度至少是2的n次方。哈希函数也可以用在带密钥的模式下，如消息认证码。如果哈希函数H存在复杂度低于2的n/2次方的碰撞攻击，或复杂度低于2的n次方的（第二）原像攻击，那么该哈希函数即被攻破。如果攻击的复杂度可实现，就会导致签名伪造、身份冒充、口令窃取等恶意攻击，给实际应用带来极大风险。2017年，随着SHA-1被实际攻破，各大互联网应用纷纷向具有更强安全性的SHA-2、SHA-3迁移。

对Keccak/SHA-3的分析

对Keccak/SHA-3算法的分析主要围绕碰撞攻击和原像攻击两个方面进行。目前Keccak/SHA-3算法在这两方面分析的最新结果均由中国科学院信息工程研究所和新加坡南洋理工大学的团队合作给出。

碰撞攻击

2012年，Dinur等人将代数分析与差分分析结合，得到Keccak 4轮的碰撞攻击，其中代数方法将消息初始值和一条3轮的差分路径连接起来，如下图所示。初始值和差分路径之间的这部分被称为连接器。

SHA-3碰撞攻击框架

2016~2017年，中国科学院信息工程研究所乔珂欣、宋凌、刘美成和新加坡南洋理工大学郭建、华南师范大学廖国鸿提出原创性的（部分）线性化方法，通过消耗自由度的方式将Keccak的非线性部件（部分）线性化，并将连接器从原来的1轮推进到3轮，从而得到Keccak一系列5轮和6轮的实际碰撞攻击，这也是目前Keccak最好的碰撞攻击。

Keccak/SHA-3碰撞攻击现状

同时，乔珂欣等也是Keccak碰撞攻击挑战最高轮数记录的保持者。

Keccak碰撞攻击挑战赛进展（https://Keccak.team/crunchy_contest.html）

 原像攻击                                 

尽管有学者提出过利用差分路径解决原像问题的思路，但目前Keccak的原像攻击主要还是通过求解代数系统来实现。低轮次的原像攻击主要通过SAT求解器完成。由于高轮Keccak算法对应的代数系统次数较高，在随后的几年里，原像攻击方面都没有实质性的进展。直到2016年中国科学院信息工程研究所的刘美成、宋凌和新加坡南洋理工大学的郭建提出了一种线性结构，才获得了3轮和4轮Keccak原像问题的更好分析结果。2017~2018年，中国科学院信息工程研究所的孙瑶和李婷基于非线性代数方法给出了目前3轮和4轮Keccak原像攻击的最好结果。

Keccak/SHA-3原像攻击现状

在挑战方面，最高轮次以及（目前）最后被攻破的挑战问题由刘美成、郭建、孙瑶、李婷等完成。

Keccak原像攻击挑战赛进展（https://Keccak.team/crunchy_contest.html）

结束语

Keccak/SHA-3函数不仅将作为目前最重要的哈希函数被更加广泛的应用于经济生活中，同时也将是学术界未来若干年的研究热点，将会受到广泛的关注。欢迎有兴趣的读者投身于Keccak/SHA-3函数的研究，任何新方法、新技术都将引领哈希函数领域的进一步发展。

参考文献：

[1].    Bertoni, G., Daemen, J., Peeters, M., Van Assche, G. (2013, May). KECCAK. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 313-314). Springer, Berlin, Heidelberg.

[2].    Bertoni, G., Daemen, J., Peeters, M., Van Assche, G. (2014). KECCAKcrunchy crypto collision and pre-image contest. Online at http://keccak.noekeon.org/crunchy_contest. html.

[3].    Dobbertin, H. (1996, February). Cryptanalysis of MD4. In International Workshop on Fast Software Encryption (pp. 53-69). Springer, Berlin, Heidelberg.

[4].    Guo, J., Liu, M., Song, L. (2016, December). Linear structures: Applications to cryptanalysis of round-reduced KECCAK. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 249-274). Springer, Berlin, Heidelberg.

[5].    Guo, J., Song, L.(2017). Cube Attack against Full Kravatte.Cryptology ePrint Archive, Report 2017/1026 (2017), https://eprint.iacr.org/2017/1026.

[6].    Li, T., Sun, Y., Liao, M., Wang, D. (2017). Preimage attacks on the round-reduced KECCAK with cross-linear structures. IACR Transactions on Symmetric Cryptology, 2017(4), 39-57.

[7].    Qiao, K., Song, L., Liu, M., Guo, J. (2017, April). New collision attacks on round-reduced KECCAK. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 216-243). Springer, Cham.

[8].    Rivest, R. (1992). The MD5 message-digest algorithm.

[9].    Secure Hash Standard (1993). Federal Information Processing Standard (FIPS) Publication 180.

[10].Secure Hash Standard (1995). Federal Information Processing Standard (FIPS) Publication 180-1.

[11].Song, L., Liao, G., Guo, J. (2017, August). Non-full sbox linearization: Applications to collision attacks on round-reduced KECCAK. In Annual International Cryptology Conference (pp. 428-451). Springer, Cham.

[12].Song, L., Guo, J.,  Shi, D. New MILP modeling: improved conditional cube attacks to KECCAK-based constructions.

[13].Stevens, M., Karpman, P.,  Peyrin, T. (2016, May). Freestart collision for full SHA-1. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 459-483). Springer, Berlin, Heidelberg.

Wang, X., Feng, D., Lai, X., Yu, H. (2004). Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. IACR Cryptology ePrint Archive, 2004, 199.

中国保密协会

科学技术分会

长按扫码关注我们

作者：京香花园

责编：何洁

往期精彩文章TOP5回顾

近期精彩文章回顾