今天分享的论文主题为针对SHA-1算法的选择前缀碰撞攻击，由来自法国国家信息与自动化研究所及新加坡南洋理工大学的两位密码学研究者合作完成。哈希算法SHA-1早在2005年[1]便被证实存在碰撞攻击安全风险。但迄今为止，公钥证书、TLS/SSH等网络安全协议及应用仍未完全将其“淘汰”。关键原因在于，对真实世界的攻击者而言，寻找SHA-1碰撞攻击实例的计算复杂度和技术挑战非常高，攻击代价过于昂贵。工业界普遍默认不太可能出现真实的攻击案例，也就没有动力彻底弃用SHA-1算法。
本次介绍的论文首次在真实网络应用场景中实现了SHA-1选择前缀碰撞攻击。作者首先基于对已有攻击原理和步骤的深入分析，提出了优化方案，将攻击计算复杂度从2^67降低至2^63；随后利用低价租借的GPU计算资源完成了攻击方案的实际部署，单次攻击成本可控制在4万5千美元；基于优化后的攻击方法，作者成功实现了针对PGP网络用户证书的选择前缀碰撞，能够伪造任意受害者用户的PGP公钥证书。论文发表于网络安全顶级会议USENIX Security 2020 （录用率16.1%）。
全文约4500字，阅读时间约12分钟。
哈希函数可将任意长度的消息映射为某个固定长度的哈希值，即计算消息摘要。由于具备确定性（对固定输入消息产生确定的摘要计算结果）、单向性（无法根据摘要值倒推出原始消息）、快速性（摘要计算过程可快速完成）等特性，其已广泛应用于各类密码算法及安全协议，为加密、认证、鉴权等应用场景提供支撑。
“抗碰撞”（Collision Resistance）是哈希函数最重要的安全特性之一。其含义为，对哈希函数H(X)而言，若想找到两条不相同的消息M、M’，使得H(M)=H(M’)，必须是非常“困难”的。“困难”程度通常以寻找碰撞消息所需的计算复杂度来衡量。于密码学家而言，对某种哈希算法的“破解”，便是指找到计算复杂度足够低的方法，生成关于该算法的碰撞消息。考虑到现实应用中，哈希算法保护的通常是文件、协议报文等具有一定格式要求的数字消息，碰撞攻击又可进一步升级出“固定前缀碰撞攻击”（Identical-prefix Collision）与“选择前缀碰撞攻击”（Chosen-prefix Collision），即要求找到的两条碰撞消息具有完全相同或等于已知数值的不同前缀。选择前缀攻击的难度显然高于普通碰撞，但也更符合哈希算法的现实应用场景。
图表1：SHA-1采用Merkle-Damgård结构计算消息摘要
SHA-1是安全散列算法家族（Secure Hash Algorithm）历史最为悠久且（曾经）应用最广泛的哈希算法，发布于1995年[2]。通常而言，输入任意长度消息、输出固定长度摘要的哈希算法H(X)是由某个输入输出长度均固定的h(x)以某种方式组合构造而成的。SHA-1采取的是Merkle-Damgård[3,4]构造结构，如图表1所示。算法将首先对输入消息M进行一定的填充，使其长度为h(x)输入长度的整数倍；其次将M分割为消息块M[i]，从首个消息块开始，结合固定值IV计算哈希值，并将该值作为下一个消息块计算的IV；该过程将持续进行，直到最后一个消息块计算完毕，得到完整消息M的哈希值。
图表2：SHA-1碰撞攻击的学术界研究进展
此前，学术界已经针对SHA-1的“抗碰撞”能力开展了诸多研究，如图表2所示。2005年，我国密码学家王小云院士于美密会议首次披露了对SHA-1哈希函数的破解方法[1]，攻击复杂度约为2^69；随后，多项研究工作围绕如何降低攻击复杂性展开，但都局限于理论层面；直到2017年，来自谷歌的研究团队将攻击变为现实，其利用在计算平台方面的优势，通过调度庞大的GPU集群，以约2^64.7的计算复杂度实现了SHA-1碰撞攻击[5]，构造出内容不同但哈希值相等的两份PDF文件，如图表3所示。值得注意的是，由于PDF文件有一定格式要求，该攻击为相同前缀碰撞攻击；而对于更为复杂的选择前缀攻击，最新研究为2019年的一项工作[6]，将攻击复杂度降为2^67.2，但该强度对攻击者而言，尤其是在没有类似谷歌庞大GPU计算集群的前提下，几乎仍是不可能实现的。
图表3：首个SHA-1相同前缀攻击实例（内容不同但哈希值相等的两份PDF文件）
本次介绍的论文则针对SHA-1实际应用中更为普遍的攻击场景，即复杂度更高、难度更大的选择前缀攻击展开研究。作者通过深入分析已有理论分析工作和实际攻击工作的底层原理和技术细节，利用多项密码分析技巧，将选择前缀攻击的复杂度约从2^67降低至2^63，并通过租借价格低廉的GPU计算资源，以低成本进行了攻击实现；此外，作者还以可信网络（Web of Trust）模型中的PGP证书为对象，成功构造出用户ID及公钥不同但哈希值相等的证书内容，并依此实现了PGP网络中的身份伪造攻击。
论文的密码攻击算法优化部分涉及大量底层细节，作者在USENIX Security论文[7]之外还提供了包含更多技术内容的补充版本[8]。本篇推送将仅介绍算法部分的大致思路，请对密码算法细节感兴趣的读者参考原文[7]和补充论文[8]。
（1）优化碰撞攻击的底层技术
作者首先对2013年的一项碰撞攻击理论研究工作[9]和2017年谷歌团队寻找碰撞攻击实例的工作[5]进行了深入分析，发现底层攻击技巧可以调整优化，但该过程非常复杂。例如，采取某个技巧将损失某个步骤的成功概率，但可以大幅地提升实际的整体攻击效率，此外，也还需要考虑算法的整体复杂度是不是可评估的。总之，作者基于对已有研究工作结果的经验性观察，利用技术性极强的密码分析技巧，在已有方案的基础上，将碰撞攻击底层技术的复杂度降低为约1/10。
图表4：选择前缀攻击的整体流程示意图
除了密码分析的底层技术之外，作者也对选择前缀碰撞的整体攻击方法进行了调整。例如，在图表4攻击流程的stage 2结束后，算法已经找到了某个备选集合S，下一步便是消除S中元素的差异。在已有攻击流程中，此步骤将通过在Graph（图）中寻找某条Path（路径）的方法实现。由于需要检索和计算的Graph规模非常庞大（约含有2^36.2个节点，仅存储节点就需要2TB的空间），此步也是优化的关键所在。作者采取了几种不同的优化技巧，如图表5所示，包括（1）对图进行聚类，减少重复搜索；（2）在图中部署二向搜索，结合预计算降低图搜索复杂度（3）在图中增加隐式节点提高效率，并通过仿真模拟评估复杂度的方法，解决增加节点引入的复杂度不可计算的问题。
图表5：选择前缀攻击中对图搜索算法的优化（从左至右：原始方法、聚类优化、二向图优化、隐节点优化）
（3）攻击算法实际部署
经过优化，SHA-1选择前缀攻击的计算复杂度已降低至2^63.7。然而，作者估计，如果使用成熟的云计算集群，例如Google或者Amazon的计算平台，部署该攻击仍需花费约16万美元。作者认为，SHA-1碰撞的计算并不需要GPU提供多么华丽的功能（例如任务调度等），没有必要花高价租借性能强大的商业计算服务。于是，作者把目光转移到低价的GPU租借平台gpuserversrental.com，租用某些原本用于游戏加速或者挖矿的显卡（如GTX 1060）实现了攻击。
（4）实验结果
作者实际租借了共150台机器，每台机器配备6张显卡（GTX 1060），在其上部署了攻击计算实验。实验整体计算耗时为两个月，如图表6所示。作者于2019年9月27日成功构造出首个SHA-1选择前缀攻击实例，实际花费约为7万5千美元。但考虑到GPU计算价格的波动（基本持续下滑），作者认为，攻击成本可以控制在4万5千美元左右。
图表6：攻击实验计算时间记录
然而，找到选择前缀碰撞消息只是基础，在实际网络应用场景中利用SHA-1碰撞实现攻击仍然是极具挑战的任务。因为在实际场景中，SHA-1保护的消息需要符合一定的格式（例如证书格式），其消息内容也不应完全随机，而是具备实际意义（例如为某用户的公钥）。
（1）攻击场景
作者选取的攻击场景为信任网络（Web of Trust）。不同于Web PKI体系通过固定的第三方权威机构签发证书，Web of Trust的信任锚点更加分散，每个用户都可作为CA为其所信任的其他用户签发证书。Web of Trust用户使用的是PGP（Pretty Good Privacy）证书，内容包含基本的报头等格式信息、用户的身份（ID，property）以及用户持有的公钥（Public Key）。其主要作用便是证明用户身份和公钥之间的绑定关系，使得通信双方信任对应的密钥，并基于此实现安全通信。具体地，攻击者Bob是该网络的一位合法用户，持有ID Bob 和 Public Key Bob，并可获取对应的证书，其攻击目标便是通过巧妙地构造ID Bob与Public Key Bob，使得证书内容与另一张嵌有受害者Alice ID的证书发生碰撞，进而伪造带有合法签名的Alice证书，实现仿冒攻击。
图表7：Web of Trust信任模型，证书内容包含用户ID及其公钥，用来证明用户和密钥的绑定关系
（2）实施步骤
图表8：PGP证书碰撞构造示意图
a. 寻找选择前缀碰撞消息。PGP证书的格式如图表8所示，最前方是头部消息和格式信息（Prefix）。因此，攻击者Bob在还未加入网络时，就可以提前根据自己证书的Prefix和Alice证书的Prefix进行预计算，找到两条SHA-1碰撞的消息M与M’，为构造碰撞证书内容做准备。
b. 精心构造公钥和用户身份信息。Bob在加入网络后，可以声明自己的身份信息和其所持有的公钥。根据PGP证书格式要求，在证书内容中，公钥将首先填充到Prefix后，随后才是用户身份信息。Bob将首先寻找到某个key，使得key的前缀部分刚好为已经找到的碰撞消息M（由于PGP的公钥长度允许范围宽泛，根据论文介绍，此步骤并不难做到），参见图表8 右侧证书的绿色部分（CPC代表找到的碰撞消息M）；其次，在填充用户身份信息时，由于PGP证书允许使用图像作为身份特征，而图像格式的校验通常并不严格，在JPEG Reader可读的数据范围之外，还可填充不影响图像内容的冗杂数据段，给碰撞构造带来充足的空间。Bob将选取自己的一张照片，并在合法数据段之后填入冗杂数据，使得冗杂数据中刚好嵌入受害者Alice的ID。
c. 申请合法证书签名。Bob将带有精心构造的公钥和身份信息（带有Alice ID的图像）发送给某个CA，由于Bob目前看起来只是一个加入网络的普通用户，且其图像可读的部分是合法的身份ID，CA将通过Bob的身份认证，为该证书补充数字签名。值得一提的是，数字签名是针对SHA-1哈希之后的证书内容进行的。
d. 构造仿冒Alice身份的证书。Bob在获得合法证书（图表8右侧）后，便可开始伪造Alice的证书（图表8左侧）。首先将和消息M产生SHA-1碰撞的M’贴到证书内容中，由于存在碰撞，左右两张证书内容在图中“Collision”标注之前的哈希值是完全一致的；随后，Bob直接将其证书的后半部分复制粘贴过来。请注意，此时得到的证书包含Alice ID，且Bob在构造自身证书时，利用冗余字段的自由度，使得碰撞消息M’ + Alice ID之前的证书数据内容刚好又形成另一个由Bob掌握的公钥key’；也就是说，对当前左侧的证书而言，其前半部分为Bob掌握的某个公钥，后半部分为Alice ID，且证书的SHA-1哈希与Bob合法证书完全一致（选择前缀碰撞消息+完全相同的复制消息），因此，Bob合法证书的签名可以直接复制给伪造证书。最终，Bob便生成了一张带有Alice ID与自己持有的公钥key’，且被合法CA赋予签名的证书，便可使用自己持有的公钥伪装成Alice与其他用户进行通信。
作者将构造出的PGP证书实例公布在了项目的开源网站[10]，感兴趣的读者可亲自动手验证。
论文选择寻找PGP证书碰撞，而不是应用更为广泛的X.509证书，原因包括但不限于：
a. X.509证书格式比PGP更为复杂，特别是前缀部分。选择前缀碰撞攻击需要首先确定消息前缀的内容，再寻找可以发生碰撞的后续信息。然而X.509的证书前缀太复杂，还包含了证书序列号等难以预知内容的信息，将极大地增加攻击的难度。
b. X.509证书字段要求、顺序与PGP不同，碰撞攻击难度更大、成本更高。作者能够顺利构造出PGP证书碰撞的主要因素，是PGP证书字段要求宽泛，为伪造证书提供了充足的自由度。攻击者可以在JPEG图像之中嵌入冗余字段、隐藏受害者ID；此外，PGP证书的字段顺序是先公钥、再用户ID，即用户ID不作为前缀的一部分，这使得选择前缀碰撞的可以不考虑用户ID，也就是单次碰撞的计算结果可用来伪造多张证书，极大地降低了攻击成本；而X.509证书的字段顺序是先用户ID、再公钥，用户ID为前缀的一部分，碰撞的计算也就仅对固定ID有效，实际的攻击成本依旧很高。
04
尽管早在2005年便被发现存在碰撞攻击风险，SHA-1算法在当前的网络安全应用中仍未被完全淘汰。原因是，实际攻击对碰撞消息的格式、内容以及攻击计算成本都有额外的要求，工业界普遍认为，很难在可接受的计算成本内找到SHA-1碰撞攻击案例。本次介绍的论文实现了首个SHA-1选择前缀碰撞攻击在真实网络场景的攻击实例，作者在攻击底层算法、选择前缀碰撞寻找方式等技术层面进行了极具技术挑战性的优化，降低了攻击复杂度，并通过租借低价GPU服务，将SHA-1选择碰撞攻击成本控制在4万5千美元。作者还在Web of Trust场景中成功地构造出了PGP证书碰撞，可以实现身份仿冒攻击。论文证明，攻击者完全有能力利用SHA-1的碰撞脆弱性，发起真实的网络攻击。论文技术部分难度很高，工作内容扎实，实验结果将对安全社区重新认识SHA-1的实际安全风险、推动密码算法更新起到非常重要的作用。
原文链接
https://www.usenix.org/system/files/sec20-leurent.pdf
扩展补充版本
https://eprint.iacr.org/2020/014
开源项目
https://sha-mbles.github.io/
参考文献
[1] Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu. Finding collisions in the full SHA-1. In Victor Shoup, editor, CRYPTO 2005, volume 3621 of LNCS, pages 17–36. Springer, Heidelberg, August 2005.
[2] National Institute of Standards and Technology. FIPS 180-1: Secure Hash Standard, April 1995.
[3] Ivan Damgård. A Design Principle for Hash Functions.
[4] Ralph C. Merkle. One Way Hash Functions and DES.
[5] Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, and Yarik Markov. The first collision for full SHA-1. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 570–596. Springer, Heidelberg, August 2017.
[6] Gaëtan Leurent and Thomas Peyrin. From collisions to chosen-prefix collisions application to full SHA-1. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part III, volume 11478 of LNCS, pages 527–555. Springer, Heidelberg, May 2019.
[7] Leurent, Gaëtan, and Thomas Peyrin. SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust. 29th USENIX Security Symposium (USENIX Security 20). 2020.
[8] Gaëtan Leurent and Thomas Peyrin. SHA-1 is a Shambles – First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust. Cryptology ePrint Archive, Report 2020/014, 2020.
[9] Marc Stevens. New collision attacks on SHA-1 based on optimal joint local-collision analysis. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 245–261. Springer, Heidelberg, May 2013.
[10] SHA-1 is a Shambles. https://sha-mbles.github.io/.
原文始发于微信公众号（NISL实验室）：【论文分享】SHA-1选择前缀碰撞攻击及PGP证书伪造实例
