哈希游戏- 哈希游戏平台- 哈希游戏官方网站安全hash函数在信息系统中有相当广泛的应用，特别是用于消息签名来保护消息的完整性和不可抵赖性等任务，可以说安全hash函数是现代应用密码学最重要的基石之一。如果安全hash函数出现安全问题，那么整个应用密码体系乃至整个互联网的安全都受到严重影响，包括软件发行、网络支付、设备升级等等。安全hash函数面临的最大技术安全威胁是同谋碰撞攻击，但我们也发现国内不少厂家的自制协议中存在着大量不正确的安全hash应用，导致可以利用简单的方法攻破其防护。近些年随着计算机性能的提高，针对 MD5、SHA1 函数的碰撞攻击研究也进展迅速。而国内由于现实情况，替换MD5/SHA1的代价高昂，很难在短期内能解决。MD5/SHA1 碰撞究竟会对现有的信息系统产生哪些威胁？本文对 MD5/SHA1 的碰撞攻击及其应用场景进行讨论，给出了具体的攻击实例，同时给出了缓解措施。我们指出，在进行严格的约束消除同谋碰撞的条件下，要攻破MD5/SHA1依然是一个非常艰巨的任务。尽管如此，这样的机制只是给了厂商难得的喘息时间，我们依然督促各厂商尽快升级到更安全的HMAC-SHA256。

　　密码学中的安全 hash 函数与普通的 hash 函数有着相当大的区别。在典型数据结构hash_map、hash_set中所用到的hash函数，只需要将key映射为一个索引即可，即使产生了碰撞，也可以采用开散列或者闭散列的方式进行处理。密码学中的安全hash函数[1]要求则严格的多，至少需要满足三个性质：（1）抗碰撞攻击（2）抗原根攻击以及（3）抗第二原根攻击。抗碰撞攻击是指，寻找两个不同的串x和y，使得hash(x)=hash(y)是困难的。抗原根攻击是指，在hash(x)=s中，已知s，求x是困难的。抗第二原根攻击是指，已知hash(x)=s，求一个异于x的串y，使得hash(y)=s是困难的。只有满足了以上三点的hash函数才有资格成为安全hash函数。

　　MD5/SHA1是用途非常广泛的安全hash函数。他们的输入是任意串，输出是128/160bit长的散列值。MD5和SHA1在1992年和1993年被发明出来，在相当长一段时间内，他们被认为是安全的。2004年和2005年，研究者发现了对他们的攻击方法，减少了特定情况下发现碰撞的计算代价。在2007年首次提出了利用MD5碰撞伪造CA证书的理论方法，2008年这种攻击方法得到了验证，攻击者成功伪造了合法的CA证书。而针对SHA1的攻击方法则一直停留在理论中，直到2017年初，对SHA1的成功碰撞攻击才首次公开出来。

　　对于MD5/SHA1更复杂的攻击目前主要有共同前缀碰撞攻击(Identical PrefixCollision)和选择前缀碰撞攻击(Chosen Prefix Collision)。共同前缀攻击是构造两个不同的消息s1和s2，他们由相同的前缀，和不同的尾部“碰撞块”组成。前几天震惊世界的SHAttered攻击是对SHA1进行的共同前缀攻击。选择前缀攻击则是构造两个不同的消息s1和s2，他们不必有共同的前缀，但是经过在尾部附加不同的“碰撞块”后，两个消息的散列值相同。选择前缀攻击是包括共同前缀攻击的，因此共同前缀的攻击代价小于选择前缀攻击。在Marc Stevens（SHAttered作者）2009年的文章中对此类攻击的计算代价总结如表1。

　　这里的单位是需要计算的hash的次数。例如2004年之前，对MD5的平凡攻击（生日攻击）需要蛮力计算2的64次方次md5 hash。在2009年时，对于MD5的共同前缀攻击计算代价是2的16次方次MD5 hash，对SHA1的则是2的52次方。不难看出，无论是共同前缀攻击，还是选择前缀攻击，都可以被应用在同谋碰撞攻击中。由于共同前缀攻击和选择前缀攻击的研究进展迅速，同谋碰撞攻击逐渐成为数字签名体系最大的威胁。

　　计算复杂度和最后构造出的碰撞结构有很大关系。对于共同前缀碰撞攻击，由王小云教授提出的攻击方法需要构造两个碰撞块，第一个碰撞块由生日攻击得到，目的是使得计算完第一碰撞块后的hash内部状态的差分满足特定形式。第二个碰撞块则由对差分路径的搜索得到。因此构造共同前缀碰撞攻击只需要两个碰撞块。对于选择前缀碰撞攻击，需要构造多个（=2个)碰撞块。第一个碰撞块的作用相同，后续的碰撞块则对第一个碰撞块计算完成之后内部状态的区别做逐一修正。在唯一一份公开的选择前缀碰撞代码 [2,3] 中，这个后续碰撞块的长度指定为9，意为需要构造9次修正块，以完成一次碰撞攻击。长度越短，对于每个碰撞块的要求就越高，计算所需的时间也指数级提高。在长度为9时，计算可以在普通计算机上运算几小时即可完成。

　　对于MD5碰撞的研究主要关注与快速发现MD5碰撞。王小云教授的著名工作[7]等，以及谢涛的后续工作[8]等，使得在短时间内构造简短的MD5碰撞成为可能。对SHA1最著名的攻击是最近的SHA1 Shattered攻击，是一种共同前缀碰撞攻击 [9]。另一方面，利用选择前缀攻击，可以伪造X509格式的CA证书 [10]，以及构造多个消息的碰撞“Herding Attack”,可以用于“预测”任何一次的美国总统大选结果。 此外，对于攻击签名机制，还有一些由于签名机制实现不当而产生的漏洞和对应的攻击方法。下面我们简要介绍一下选择前缀碰撞攻击的能力，然后再讨论如何利用择前缀碰撞攻击，最后回顾一下对于基于hash的签名机制实现不当而产生的攻击。

　　举个例子，令p1=“希拉里会当选”，p2=“川普会当选”。在大选之前先利用CPC攻击，构造出两个后缀m1和m2，然后计算他们的MD5值v=MD5(p1+m1)=MD5(p2+m2)。然后告诉世人本次大选结果的md5值是v。在真正结果揭晓后，若希拉里当选，则展示p1+m1，否则展示p2+m2，即可完成预测。当然实际场景下没有那么简单，任何人看到“XXX当选”后面那串毫无意义的后缀字串都会产生质疑。在实际攻击场景中往往需要一个可以在末尾附加额外数据的数据结构上进行CPC攻击，例如PE可执行文件、ZIP压缩文件、JPG图像文件等末尾都可以加入后缀且不影响正常使用。

　　图1左侧是合法的网站证书结构，右侧是需要伪造的CA证书结构。进行攻击时，攻击者可以同时控制左侧的合法网站证书结构，和右侧的伪造CA证书的结构。这里攻击者需要对头部几个域(serial number/validity period)等进行猜测，但是由于很强的可预测性，做这个猜测并不难。攻击者通过对发行证书的机构进行反复观测（反复申请证书），发现1. 序列号是线. 有效期是可预测的。因此攻击者可以计划一个攻击的时间，并猜测那个时间段可能出现的序列号范围，并构造其对应有效期，构造出一批可能的合法证书头部，作为选择前缀攻击的消息前缀。而对于右侧伪造的CA证书，则构造了一个合法的CA证书头部。接下来攻击者就进行大量运算，计算出一批碰撞。接下来再对做出的碰撞进行尾部补全，得到一批“合法网站证书”和“伪造CA证书”，并且从“合法网站证书”中取出RSA公钥。最后，在攻击者精心计划的攻击时间，去申请网站证书。如果申请下来的网站证书的序列号/有效期恰好匹配到攻击者预测范围内的某一个证书，那么攻击就完成了，生成了一个完全“有效”的伪造的CA证书。

　　第一个问题，Marc Stevens已经为此研究数年。这次他联合了Google的工程师终于把算法变成现实。在这次攻击中，他们使用了CPU来计算碰撞块的第一个block，使用GPU来计算碰撞块的第二个block。碰撞块的第一个block的第一次碰撞消耗了3583核-年的计算量，第二次碰撞消耗了2987核-年的计算量。在第二阶段，除了CPU外，还是用了GPU集群进行运算。GPU集群的计算量相当于114块K20计算一年，或是95块K40计算一年，或是71块K80一年的计算量。如果使用商业的云GPU服务，租用71块K80计算一年，就将耗费56万美元。

　　注意其中的FFFE comment处。FF FE 这两个字节代表了comment段的开始，其后的两个字节代表该comment段的长度。在图4中出现了两个comment段，第一个段的长度是0x24，用该comment段的起始地址0x99+0x24可以得到第二个comment段的地址0xBD。可以看到0xBD位置处依然是一个FF FE标签，代表另一个comment段的开始。这个comment段的长度在两份pdf中就不相同了，在第一份pdf中，这个长度是0x173（指向0xBF+0x173=0x232），而在另一份pdf中，这个长度是0x17F（指向0xBF+0x17F=0x23E）。0x232开始的位置是一个很长的区段，而0x23E开始的部分是一个非常短的区段。其后还有一些精心布置的区段，它们的字节表示都一样，但是由碰撞块的第一字节引起差别后，所能表示的结构不同，从而使得显示出来的图像不同。

　　这里我们使用网易网盘、115网盘、城通网盘、腾讯网盘、中国移动彩云网盘、Dropbox进行测试。除了网易网盘外，其他网盘均提供了对txt后缀文件的预览功能。我们使用了一对704字节的碰撞和一对1MB字节的碰撞作为实验文件，将他们上传到网盘中，使用下载、预览功能分别下载、预览这两个文件，测试各个网盘能否区分这两个大小相等而且MD5值相同的文件。结果如下表。如果下载下来的两个文件是相同的，则证明网盘无法区分这两个文件，我们将这个测试结果标记为“冲突”，否则标记为“不冲突”。

　　这里我们注意到：验签时的参数列表默认是对“所有”参数验签。如果攻击者可以在消息中插入一个域，那么就可以使得验签时也包括这个参数。由于此类系统的复杂性，这个请求往往很长，包括很多参数以及嵌套了许多层的商品信息。攻击者一旦找到一个参数或者嵌套的参数可以注入，那么就可以控制异步通知的内容。为了叙述方便，我们假定攻击者下了两个订单，订单Id分别为1704176438和1704176439。而且攻击者可以控制参数“zzz”的尾部内容，例如将请求设置为src的形式：

　　这里只简单修改了orderId以演示效果。然后通过CPC攻击计算得出一组碰撞l和dst.coll。由于攻击者能控制zzz域，于是将src.coll进行真实支付，获得支付平台的签名sign，然后将其异步通知中的订单号做简单修改，从1704176438改为1704176439，作为伪造的异步通知提交给商户服务器。由于src.coll和dst.coll的MD5值是相等的，所以他们在尾部附加上商户的密钥之后做MD5值依然是相等的（MD5碰撞的尾部附加性质）。因此伪造的异步通知也是有效的。如果商户服务器不去查账而是相信支付平台的异步通知，那么攻击者成功的用一个订单的金额完成了两个订单。

　　种种关于MD5/SHA1是否过时的讨论已经持续多年，但是由于国内的实际情况，MD5/SHA1依然存在于我们日常生活的每个方面，要替换的过程依然漫长。我们在对实际系统中的MD5/SHA1进行攻击分析后发现，在完善了验签、判重机制并尽可能消除同谋碰撞后，其安全性短期之内还是可以得到保证的。尽管如此，这样的机制只是给了我们难得的喘息时间，我们依然督促各厂商尽快升级到更安全的HMAC-SHA256。最后再次强调，所有可能被长度扩展攻击的数字签名协议（节2.1）应该立即升级成第四节中所述的HMAC-SHA256算法，因为很有可能黑产已经在享用你的服务了。