新碰撞攻击无情鞭挞SHA1算法 BTC的SHA256已不安全？

三年前，谷歌宣布SHA1加密哈希算法正式死亡，研究人员成功执行了世界上第一例已知的针对SHA1的碰撞攻击。本周二，另一组研究人员公布了一种新的攻击方法，而它的威力要明显更加强大，这使得已死过一次的SHA1遭到了无情鞭尸。

这种新的碰撞方式，赋予了攻击者更多的选择和灵活性，它使得创建PGP加密密钥变得切实可行，而研究者在周二公布的数据显示，这种攻击只花费了4.5万美元，相比之下，2017年披露的攻击不允许伪造特定的预先确定的文档前缀，而当时的攻击成本预计从11万美元到56万美元不等，这取决于攻击者的执行速度。

ENuzCQHXsAAN1IC

（图片来自：John Adler）

而新的攻击则要明显更加强大，大致上实现了约10倍的效果。

你可能会说，谷歌都宣布过SHA1已死了，还有人在使用这种哈希算法？

事实上，还就是那么回事，尽管在过去五年里，SHA1的使用率已越来越低，但它距被完全淘汰还有很远的距离。

截至目前，SHA1仍然是GnuPG遗留1.4版本分支中用于验证PGP密钥的默认哈希函数（GnuPG是PGP应用程序的开源后续版本，其被用于加密电子邮件和文件）。

Git，一款被广泛应用的管理软件系统，它仍然依赖SHA1来确保数据的完整性。很多依赖于HTTPS加密的非Web应用程序仍然接受SHA1证书。

也难怪，本周在纽约召开的密码学研讨会上，研究人员警告说，即使SHA1的使用率很低或仅用于向后兼容，它也会让用户面临攻击威胁，他们强调应尽快全面淘汰SHA1哈希算法。

啥是哈希函数？

概括地说，哈希（hash）是消息、文件或其他类型的数字输入的加密指纹，与传统指纹一样，它们应该是唯一的。哈希也被称为消息摘要，它在确保加密密钥、电子邮件和其他类型的消息属于特定个人或实体方面，起着至关重要的作用，这可以防止对手创建伪造的输入。这些数字指纹以固定的数字和字母序列的形式出现，它们是在将消息输入哈希算法或函数时生成的。

sha1-800x535

而哈希算法的整个安全性，取决于能否找到产生相同指纹的两个或多个不同输入。位长为n的函数，应要求暴力攻击者在发现碰撞之前测试2^(n/2)个输入（一个被称为生日悖论的数学概念，显著减少了所需的猜测次数）。具有足够位长和抗碰撞性的哈希函数是安全的，因为它们需要攻击者投入不可行的时间及计算资源来进行碰撞。如果使用少于2^(n/2)次的尝试就可以发现碰撞，则我们认为该哈希函数被破解。

128位的MD5哈希函数是较早被广泛使用，且遭到破解的哈希函数。尽管早在1996年，研究人员就曾警告说，MD5的缺陷使其容易被碰撞，但在此后的20多年里，MD5哈希函数仍是软件和Web身份验证的关键部分。

然后，在2008年，研究人员使用MD5碰撞为他们任意选择的网络创建了一个HTTPS证书。这次演示，最终说服证浏览器信任的证书颁发机构放弃了MD5哈希函数，但该算法仍被广泛用于其他目的。

SHA1被证明遵循了一条与MD5惊人相似的路径。在MD5消亡之后，SHA1在2004年就被王小云教授等人证明存在碰撞缺陷，但它由于具有更好的抗碰撞性，以及转向新算法存在的困难性，这使得SHA1即使在2015年之后仍然被广泛使用。

SHA1第一次被碰撞攻击

在2017年，研究人员展示了世界上首例已知的针对SHA1的碰撞攻击。它以两个PDF文件的形式出现，尽管它们显示的内容不同，但具有相同的SHA1哈希。其背后的研究者表示，在亚马逊的云计算平台上进行的攻击，只需要花费11万美元，当时密码学家们称之为经典的碰撞攻击。这也被称为相同前缀碰撞攻击，当两个输入具有相同的预先确定的前缀或开头，以及随后不同的数据时，就会产生相同的前缀碰撞。即使这两个输入明显不同，但如果文件中附加了其他数据，它们也可以哈希得出相同的值。换句话说，对于哈希函数H，两个不同的消息M1和M2将会导致相同的哈希输出：H(M1) = H(M2)。

相同前缀碰撞攻击非常强大，它对哈希函数的安全性而言是致命的打击，但它们对攻击者的作用也有限。一种更强大的碰撞形式称为选择前缀攻击（chosen prefix attack），这使得2008年针对HTTPS证书系统的MD5攻击和2012年针对微软更新机制的MD5攻击成为可能。内容交付网络Cloudflare的密码学主管Nick Sullivan在2015年的文章中对这种选择前缀碰撞攻击进行了详细的解释。

PGP/GnuPG 选择前缀碰撞攻击模拟

而在本周二发生的碰撞攻击，是已知第一例针对SHA1的选择前缀碰撞攻击，为了证明其效力，来自法国INRIA和新加坡南洋理工大学的研究人员Gaëtan Leurent和Thomas Peyrin分别利用这种碰撞方式进行了PGP/GnuPG模拟攻击。在他们的论文当中，他们解释称：

“选择前缀对应于具有不同大小密钥的两个PGP身份证书的header，一个RSA-8192密钥和一个RSA-6144密钥。通过利用OpenPGP和JPEG格式的特性，我们可以创建两个公钥：带有受害者名称的密钥A和带有攻击者名称和图片的密钥B，这样包含攻击者密钥和图片的身份证书，与包含受害者密钥和名称的身份证书具有相同的SHA-1哈希。因此，攻击者可以从第三方（从信任网或CA）请求其密钥和图片的签名，并将签名传输到密钥A。由于碰撞，签名仍然是有效的，而攻击者使用受害者的名称控制密钥A，并由第三方签名。因此，攻击者可以冒充受害者，以受害者的名义签署任何文件。”

在一篇进一步演示攻击的文章中，研究人员同时提供了消息A和消息B。尽管包含了不同的用户ID前缀，但它们都映射到相同的SHA1哈希值8ac60ba76f1999a1ab70223f225aefdc78d4ddc0。

这显著提高了攻击SHA1哈希算法的效率，加速因子大约为10。更准确地说，当在GTX 970图形处理器上执行时，新的攻击将相同前缀碰撞攻击的代价从2^(64.7)降低到2^(61.2)，将选择前缀碰撞攻击的代价从2^(67.1)降低到2^(63.4)。

据悉，研究人员在两个月的时间里，对他们在线租用的900台Nvidia GTX 1060 GPU集群进行了攻击。

他们说，与亚马逊网络服务和其它竞争对手的云服务相比，租用的集群是一个更经济的选择。几个月前，他们进行的攻击花费了7.4万美元，但随着优化的实现以及计算成本的持续下降，他们现在执行同样的攻击只需花费4.5万美元，而根据预计，到2025年，执行攻击的成本将降低至10000美元。 因此，他们的结论便是，自2009年以来，针对MD5的选择前缀攻击，现在也适用于SHA1，并且会随时间的推移只会变得更便宜。

SHA1终于可以安息了，那比特币使用的SHA 256呢？

据悉，研究人员私下向受影响最大的软件开发人员报告了他们的研究成果，其中包括：

1. GnuPG，其回应称在11月份实施了一项对策，使得2019年1月之后创建的基于SHA1的身份签名失效；

2. CAcert，颁发PGP密钥的证书颁发机构，该机构承认目前仍在使用SHA1，并计划离开SHA1；

3. OpenSSL，此前，该加密库仍在继续接受SHA1证书，开发者回应称他们正考虑禁用SHA1；

考虑到依赖SHA1哈希算法的应用及协议依旧有很多，研究人员无法联系到所有受影响的开发者。为了防止攻击被滥用，他们暂时保留了许多碰撞细节。

约翰霍普金斯大学密码学教授马特.格林（Matt Green）评论称，这一研究结果令人印象深刻，它强调了SHA1算法不再安全的事实，他在接受采访时表示：

“对于一个安全的哈希函数来说，10的加速因子应该不会有太大的影响，但是当你陷入一个极其接近崩溃的状态时，这种效率的提升确实具有很大的影响，特别是当有大量的挖矿硬件存在的时候，我们知道，一只鞋子已经掉了，现在要轮到下一只鞋子了。”

译者简评：比特币当前采用的SHA 256哈希算法依旧是非常安全的，但总有一天，它也会面临更换哈希算法的时候，届时，加密货币和开发者社区会很快达成一致，然后通过硬分叉的形式将SHA 256更换成更强大的哈希算法（注：比特币代码维护者Pieter Wuille在第一时刻就转发了最新的SHA1碰撞研究，可见开发者们是非常关注的）。