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文件，这就意味着在理论研究长期以来警示SHA-1算法存在风险之后，SHA-1算法的实际攻击案例也浮出水面，同时也标志着SHA-1算法终于走向了生命的末期。
、
相关背景
MD-SHA系列Hash函数家族是zui为的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的一个碰撞实例(64GPU集群，10天计算量)，这就已经吹响了攻克SHA-1*实际碰撞攻击的决战号角。终于，在Google公司强有力的计算资源支持之下，在2017年2月23日，SHA-1算法的碰撞实例出现在我们面前!
此次攻击到底使用了多强的计算资源，我们可以看一下Google Security Blog给出的原始数据：
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
可以看到，这样如此强劲的计算能力几乎是历*zui大规模的一次计算Hash碰撞的实验。Google Security Blog还专门配了一幅图来比较，如果使用暴力搜索，使用的计算资源即使是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系统中应用APP、升级包、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消息摘要(密码杂凑)算法。这些算法的安全性在目前经受住了广泛的测试和分析，是值得信赖的。所以，文章的zui后，GoSSIP小组建议大家：任何以SHA-1作为消息摘要算法的安全产品应该尽快更换至这些更为安全的Hash算法。
上海交通大学密码与计算机安全实验室(LoCCS)软件安全小组(GoSSIP)翻译。
