密码学大事件！ SHA-1 哈希碰撞实例

在经过两年的联合研究和花费了巨大的计算机时间之后，研究人员在他们的研究网站 SHAttered 上给出了两个内容不同，但是具有相同 SHA-1 消息摘要的 PDF 文件（PDF 1、 PDF 2），这就意味着在理论研究长期以来警示 SHA-1 算法存在风险之后，SHA-1 算法的实际攻击案例也浮出水面，同时也标志着 SHA-1 算法终于走向了生命的末期。

2017年2月23日，荷兰阿姆斯特丹 Centrum Wiskunde & Informatica (CWI) 研究所和 Google 公司的研究人员 [Marc Stevens (CWI Amsterdam), Elie Bursztein (Google), Pierre Karpman (CWI Amsterdam), Ange Albertini (Google), Yarik Markov (Google), Alex Petit Bianco (Google), Clement Baisse (Google)] 在谷歌安全博客上发布了世界上第一例公开的 SHA-1 哈希碰撞实例！在经过两年的联合研究和花费了巨大的计算机时间之后，研究人员在他们的研究网站 SHAttered 上给出了两个内容不同，但是具有相同 SHA-1 消息摘要的 PDF 文件（PDF 1、 PDF 2），这就意味着在理论研究长期以来警示 SHA-1 算法存在风险之后，SHA-1 算法的实际攻击案例也浮出水面，同时也标志着 SHA-1 算法终于走向了生命的末期。

MD-SHA 系列 Hash 函数家族是最为知名的 Hash 函数家族，MD5，SHA-1 和 SHA-2 都被广泛的使用过。1990 年 MD4 算法被提出，但是被很快发现了严重的安全问题，在 1992 年被 MD5 算法取代。MD5 算法在之后的十几年内被软件行业广泛使用，直到 2004 年我国密码学家王小云在国际密码讨论年会（CRYPTO）上展示了 MD5 算法的碰撞并给出了第一个实例（《Collisions for hash functions MD4, MD5, HAVAL-128 and RIPEMD，rump session of CRYPTO 2004，How to Break MD5 and Other Hash Functions，EuroCrypt 2005》）。该攻击复杂度很低，在普通计算机上只需要几秒钟的时间。在 2005 年王小云教授与其同事又提出了对 SHA-1 算法的碰撞算法（《Finding Collisions in the Full SHA-1， CRYPTO 2005》），不过计算复杂度为 2 的 69 次方，在实际情况下难以实现。

在现实世界中，利用 Hash 碰撞的真实案例确确实实发生在我们身边：

2008 年的 Chaos Communication Congress 大会上，研究人员展示了利用 MD5 碰撞来伪造合法 CA 证书，从而攻破 HTTPS 的安全体系。

2012 年在中东大范围爆发的火焰（Flame）病毒，包含了一个伪造的数字签名，就是利用 MD5 碰撞伪造了合法的微软签名来逃避杀毒软件的查杀。

本次攻击的关键先生是荷兰阿姆斯特丹 CWI 研究所的 Marc Stevens，他自 2006 年以来一直在 Hash 算法的研究领域发表了大量令人艳羡的成果，包括一系列关于 MD5 算法的攻击。2009 年他作为一作的论文 《Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate 》在当年的 CRYPTO 上获得了最佳论文奖，在 2013 年的 Eurocrypt 上，他发表了一篇论文——《New collision attacks on SHA-1 based on optimal joint local-collision analysis》，提出了构造 SHA-1 碰撞的一种新的攻击方法（攻击复杂度为 2 的 61 次方，随后又提出了基于 GPU 的高效实现方法），随后数年不断提出了新的改进方法，在 2016 年他给出了关于 SHA-1 算法的 Freestart collision，也就是找到了 SHA-1 算法内部的核心组件 internal compression function 的一个碰撞实例（64 GPU 集群，10 天计算量），这就已经吹响了攻克 SHA-1 完全实际碰撞攻击的决战号角。终于，在 Google 公司强有力的计算资源支持之下，在 2017 年 2 月 23 日，SHA-1 算法的碰撞实例出现在我们面前！

此次攻击到底使用了多强的计算资源，我们可以看一下谷歌安全博客给出的原始数据：

• Nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total
• 6,500 years of CPU computation to complete the attack first phase
• 110 years of GPU computation to complete the second phase

可以看到，这样如此强劲的计算能力几乎是历史上最大规模的一次计算 Hash 碰撞的实验。谷歌安全博客还专门配了一幅图来比较，如果使用暴力搜索，使用的计算资源即使是 Google 也无法承担，而在人类智慧的研究之下，改进的 Shattered 算法只需要 110 个 GPU 年就可以完成第二阶段的搜索任务。

关于攻击的更多细节，可以参考论文——《The first collision for full SHA-1》。关于这篇论文，还有很多幕后的八卦，LoCCS 实验室理论密码研究组长期从事分组加密算法研究的王磊研究员曾与 Marc Stevens 合家聚餐，亲切交谈，并与本次工作的作者之一 Pierre Karpman 长期合作交流，王磊老师告诉我们，他目睹了这个密码学历史性事件的诸多进展，这个轰动性结果甚至让今年某顶级学术会议的 Deadline 为之延期！！！

我们指出，SHA-1 碰撞攻击影响了大量现有的安全应用。

目前许多部署的 SSL/TLS 服务连接中均使用了 SHA-1 算法作为消息验证的基本密码学原语，因此受到该攻击的影响；流行的源代码管理系统 Git 直到目前依然使用 SHA-1 作为文件的消息“指纹”。

另外一个广泛受到影响的场景是 Android 系统中应用、升级包、Bootloader 等模块的签名机制（RSA + SHA-1），虽然 Android 7.0 给出的全新的签名方案 APK Signature Scheme v2 中支持 SHA-2 家族的 SHA-256 和 SHA-512，但经过我们的验证，目前大量设备仍然在使用 sha1withRSA 的签名验证。在碰撞攻击的影响下，攻击者能够构造出内容篡改但是签名一致的文件绕过验证。尽管计算量巨大且对内容的控制存在一定的困难，但是我们认为这类安全机制已经不再可信。

Google 公司和诸多 IT 安全研究人员均在过去几年呼唤开发者尽快更换 SHA-1 算法，早在 2014 年，Chrome 团队就已经宣布了淘汰 SHA-1 算法的时间表，本次碰撞实例的发布，也给所有还在持观望和犹豫态度的人敲响了警钟：赶紧为安全的系统启用新的 Hash 算法！

事实上，SHA-1 算法的后继算法早就已经被研究人员设计和推广，SHA-2 算法家族（包括六种 Hash 函数：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256）在 2001 年就已经公布，而 NIST 在经过多年的 SHA-3 设计竞赛后，在 2015 年正式推荐由著名的密码学研究人员 Guido Bertoni, Joan Daemen, Michaël Peeters 和 Gilles Van Assche 共同设计的 Keecak 算法家族作为 SHA-3 的候选算法。更为值得注意的是，中国国家密码管理局同样在 2010 年底发布了我国自主的国密 SM3 消息摘要（密码杂凑）算法。这些算法的安全性在目前经受住了广泛的测试和分析，是值得信赖的。所以，文章的最后，GoSSIP 小组建议大家：任何以 SHA-1 作为消息摘要算法的安全产品应该尽快更换至这些更为安全的 Hash 算法。

上海交通大学密码与计算机安全实验室（LoCCS）软件安全小组（GoSSIP）版权所有，转载请与作者取得联系！

本文已获授权转载。本文使用的图片来自谷歌安全博客。