你的数字签名会被撞破么？——安全hash的攻与防

本篇文章10166字，读完约25分钟

前言安全散列函数广泛应用于信息系统中，特别是用于消息签名任务，以保护消息的完整性和不可否认性。可以说，安全散列函数是现代应用密码学最重要的基石之一。如果安全哈希函数存在安全问题，将严重影响整个应用密码系统乃至整个互联网的安全，包括软件分发、网络支付、设备升级等。安全哈希函数面临的最大技术安全威胁是共谋碰撞攻击，但我们也发现，国内许多厂商自制的协议中存在大量不正确的安全哈希应用，导致使用简单的方法破坏其保护。近年来，随着计算机性能的提高，针对md5和sha1函数的冲突攻击的研究也取得了快速的进展。然而，由于中国的现实，替换md5/sha1非常昂贵，很难在短时间内解决。md5/sha1冲突会对现有信息系统造成什么威胁？本文讨论了md5/sha1的碰撞攻击及其应用场景，并给出了具体的攻击实例，同时给出了缓解措施。我们指出，在严格约束条件下破解md5/sha1以消除共谋冲突仍然是一项非常困难的任务。然而，这种机制只能给制造商一个难得的喘息机会，我们仍然敦促制造商尽快升级到更安全的hmac-sha256。

1.md5/sha1算法简介密码学中的安全散列函数不同于普通的散列函数。在典型的数据结构Hash_map和hash_set中使用的hash函数只需要将关键字映射到一个索引，即使有冲突，它们也可以通过开放哈希或封闭哈希来处理。密码学中对安全散列函数[1]的要求要严格得多，至少要满足三个性质:(1)防碰撞攻击，(2)抗抗原根攻击，(3)抗第二原始根攻击。防冲突攻击意味着很难找到两个不同的字符串x和y，使得哈希(x)=哈希(y)。抗原根攻击意味着在散列(x)=s中，知道s，很难找到x。反秒根攻击意味着当散列(x)=s已知时，很难找到不同于x的字符串y。只有满足上述三点的哈希函数才被视为安全哈希函数。

Md5/sha1是一个广泛使用的安全散列函数。它们的输入是任意字符串，输出是128/160位长的哈希值。Md5和sha1是在1992年和1993年发明的，它们被认为是安全的。在2004年和2005年，研究人员发现了针对它们的攻击方法，这降低了在特定环境下寻找碰撞的计算成本。2007年，首次提出了利用md5碰撞伪造ca证书的理论方法。2008年，这种攻击方法得到了验证，攻击者成功伪造了合法的ca证书。然而，针对sha1的攻击方法仍然停留在理论上，直到2017年初，针对sha1的成功碰撞攻击首次公之于众。

本文简要介绍了md5的计算过程，以供读者理解。sha1的计算过程非常相似:

首先，将补码相加，使位长度模块512的剩余部分为448(512-64)。接下来，长度被表示为一个小的端序，它被附加到后面(如果它大于64位，则只取较低的64位)。此时，位长度是512的倍数。接下来，依次处理每个512位块。md5内部状态(128位)在处理过程中不断更新。处理完所有块后，内部状态作为最终哈希值输出。

2.针对安全哈希的冲突攻击在某些情况下，攻击者需要构造一个字符串y，以便哈希(y)是一个指定的值s。此时，攻击者只能控制y，因此如果您想找到一个满足哈希(y)=s的实例，它属于原始根攻击。目前，md5/sha1的原始根攻击没有好的计算方法，只能依靠彩虹表、字典或蛮力搜索，攻击复杂度相当高(md5的状态空为2 128，蛮力搜索需要计算md5 2 128次)。

在其他情况下，攻击者可以同时控制两个输入字符串x和y，这样哈希(x)=哈希(y)，从而欺骗基于哈希的身份验证系统。这种情况被称为“阴谋碰撞”。共谋碰撞可以使用“生日攻击”来大大减少计算量。以md5为例，我们不需要枚举所有128位字符串来计算md5冲突值，只需要计算md5值2 64次就可以找到这样的X和Y，有50%的几率。

添加后缀后，Md5/sha1冲突具有冲突属性:

哈希(a+s)=哈希(b+s)，如果哈希(a)=哈希(b+s)

但它不满足添加前缀的性质，即

哈希(a)=哈希(b)不能推哈希(s+a)=哈希(s+b)

2.1长度扩展攻击由后缀扩展冲突引起的简单攻击是长度扩展攻击[4]。例如，一些基于md5的协议使用以下形式的签名值

符号=散列(秘密+消息)

秘密在哪里？在计算签名值签名之后，客户端将向服务器提交签名和消息。在某些情况下，攻击者可以同时获得签名值符号和明文消息，并能够在明文末尾附加任意字符串。此时，攻击者可以直接使用md5的属性，将恶意部分S附加到明文的尾部，并直接从原始的md5值计算出来

符号=散列(符号，s) =散列(秘密+消息+ s)

以这种方式构造的新请求消息+s具有合法的签名，因此它可以通过md5签名验证，但是包含攻击者注入的恶意部分。这种攻击也涉及到一些ctf主题[5]。在某些情况下，长度扩展攻击可以用来绕过基于md5的身份验证[6]。因为sha1或其他安全哈希具有这样的属性，所以用sha1或其他安全哈希替换md5通常是无效的。

所有可能受到长度扩展攻击的数字签名协议都应该立即升级到第4节中描述的hmac-sha256算法，因为黑色产品很可能已经在享受您的服务。

2.2前缀冲突攻击对于md5/sha1来说，比较复杂的攻击是目前常见的前缀冲突攻击和选择前缀冲突攻击。常见的前缀攻击是构造两个不同的消息s1和s2，它们由相同的前缀和不同的尾部“冲突块”组成。几天前震惊世界的粉碎攻击是对sha1的常见前缀攻击。选择前缀攻击是为了构造两个不同的消息s1和s2，它们不必有共同的前缀，但是在尾部附加不同的“冲突块”之后，这两个消息的哈希值是相同的。选择前缀攻击包括公共前缀攻击，因此公共前缀的攻击代价小于选择前缀攻击。在马克·史蒂文斯(粉碎的作者)2009年的文章中，此类攻击的计算成本总结在表1中。

表1:1的两种不同攻击的计算成本:md5和sha1

这里的单位是需要计算的哈希数。例如，在2004年之前，对md5的简单攻击(生日攻击)需要强力来计算md5散列到2的64次方。2009年，md5常见前缀攻击的计算成本是md5哈希的2到16次方，sha1是2到52次方。不难看出，普通前缀攻击和选择性前缀攻击都可以应用于共谋冲突攻击。由于常见前缀攻击和选择性前缀攻击的快速发展，共谋碰撞攻击逐渐成为数字签名系统的最大威胁。

计算复杂度与最终构建的碰撞结构密切相关。对于常见的前缀碰撞攻击，王小云教授提出的攻击方法需要构造两个碰撞块。第一个碰撞块是通过生日攻击获得的，以便在计算第一个碰撞块后使散列内部状态的差异满足特定形式。通过搜索差分路径获得第二个冲突块。因此，只需要两个冲突块来构造一个公共前缀冲突攻击。对于选择性前缀冲突攻击，有必要构造多个(> =2)冲突块。第一个碰撞块具有相同的功能，并且在计算出第一个碰撞块之后，后续的碰撞块校正内部状态的差异。在唯一公开的选择性前缀冲突码[2，3]中，该后续冲突块的长度被指定为9，这意味着需要构造9个校正块来完成冲突攻击。长度越短，对每个碰撞块的要求越高，计算所需的时间呈指数增长。当长度为9时，可以在普通计算机上用几个小时完成计算。

对md5冲突的研究主要集中在快速发现md5冲突上。王小云教授的著名工作[7]和谢涛的后续工作[8]使得在短时间内构造短md5冲突成为可能。对sha1最著名的攻击是最近的sha1摇动攻击，这是一种常见的前缀冲突攻击[9]。另一方面，通过使用选择性前缀攻击，我们可以伪造x509格式[10]的ca证书，并构造多个消息的冲突“羊群攻击”，该攻击可用于“预测”任何美国总统选举的结果。另外，对于攻击签名机制，由于签名机制实施不当，也存在一些漏洞和相应的攻击方法。让我们先简单介绍选择性前缀冲突攻击的能力，然后讨论如何使用选择性前缀冲突攻击，最后回顾由于基于哈希的签名机制实现不当而导致的攻击。

3.对于两个给定的不同前缀p1和p2，cpc攻击可以构造两个后缀m1和m2，因此

哈希(p1+m1) =哈希(p2+m2)

p1+m1的长度等于p2+m2的长度。

例如，假设p1=“希拉里将当选”和p2=“特朗普将当选”。在选举之前，cpc攻击被用来构造两个后缀m1和m2，然后计算它们的md5值v=md5(p1+m1)=md5(p2+m2)。然后告诉全世界，这次选举结果的md5值是v。在公布真实结果后，如果希拉里当选，显示p1+m1，否则显示p2+m2，预测就可以完成了。当然，在实际场景中没那么简单。任何看到“xxx当选”后的无意义后缀字符串的人都会有疑问。在实际攻击场景中，经常需要对数据结构进行cpc攻击，并在最后附加附加数据。例如，可以在pe可执行文件、zip压缩文件、jpg图像文件等的末尾添加后缀。，而不影响正常使用。

使用cpc攻击，也可以构造多个消息的冲突。以三条信息为例(图[9]):

Ihv0是md5的默认初始状态。M1/m2/m3是三个不同的前缀，并且在md5操作之后获得三个不同的md5状态(值)ihv1、ihv2和ihv3。此时，cpc用于攻击m1和m2，以生成填充c1和c2，它们具有相同的md5值ihv4。此时，对m3进行普通的补码p3以生成ihv5。然后用来自ihv4和ihv5以及c4和c5的cpc进行攻击。此时此刻

MD5(m1+C1+C4)= MD5(m2+C2+C4)= MD5(m3+P3+C5)

以及len(m1+C1+C4)= len(m2+C2+C4)= len(m3+P3+C5)。

一个公开的cpc攻击源代码是由mark stevens编写的hashclash [2]，它支持cuda加速cpc攻击的生日攻击部分，但是这个代码目前工作不太好。工作代码可以在[11]中找到。由于cuda接口升级，无法正常编译[2，11]中的所有cuda部分。在做了一些修改后，我们在[12]中发布了工作版本，供用户进行实验。

利用[12]，我们构造了两组大小分别为704字节和1048576字节(1mb)的哈希冲突。在我们的双向e5-2650v3服务器上，我们使用30个内核和3个k1200加速卡，我们可以在6小时内得到一组冲突。其中，使用加速卡进行生日攻击不到十分钟。

A.伪造ca证书

马克·史蒂文斯(Marc Stevens)在2009年的工作表明，对ca证书的攻击使用了选择性前缀攻击。图1显示了伪造ca证书的原理。

图1认证证书的伪造过程

图1显示了左边的合法网站证书结构和右边的伪造ca证书结构。攻击时，攻击者可以控制左侧的合法网站证书结构和右侧的伪造ca证书结构。在这里，攻击者需要“猜测”前几个域(序列号/有效期)，但是这种猜测并不难，因为它具有很强的可预测性。通过反复观察颁发证书的机构(反复申请证书)，攻击者发现1。序列号线性增加，为2。有效期是可预测的。因此，攻击者可以计划一个攻击时间，猜测在该时间段内可能出现的序列号的范围，构造其相应的有效期，并构造一批可能的合法证书头作为选择性前缀攻击的消息前缀。对于右侧的伪造ca证书，构造一个合法的ca证书头。接下来，攻击者进行大量计算来计算一批碰撞。然后，在最后完成碰撞，获得一批“合法网站证书”和“伪造的ca证书”，并从“合法网站证书”中取出rsa公钥。最后，在攻击者精心策划的攻击时间，申请网站证书。如果应用的网站证书的序列号/有效期与攻击者预测范围内的某个证书完全匹配，则攻击完成，并生成完全“有效”的伪造ca证书。

2007年，alexander sotirov和marc stevens的团队使用200台ps3主机进行基于md5 cpc攻击的ca证书伪造攻击。每次计算需要1-2天，三次失败后，第四次终于成功。

B.sha1粉碎攻击

今年2月，sha1的碰撞攻击粉碎首次在互联网上发表。粉碎攻击是一种常见的前缀攻击，其显示形式非常直观——两个大小和sha1值相同的pdf文档，但显式效果不同。

图2粉碎攻击示例

这种攻击有两个难点，一是如何完成sha1公共前缀攻击，二是如何利用公共前缀和后缀以及不同的碰撞块构造两个合法的pdf，它们的显示效果是不同的。

第一个问题，马克·史蒂文斯已经研究了好几年。这一次，他加入了谷歌工程师，最终将算法变成了现实。在这次攻击中，他们使用cpu来计算第一块碰撞块，使用gpu来计算第二块碰撞块。第一组碰撞块的第一次碰撞消耗了3583个核心年的计算，第二次碰撞消耗了2987个核心年的计算。在第二阶段，除了cpu，gpu集群用于计算。gpu集群的计算量相当于一年114个k20计算、一年95个k40计算或一年71个k80计算。如果你使用商业云gpu服务，租用71 k80一年将花费56万美元。

对于第二个问题，攻击的结构非常巧妙。我们用热心网民的回答[17]进行分析。首先，粉碎攻击是一种常见的前缀攻击，因此pdf必须有一个通用的pdf头，如图3所示。

图3震荡攻击的pdf结构

两个pdf文件头的共同部分包括:pdf文件头和一部分图像对象。在图像对象中，包括属性表引用、内容结构和属性。该攻击构建了一个巧妙的内容结构，其中包含一个jpeg图像。碰撞块魔术块1和魔术块2位于这个jpeg图片的元数据部分，如图4所示。

图4 JPEG元数据的结构

请注意fffe评论。两个字节ff fe代表注释部分的开始，接下来的两个字节代表注释部分的长度。图4中有两个注释段，第一个段的长度为0x24，第二个注释段的地址0xbd可以通过使用注释段的起始地址0x99+0x24获得。您可以看到在0xbd仍然有一个ff fe标记，它代表另一个注释段的开始。在两个pdf中，此注释部分的长度不同。在第一个pdf中，该长度为0x173(指向0xbf+0x173=0x232)，而在另一个pdf中，该长度为0x17f(指向0xbf+0x17f=0x23e)。0x232的起始位置是一个长段，而0x23e的起始部分是一个非常短的段。之后，有一些精心安排的部分，所有这些部分都具有相同的字节表示，但是在由冲突块的第一个字节引起差异之后，可以表示的结构是不同的，这使得显示的图像不同。

C.攻击网络磁盘的“二次传输”机制

众所周知，网络磁盘的“二次传输”机制可以大大降低文件上传的时间成本。“二次传输”机制通常使用哈希函数生成文件的抽象值作为文件特征值来判断是否可以使用“二次传输”函数。影响“第二次传输”机制的另一个参数是文件大小。大文件通常会触发“二次传输”机制，而小文件可能不会。

这里我们使用网易网络磁盘、115网络磁盘、城市互联网络磁盘、腾讯网络磁盘、中国移动蔡赟网络磁盘、机顶盒和收录机进行测试。除网易网络磁盘外，其他网络磁盘提供txt后缀文件预览功能。我们使用一对704字节的冲突和一对1mb字节的冲突作为实验文件，将它们上传到网络磁盘，并使用下载和预览功能分别下载和预览这两个文件，并测试每个网络磁盘是否能够区分这两个相同大小和相同md5值的文件。结果如下表所示。如果下载的两个文件相同，则证明网络磁盘无法区分这两个文件，我们将测试结果标记为“冲突”，否则标记为“无冲突”。

由此可见，网易网盘、城市联通网盘和蔡赟网盘根本无法区分md5碰撞的文件。

著名的病毒总网站使用md5作为文件复制确定的标准，以减少计算量。但是，在cpc攻击之后，攻击者可以通过在传播恶意文件之前提交善意文件来避免病毒威胁。因此，使用sha256的哈希值作为文件功能，快速修改了virustotal。

目前，许多安全供应商仍然使用md5进行恶意代码识别，这需要额外的重复判断机制。由于md5冲突基本上属于上述的共谋攻击，如果一个样本在相同的md5值下是恶意的，其他样本一般作为攻击的中间环节存在，将所有样本上报给警方也是一种可行的方法。

D.该攻击基于“尾部附加密钥”形式的md5签名

我们首先回顾了上一篇文章[13]中描述的在线支付协议中基于md5的签名机制。以请求“c=c&b=b&a=a”为例。要签署此请求，首先将请求解析为键值对:

{"c":"c "、" b":"b "、" a":"a"}

然后按照关键字的字典顺序进行排序和连接

a=a&b=b&c=c

附加密钥

a = a & b = b & c = c & key =这是秘密

计算md5值

MD5(a = a & b = b & c = c & key = this _ is _ a _ secret)= 0a1d 218 F9 B2 b 029 c 84 c 84458 bb 6 DBC 00

形成最终请求

c = c & b = b & a = a &符号= 0a1d 218 F9 B2 b 029 c 84 c 84458 bb 6 DBC 00

这种请求存在于从支付平台返回给商家服务的支付结果的异步通知中。商家的签约过程通常是这样的:

1.从参数中移除符号字段

2.对剩余参数进行解码，并根据键值按升序排列每个接口的参数；

3.将有序参数链接成键=值&形式的字符串。

4.将密钥“key=token”附加到生成的字符串的尾部，然后执行md5；

5.检查md5值是否等于符号字段。如果它们相等，则证明消息没有被篡改。

这里，我们注意到默认情况下，所有参数在签名时都在参数列表中签名。如果攻击者可以在消息中插入一个字段，那么这个参数就可以包含在签名验证中。由于这种系统的复杂性，这个请求通常很长，包括许多参数和许多层中的嵌套商品信息。一旦攻击者找到要注入的参数或嵌套参数，他就可以控制异步通知的内容。为了描述方便，我们假设攻击者下了两个订单，订单id分别是1704176438和1704176439。并且攻击者可以控制参数“zzz”的尾部内容，例如，以src的形式设置请求:

customerid = 4 & order id = 1704176438 & service = query pay & version = 1.0 & zzz =

在这里，zzz=后面可以跟任何给定的内容，离开空并不影响。攻击者构建另一个请求dst:

customerid = 4 & order id = 1704176439 & service = query pay & version = 1.0 & zzz =

Orderid在这里被简单地修改以演示效果。然后通过cpc攻击计算一组冲突src.coll和dst.coll。因为攻击者可以控制zzz域，所以他向src.coll .支付了真实费用，获得了支付平台的签名，然后简单地将异步通知中的订单号从1704176438修改为1704176439，并将其作为伪造的异步通知提交给商户服务器。由于src.coll和dst.coll的md5值相等，因此src的md5值。coll和dst。因此，伪造的异步通知也是有效的。如果商家服务器不审核账户，但是信任来自支付平台的异步通知，那么攻击者成功地完成了两个订单，一个订单的金额。

此外，针对微软msi不完善的签名机制/双重签名机制的攻击也时有发生，并构建了具有“合法签名”的恶意代码。我们还发现了cpc攻击传播恶意代码的真实例子。感兴趣的读者可以参考[14]。

4.安全使用安全散列签名首先，为了抵抗cpc攻击，您不能简单地将密钥附加到要签名的字符串，而是需要在要签名的字符串前后附加密钥，即计算:

sign = hash(secret 1+string+secret 2)

作为签名。如果它仅附加到报头，它可能会受到长度扩展攻击的影响。如果它只附着在尾部，它可能会受到cpc攻击的影响。但是如果两端都连接，它们就不会受到这两种攻击的影响。这时，为了计算合法碰撞，攻击者不得不使用基于生日攻击的蛮力搜索来攻击。此外，如果秘密被安全地存储在云中，攻击者必须生成大量的网络请求来完成冲突，这很难实现并且很容易被检测到。

如果存在共谋碰撞攻击的可能性，强烈建议在前后增加签名密钥保护，这正是hmac的设计和实现[15，16]。因此，在实际应用中，建议使用hmac扩展算法代替md5/sha算法，即使是sha256。

如果您不能直接升级到hmac-sha256算法，您应该尽可能地消除共谋冲突攻击的机会，并针对固定的哈希值将攻击降级为单向冲突攻击。在共谋冲突攻击(公共前缀攻击和选择性前缀攻击)中，由于冲突块的存在，有必要有足够的自由选择输入。如果能严格限制参与签名的域，并严格检查每个参与签名的域，就能大大消除合谋攻击的潜在机会。

现实世界中有很多例子容易成为同谋。以anysdk为例。Anysdk是第三方sdk访问工具，可以访问许多不同的在线支付平台。Anysdk提供了一个典型的高风险特征码[17]，容易受到共谋攻击:

functionchecksign($data，$privatekey){

if(空($data)||！isset($ data[sign])| |空($privatekey)){

returnfalse

{}

$sign=$data[ sign

//签名不参与签名

未设置($data[ sign

$_sign=getsign($data，$ private key)；

if($_sign！= $符号){

returnfalse

{}

returntrue

{}

getsign函数只负责签名字符串的拼写和哈希计算。可以看出，这段代码对输入字段没有限制，因此攻击者的任何输入都可以进入验证过程。这很危险。使用普通服务器运行几个小时就可以生成并完成md5 cpc的操作，并生成一组md5冲突，可以用来发动攻击，而且成本只有几元电。如果你使用云计算平台，你可以进一步提高速度。因此，这种签名结构，加上有缺陷的签名代码，现在是非常危险的。

下面是一个输入参数验证良好的示例代码，可以最大程度地消除共谋冲突的可能性:

functionchecksign($data，$privatekey){

if(空($data)||！isset($ data[sign])| |空($privatekey)){

returnfalse

{}

$this->参数[ arg1 ]=$data[ arg1

$this->参数[ arg2 ]=$data[ arg2

if(check args($ this-> params)= false){

returnfalse

{}

$sign=$data[ sign

$_sign=getsign($this->params，$ private key)；

if($_sign！= $符号){

returnfalse

{}

returntrue

{}

通过checkargs函数检查params数组各字段的有效性，然后进行签名计算。

实施这些保护措施后，共谋碰撞攻击将接近原始根攻击。目前，估计针对md5的攻击复杂度将超过112位，而针对sha1的攻击复杂度将超过144位。在可见的不远的将来，成本仍然很高，这是普通机构无法承担的。

5.总结关于md5/sha1是否过时的各种讨论已经持续了很多年，但是由于中国的实际情况，md5/sha1仍然存在于我们日常生活的各个方面，更换的过程仍然很长。通过对实际系统中md5/sha1攻击的分析，我们发现在完善签名检查和重复判断机制，尽可能消除共谋冲突后，MD5/SHA1的安全性仍能在短时间内得到保证。然而，这种机制只能给我们一个难得的喘息机会，我们仍然敦促制造商尽快升级到更安全的hmac-sha256。最后，再次强调，所有可能受到长度扩展攻击的数字签名协议(第2.1节)都应该立即升级到第4节中描述的hmac-sha256算法，因为黑色产品很可能已经在享受您的服务。

参考

1 .加密散列函数，en . Wikipedia/wiki/cryptial _ hash _ function

2 .哈斯克拉什项目，win.tue.nl/hashclash/

3 .创建自己的md5冲突

4.md5长度扩展攻击，zh.wikipedia/wiki/长度扩展攻击

5.哈希长度扩展攻击解决方案

6.md5长度扩展攻击原理，blog.nfocus/tech/technology共享/2016/06/27/md5长度扩展攻击原理

7 .如何破解md5和其他散列函数？id=2154601

8 .如何查找md5冲突攻击的弱输入差异，eprint.iacr/2009/223.pdf

9.md5选择的前缀冲突，win . tue . nl/hashclash/chosen prefixcollinations/

10 .创建流氓ca证书，win . tue . nl/hashcash/流氓-ca/

11 .创建自己的md5冲突

12.md5冲突示例代码，github/dingelish/md5-cpc

13.支付安全不能说的东西，百度安全实验室公开号

14.MD5冲突的演变，bobao.360/learning/detail/2577

15 .用于消息认证的键控散列函数，mihir bellare，ran canetti，hugo krawczyk

16 .粉碎组是如何设法为一个看起来与原件相似的pdf创建sha1冲突的？，security . stackexchange/questions/152341/the-breaked-io-group-manage-create-a-sha1-conflict-for-a-pdf-the

17.anysdk签名算法和示例，docs.anysdk/integration/server/payment-notice/

雷锋的特别贡献。严禁擅自转载。详情请参考转载说明。