基于选择前缀攻击的哈希函数多文件格式碰撞*

李德刚, 杨 阳, 曾 光

信息工程大学 数学工程与先进计算国家重点实验室, 郑州450000

1 绪论

哈希函数用于各种安全应用和协议进行消息签名构造和完整性检验, 它的一个重要的功能就是能够进行消息压缩, 即可以将任意长度的消息映射为固定长度的比特串输出.对于任意的哈希函数, 它可以将任意长度的消息串映射到一个固定长度的消息空间中, 记为该消息的哈希值.

目前存在着众多哈希函数, 其中MD5[1]和SHA-1[2]因具有良好的抗碰撞性, 曾被NIST 作为安全标准广泛应用于军事、商业等领域.由于哈希函数的广泛应用, 这些函数算法的攻击一直是密码学家研究的重点.在过去的20 多年时间里, 针对MD 结构哈希函数安全性研究取得了一系列的成果[3–9].目前针对哈希函数的攻击方法有原像攻击、第二原像攻击和随机碰撞攻击.本文主要介绍随机碰撞攻击方法, 并给出该攻击在不同文件格式下的实际应用.

MD5 是1992 年由Rivest 设计用来替代MD4 函数的升级算法[1], 也是曾被广泛使用的密码哈希函数之一.1996 年欧密会上, Dobbertin 实现了全轮MD5 算法的free-start 碰撞攻击[9].该攻击通过取消MD5 算法中IV 值的限制来削弱函数的安全性, 降低攻击的复杂度, 因此得到的碰撞块并不能被应用于实际的文件碰撞.2004 年, 王小云等给出了MD5 算法全轮的随机碰撞消息对[3].文献[3] 利用模差分的思想构造了非线性差分路径, 并结合消息修改技术进一步提高差分路径的成立概率.最终给出MD5 相同前缀的近似碰撞攻击复杂度为239, 攻击时间在15 分钟到1 个小时之间.随着更多的消息修改技术被引入,MD5 的近似碰撞攻击复杂度进一步降低.2006 年, Klima 引入了隧道的概念[10], 来替代多消息修改技术.隧道比传统的消息搜索加速技术更具有通用性, 在王小云提出的差分路径框架下, 利用隧道技术可以平均每31 s 产生一个MD5 的碰撞, 且该方法可用于SHA-1 碰撞搜索加速.

2012 年, Stevens[11]实现了MD5 差分路径的自动构造以及隧道的自动化搜索, 将相同前缀攻击复杂度降为216.同时他还实现了针对MD5 的选择前缀攻击, 能针对给定任意不同的两个前缀来实现MD5的碰撞, 复杂度为239.相比于相同前缀攻击, 选择前缀攻击的应用范围更加广, 攻击结果便于应用转化.

相比于MD5 算法, SHA-1 算法的运算轮数更多, 而且消息扩展方式更加复杂, 攻击复杂度更高.在2005 年CRYPTO 会议上, 王小云[12]给出了针对SHA-1 算法的复杂度为269的碰撞攻击结果, 这是第一个将复杂度降到生日攻击以下的工作.2013 年, Stevens[13]提出了一种“联合碰撞分析技术”, 该技术可给出理论上寻找碰撞的最大概率及数目最少的充分条件集, 得到的复杂度为261的随机碰撞攻击和277.1的选择前缀碰撞攻击.2017 年, Stevens 等人[14]在消息搜索阶段使用了GPU 框架,最终以263.1的复杂度给出了SHA-1 的第一个全轮碰撞, 并构造了两个SHA-1 值相同而内容不同的PDF 文件.SHA-1选择前缀攻击的实现是在2020 年, Leurent 等人[15]在Stevens 等人的基础上扩大了近似碰撞的输出差分集合, 攻击复杂度约为263.4, 并利用选择前缀攻击的结果完成了PGP 格式的证书伪造.

随着碰撞攻击的发展, 出现了越来越多的攻击应用技术.其中相同前缀攻击主要用于实现同一文件类型的碰撞.2014 年, Albertini[16]等人构造SHA-1 近似碰撞攻击时取消了后三轮函数常量的限制, 得到了大量SHA-1 的伪随机碰撞消息.利用这些碰撞消息他们分别给出了PE 文件、JPEG 和RAR 文件的伪SHA-1 碰撞.Stevens 利用得到的SHA-1 相同前缀碰撞[14]实现了任意两个PDF 文件的碰撞.

虽然针对SHA-1 算法攻击的路径构造以及消息搜索技术在不断改进[17], 但是攻击复杂度仍然过高,自动化程度较低, 很难进行大规模应用.除此之外, 目前针对SHA-2 系列的碰撞攻击仍在减轮阶段[18],无法实际应用.目前关于选择前缀碰撞攻击的实例应用更多的集中在MD5 算法上.利用选择前缀碰撞来针对特定的文件头部进行碰撞搜索, 从而实现例如PE-JPEG、PE-PDF 等不同文件格式类型的MD5 碰撞[19].本文总结了目前已有的哈希函数的随机碰撞应用, 并给出了新的碰撞应用.利用了两次选择前缀碰撞来构造一般性的碰撞前缀, 可以得到三种不同文件类型即MP3、JPEG 和PDF 的MD5 碰撞实例, 且该碰撞应用的复杂度可以忽略不计.

本文章节安排如下, 第1 节介绍哈希函数的研究背景以及攻击现状, 第2 节介绍哈希函数及两种近似碰撞攻击, 第3 节介绍现有的碰撞攻击应用, 第4 节给出一种新的碰撞应用, 利用选择前缀攻击构造三种不同类型文件的碰撞, 实现了MD5 算法的碰撞实例并对SHA-1 算法碰撞实例复杂度进行分析, 第5 节总结全文.

2 基础知识

本节介绍主要哈希函数的一般性定义以及针对哈希函数的近似碰撞攻击.

2.1 哈希函数

哈希函数H(M) 作用于一个任意长度的消息M, 返回的n比特长度的哈希值h, 即满足下面的映射关系H:M ∈{0,1}∗→h ∈{0,1}n.MD 结构的哈希函数是哈希函数中一类非常重要的函数, 成员包括MD4、MD5、SHA-0、SHA-1、SHA-2 以及我国商用杂凑标准SM3 等.

MD 结构是Damgård[20]和Merkle[21]在CRYPTO 1989 上同时独立提出的一种杂凑函数设计方法, 该结构利用固定输入长度的压缩函数迭代的方法达到压缩任意输入长度的效果.MD 结构如图1 所示,在计算消息M的哈希值之前, 需要对消息M进行填充, 使其比特长度满足512 的整数倍.然后将消息M分割成K个长度为512 的比特串{M0,M1,···,MK−1}.使用K个长度为512 比特的消息块Mi逐步迭代更新哈希链初始值IHV0, 最终得到的哈希链值IHVK即为消息M的哈希值.

图1 MD 结构杂凑函数Figure 1 Hash function with MD structure

2.2 近似碰撞攻击

近似碰撞攻击主要针对哈希算法中的压缩函数Compress 进行攻击.对于给定的两个初始值IHV0和IHV′0, 通过构造差分路径搜索满足路径给定差分δIHVout= IHV′out−IHVout的消息块B和B′.利用这种技术可以延伸出两种搜索哈希函数碰撞的攻击方式, 一种是IHV0= IHV′0的相同前缀攻击, 另一种是指定两个不同的前缀, 即IHV0̸= IHV′0的选择前缀攻击.其中相同前缀攻击可以看作选择前缀攻击的一种特殊的情况, 所以攻击难度一般要低于相同前缀攻击.

2.2.1 相同前缀碰撞

相同前缀攻击是计算两个长度相同的消息序列{M0,M1,···,Mi−1}和{M′0,M′1,···,M′i−1}作为输入, 利用压缩函数迭代计算消息序列得到两个相同中间哈希链值IHVi和IHV′i的碰撞方法.显然两个相同消息序列就可以满足条件IHVi= IHV′i.利用该攻击, 可以通过添加后缀的方式来对任意消息P构造碰撞.首先对于任意的前缀P, 可以先在后面填充随机比特串Sr, 使得填充后的P||Sr长度满足512 的整数倍.然后将填充后的前缀P||Sr分割成i个长度相同的512 比特的消息块序列{M0,M1,···,Mi−1}.为了降低攻击的复杂度, 一般会使用两对连续的消息块序列{B0,B1}和{B′0,B′1}来产生碰撞, 其中B0̸=B′0,B1̸=B′1.将攻击得到的消息块序列{B0,B1}和{B′0,B′1}添加到前缀P||Sr之后计算得到的哈希值IHVi+2= IHV′i+2, 从而就得到了两个消息M=P||Sr||B0||B1和M′=P||Sr||B′0||B′1, 其中M ̸=M′, 但H(M)=H(M′).同时由于M和M′具有相同的哈希值, 因此在添加任意后缀S后得到的消息M||S以及M′||S哈希值仍然相同.攻击流程如图2 所示.

图2 杂凑函数相同前缀碰撞攻击流程图Figure 2 Identical-prefix attack of hash function

从图2 中可以看出, 相同前缀攻击包括两次近似碰撞攻击来分别产生消息块{B0,B1}和{B′0,B′1}.两次近似碰撞攻击中使用到的差分路径的输出差分相反, 从而保证模加后可以抵消差分.记δIHVi+1=H(IHV′i,B′0)−H(IHVi,B0), 根据 MD 结构哈希函数的迭代的特点,δIHVi+2=H(IHV′i,B′1)−H(IHVi,B1)+δIHVi+1=0.这样两块消息降低了差分路径构造难度, 同时也可以抵消差分实现碰撞.

MD5 的相同前缀攻击由王小云首次实现[3].在对MD5 算法进行密码分析时, 将异或差分和模差分结合起来构造差分路径.通过这种方法得到的路径能够更加清晰地展示差分在压缩函数中的传递, 进而保证输出差分的一致性.文献[3] 通过差分路径推导出一系列被称为充分条件的等式, 在这些等式满足的情况下, 可以保证差分路径成立.充分条件主要用于加速搜索满足差分路径的消息块.首先, 在验证消息块是否满足差分路径时, 只需要验证消息块是否满足路径上的充分条件即可, 这样可以减少计算量并提高单位时间的搜索速度, 这种方法又称为提前终止技术.其次可以通过某些技术手段, 例如单消息修改、多消息修改技术使消息满足部分充分条件, 提高路径成立的概率.

SHA-1 的相同前缀碰撞攻击流程和MD5 类似, 同样需要构造两次近似碰撞攻击来抵消引入的差分.为了提高路径成立的概率, Stevens 在构建路径时提出了联合碰撞分析技术[13], 并且在消息搜索阶段使用了Boomerang 技术和中立比特等消息搜索加速技术, 在GPU 平台上实现了SHA-1 的相同前缀碰撞[14].相同前缀碰撞要求起始差分δIHVi为0, 其使用范围受到较大局限.随后Stevens 提出了应用范围更广、危害更大的选择前缀攻击.

2.2.2 选择前缀碰撞

选择前缀攻击以任意两个指定的消息前缀P和P′作为输入, 通过在后面级联后缀S和S′来实现哈希函数的近似碰撞, 即根据给定的前缀P和P′去搜索满足H(P||S)=H(P′||S′) 的比特串S和S′.

类似于相同前缀碰撞, 在实施攻击之前需要对前缀进行填充保证长度一致.不同的是在进行攻击之前需要对填充后消息前缀的部分比特Sb进行生日搜索.这一步的目的是为了控制选择前缀碰撞的攻击的起始差分来降低后续攻击的复杂度.完成生日搜索后, 就开始通过近似碰撞攻击逐步构建差分路径.在构建差分路径时, 要求输出哈希值的差分δIHVout权重要低于输入链值的差分δIHV0, 逐步将差分权重降为0, 最终实现碰撞.一般进行一次选择前缀攻击需要两次以上的近似碰撞攻击, 所以选择前缀攻击复杂度要高于相同前缀碰撞.选择前缀攻击流程如图3 所示.

图3 MD 结构杂凑算法选择前缀碰撞攻击流程图Figure 3 Chosen-prefix attack of hash function

3 杂凑函数攻击应用

本节主要介绍目前已有的利用近似碰撞攻击得到的实际碰撞应用.首先介绍利用MD5 的相同前缀攻击来构造相同文件格式的碰撞.

3.1 相同前缀碰撞攻击应用

利用相同前缀碰撞, 结合特定的文件格式可以实现针对某一类特定文件类型的通用性的碰撞.

3.1.1 JPEG 文件的碰撞撞

JPEG (joint photographic experts group) 由国际标准化组织(ISO) 制订, 是最常用的图像文件格式, 后缀名为.jpg 或.jpeg.

JPEG 文件由段组成, 长度和数量固定, 需要根据段中的信息来确定.JPEG 文件的段一般包含两个部分, 一个是段的标识, 由两个字节构成FF XX, 其中第一个字节FF 为固定值, 表示段的开始, 第二个字节XX 为变量, 根据第二个字节XX 的内容来确定段的含义.然后后面两个字节记录了段的长度, 因此JPEG 中段的长度取值范围为0–65 535 字节.

JPEG 标准规定JPEG 文件的开始两个字节为FF D8.文件结束的标志为FF D9, 当计算机读取到文件结束的标志时, 便不再继续向后编译.除此之外, JEPG 文件中还有一种特殊的段为注释段, 该段中的内容将被编译忽略.JPEG 碰撞应用就是通过利用相同前缀碰撞中的两个近似碰撞消息之间的差异, 改变注释段的长度实现相同的文件后缀展现不同内容.

如图4 所示, 以文件前缀作为相同碰撞攻击的前缀, 构造近似碰撞攻击消息块.在构造时要求消息的前两个字节存在差分, 即图中字节1 部分.字节1 中的两个字节表示注释段1 中的长度.在构造碰撞后,两个JPEG 文件的注释段1 长度不同, 控制第一个碰撞块的所在的文件从注释段2 开始解析, 根据注释段2 的长度为06, 因此后面的字节FF FE X2X2 Y2Y2 会被注释.这样应用程序直接读取JPEG1 的数据一直到标志FF D8 结束解析, 如图4 中的虚线箭头所示, 文件1 显示图片1 的内容.由于两个文件的字节1 (XX YY) 存在差分, 通过填充字节的方式控制文件2 从字节FF FE X2X2 Y2Y2 开始解析.将JPEG 的长度储存在字节X2X2 Y2Y2 中, 这样应用程序在解析时就会跳过JPEG1 的数据段从JEPG2数据段开始解析, 如图4 中的实线箭头所示, 此时文件2 显示的就是JPEG2 的内容.

图4 利用相同前缀攻击实现JPEG 文件的哈希碰撞Figure 4 Hash collision for JPEG files using identical-prefix attack

从图5 可以看出, 碰撞的文件结构和两个JPEG 文件的内容没有直接关联, 因此可以将JPEG1 和JPEG2 替换为任意不同的两个图像文件, 即可以实现任意两个JPEG 文件的碰撞.

图5 哈希值碰撞的图片文件结构图Figure 5 Structure of JPEG file with hash collision

3.1.2 PDF 文件的碰撞

目前针对PDF 的文件碰撞可分为两类, 一类是利用JPEG 中的注释段来构造文件碰撞.由于PDF本身可以储存JPEG 文件, 因此可以先将PDF 文件保存成JPEG 文件, 然后重新嵌入到空白的PDF中.通过3.1.1 节中的方法构造相同前缀攻击实现任意两个PDF 文件的碰撞.该方法被Stevens 等人用于构造SHA-1 碰撞的PDF 文件[14].但是这种方法本身存在缺陷.一是碰撞的文件不能过大, 否则生成的JPEG 文件长度超过65 535 个字节就无法成功产生可用的碰撞文件, 二是文件格式的改变存在一定程度上的失真.另一类攻击方式是基于PDF 文件结构设计的碰撞, 该方法可以实现任意大小的PDF 文件碰撞.如图6 所示, PDF 文件本身由一个个对象构成, 对象的编号构成一个树状结构.在解析时根据根目录的内容去引用不同的对象来显示对应内容, 没有引用的对象就不显示.

图6 PDF 文件树状结构Figure 6 Tree structure of PDF file

可以通过构造相同前缀碰撞来使得root 指向两个不同的文件目录来达到显示不同文件内容的目的.首先要将两个PDF 文件的内容全部储存在一个PDF 文件中, 通过控制文件目录的对象来确定要显示的文件内容.如图7 所示, 在进行相同前缀攻击时预先给定碰撞消息B的前4 个字节为“≪Pages 1 0 R”,这样可能会一定程度减少消息的搜索空间, 但是整体影响不大.然后在前四个字节之中设置差分, 使第二块碰撞消息B′前四个字节为“≪Pages 5 0 R”.在完成相同前缀攻击后, 得到图7 中的两个PDF 碰撞文件, 两个文件的后缀一样, 但是根目录指向了不同的文件目录, 显示的内容也会不一样.

图7 利用相同前缀攻击构造PDF 文件碰撞Figure 7 Use identical-prefix attack to construct hash collision of PDF files

3.1.3 Shell Script 脚本文件的碰撞

Shell script 是通过shell 的功能所写的一个program,这个程序是使用纯文本文件,将一些shell 的语法与命令写在里面, 搭配正则式、管道命令和数据流重定向等功能.通过利用脚本程序本身的一些if-else判断结构可以实现两个shell 脚本的碰撞.如图8 所示, 首先利用脚本文件的注释功能将相同前缀碰撞得到的两个不同的消息块B和B′注释掉以保证程序的正常运行.然后使用if-else 函数去比较消息块B和B′之中的差异.因为消息块B ̸=B′, 所以必然存在字节可以使脚本1 和脚本2 执行不同的分支.

图8 利用相同前缀构造攻击shell script 文件碰撞Figure 8 Use identical-prefix attack to construct hash collision of PDF files

图8 框架可实现两个脚本文件的碰撞.碰撞后的脚本执行的功能不同, 但是拥有相同的哈希值.Albertini[16]利用这种方法展示了SHA-1 算法的shell 脚本文件的伪碰撞.

3.1.4 RAR 压缩文件碰撞

RAR 文件允许标志出现在文件任意偏移位置.RAR 文件的标记块(MARK_HEAD) 数据为52 61 72 21 1A 07 00.计算机从文件的开头开始一直读取到标记块, 然后解析标记块后面的内容到结尾块, 解析结束.RAR 文件结尾块也是一个固定字节串的块, 依次是C4 3D 7B 00 40 07 00.利用近似碰撞攻击可以构建两个碰撞的文件头, 一个文件头的RAR 标记块是可用的, 而另一个文件的标记块不可用.通过这种方法, 可以获得任意两个RAR 文件的碰撞消息.

图9 是Albertini[16]构建的RAR 文件的关于SHA-1 算法的伪碰撞.其中文件的0000h-0030h 均为近似碰撞消息块, 且消息块的最后一个字节存在差分, 碰撞后面是两个不同的RAR 文件级联在一起.这使得RAR1 文件能够解析第一个RAR 文件(红色标识之间的数据).而RAR2 文件无法解析第一个RAR 文件, 因为标记块被破坏, 而只能解析第二个RAR 文件(绿色的标识之间的数据), 从而呈现不同的内容.

图9 利用相同前缀构造RAR 文件碰撞Figure 9 Use identical-prefix attack to construct hash collision of RAR files

以上总结了相同前缀碰撞攻击应用实例.上述碰撞应用具有通用性, 即只需经过一次相同前缀攻击, 就可以实现针对该类型任意文件的哈希碰撞.但是相同前缀碰撞本身不能很好地控制差分的位置.如3.1.2 节中, 相同前缀攻击往往只能控制碰撞消息块B中靠前的消息比特.如果希望差分出现在碰撞消息块靠后位置的话, 消息搜索加速技术的使用会受到影响, 导致搜索速度下降, 难以找到碰撞的消息块.

3.2 选择前缀碰撞攻击应用

利用选择前缀碰撞, 可以更加方便控制消息中的差分, 实现针对更多文件类型的碰撞攻击.

3.2.1 PE 文件的碰撞

PE (portable executable) 文件是在Windows 系统上的可执行文件(.exe 文件) 标准格式.PE 文件是在原有的DOS EXE 文件格式的基础上发展来的, 因此继承了DOS 的MZ 标识(4D5A).然而在PE文件格中该标识的作用非常有限, 仅仅用于记录PE 文件头在整个EXE 文件中的偏移.DOS 头必须在文件的起始位置, 不能存在偏移且长度固定.PE 文件的结构如图10 所示, 从起始位置依次是DOS 头、NT头、节表以及节.

图10 PE 文件结构示意图Figure 10 Structure of PE files

NT 文件头的偏移地址指针位于DOS 头的尾部(图10 中的虚线框部分), 如果在使用相同前缀攻击时指定消息块中靠后部分的比特取值, 会导致在消息搜索时隧道数量减少, 攻击复杂度大幅提高.因此使用相同前缀碰攻击在指针处引入合适差分很难实现.使用选择前缀攻击可以解决上述问题, 实现PE 文件的碰撞.攻击中用到的前缀为图10 中的DOS 文件头(灰色部分), 通过预先指定NT 头的偏移来控制PE 文件的内容.在找到碰撞后, 将碰撞消息添加到前缀后面, 然后按照之前指定地址确定NT 头在PE 文件中的偏移.最终只需要修改节表中的各节中的地址即可.

攻击示意图如图11 所示, 利用选择前缀攻击指定两个PE 文件NT 头的偏移地址, 然后通过选择前缀攻击实现碰撞.在实现碰撞之后, 修改两个PE 文件的NT 文件头的位置, 使其分别和DOS 头中的偏移地址对应.中间空余部分用随机字符填充, 每个NT 文件头会记录文件头和后面所附节表的长度, 不会解析填充的字符.如图11 所示, 在左边的PE 文件中, DOS 头尾部的指针指向了NT 文件头1, 右边的PE文件指向了NT 文件头2.

PE 文件储存数据的物理地址记录在NT 头后面的节表中, 因此还要修改NT 文件头后面的节表, 使其能够指向对应的文件数据.从图11 中看出, 两个文件的后缀是相同的, 既包含File1.exe 的数据, 也包含File2.exe 的数据.但是NT 文件头1 指向了File1.exe 的地址, NT 文件头2 指向了File2.exe 的地址.因此左边的文件功能和File1.exe 文件一致, 而右边的文件功能和File2.exe 文件一致.这样就实现任意两个PE 文件的碰撞.

3.2.2 JPEG-PE 文件的碰撞

选择前缀碰撞可以应用于多类型的文件碰撞.如利用选择前缀碰撞可以实现JPEG 文件和PE 文件的碰撞.首先要确定碰撞的前缀, 这里分别是PE 文件的DOS 头和JPEG 文件的开头.在得到碰撞后将NT 头添加到碰撞之后, 再依次添加JPEG 数据, 以及PE 应用程序的数据.

如图12 所示, 在PE 前缀中NT 头的偏移为00 00 02 40 h , 在JPEG 文件前缀中注释段的长度为04 fc h.在解析JPEG 文件时, 计算机能够跳过NT 文件头, 从偏移量为500 h 的地方读取数据.对于PE 文件, 根据DOS 头的信息直接跳转到NT 头, 根据NT 头以及后面节表的信息定位PE 文件的数据.这样通过一次选择前缀碰撞就实现了PE 文件和JPEG 文件的碰撞.值得注意的是, 该框架可以实现任意PE 和JPEG 文件的碰撞.

选择前缀攻击技术不仅可用于实现不同身份的签名证书碰撞[15,22],还可以实现PE-PDF、PDF-PNG等更多文件类型的碰撞, 使用多次选择前缀碰撞还可以实现两个以上的文件类型碰撞, 这里不再介绍.

4 基于选择前缀攻击的多文件类型的哈希碰撞

本节给出一种新的针对MD 结构哈希函数碰撞攻击应用.通过调用两次选择前缀攻击, 实现对MP3文件、JPEG 文件和PDF 文件的哈希值碰撞.为了验证方法的可行性, 给出了MD5 算法的碰撞实例, 并分析了SHA-1 算法的碰撞复杂度估计.JPEG 和PDF 文件结构已介绍过, 这里介绍MP3 文件结构.

MP3 (MPEG audio layer 3) 是ISO/MPEG 标准的一部分.MP3 数据由多个帧组成, 帧是MP3 文件最小的组成单位.每个帧由帧头、附加信息和声音数据组成.如图13 所示, MP3 文件大体上可以分为三个部分: ID3V2、音频数据和ID3V1.其中ID3V2 位于文件的首部, 包含作者、作曲、专辑等信息, 长度不固定, 需要根据标签头来计算长度.

图13 MP3 文件结构Figure 13 Structure of MP3

4.1 实现MP3 和JPEG 文件的碰撞

ID3V2 由一个10 字节的标签头和若干标签帧组成.每个标签帧都有帧头, 长度为10 字节, 里面记录了标签帧的内容以及帧的大小.标签帧包括标题、作者、专辑、音轨格式、备注格式等, 这些信息并不影响文件的正常播放.ID3V2 后面为音频数据, 由帧头、CRC 通道信息和声音数据组成, 每个帧播放0.026 s.在构建MP3 和JPEG 文件的碰撞时, 为了防止嵌入MP3 文件时JPEG 文件的结构被破坏, 考虑直接将MP3 文件嵌入到JPEG 文件的注释字段中.

在构建MP3 文件碰撞时, 考虑在标签帧中插入选择前缀攻击得到的消息块并结合JPEG 文件的注释段来实现碰撞.如图14 所示, 字节49 44 33 对应的ASCII 值为ID3, 字节43 4F 4D 4D 为MP3 文件标志帧中备注帧(COMM) 的标识, 该帧内容并不会影响实际的音频数据播放.因此可将得到的选择前缀碰撞消息块添加到备注帧之后, 这样在解析MP3 文件时就会越过碰撞的消息块, 正常读取MP3 文件.在解析完音频文件后, MP3 文件后的JPEG 文件会被视作说明信息被播放器忽略.

图14 MP3-JPEG 文件哈希碰撞Figure 14 Hash collision for MP3-JPEG files

在构建对应的JPEG 文件时, 直接利用文件的注释段将无关信息包括碰撞消息块和MP3 文件的数据注释掉.这样就实现了JPEG 文件的正常解析.需要注意的是, 前面提到过JPEG 格式的文件中注释段FF FE 的长度不能超过65 535 个字节, 然而单个MP3 文件长度通常在MB 级别, 因此仅仅通过一个注释段并不能实现整个MP3 文件的注释.为了解决这个问题, 在MP3 音频文件中插入新的注释段来分割文件.插入注释段有两种方式, 一种是在文件中直接插入注释段标志, 然后将所有文件向后偏移.另一种方法如图15 所示, 通过替换掉某些音频帧的数据, 从而避免文件的偏移.

图15 在MP3 文件中插入JPEG 文件注释段Figure 15 Insert comment segments of JPEG file in MP3 files

经过实验对比, 第一种方法会影响过多的音频帧, 从而导致MP3 在播放时不能正常播放出现杂音.第二种方法虽然会破坏部分音频帧的内容, 但是对整体来说影响很小(每帧播放时间仅为0.026 s), 基本可以忽略不计.因此用第二种方法来分割MP3 文件可以解决MP3 文件过大的问题.结合第二种方法和一次选择前缀碰撞就实现了任意MP3 文件和JPEG 文件的哈希函数碰撞.

4.2 JPEG 和PDF 文件的碰撞

针对利用选择前缀碰撞实现JPEG 文件和PDF 文件碰撞的方法, 在设计后缀时, 将JPEG 的数据放置在图16 中的流对象(stream) 里.流对象是用字节表示的序列, 没有长度限制, 包含在stream 和endstream 之间.

图16 PDF 文件中的流对象结构Figure 16 Stream object in PDF files

具体做法是将JPEG 文件放在PDF 文件之前, 即文件结构为P||B||JPG||PDF 和P′||B′||JPG||PDF.其中P和P′分别为JPEG 文件和PDF 文件的前缀, 而B和B′为选择前缀攻击得到的消息块, 后面依次为JPEG 文件和PDF 文件.这是由于PDF 在解析时是从下向上解析的, 即需要从底部的Trailer 对象中读取交叉阴影表和Root 对象, 进而才能解析整个文件.攻击结构图见图17.

图17 PDF-JPEG 文件的哈希函数碰撞Figure 17 Hash collision for PDF-JPEG files

在JPEG 文件中使用注释段直接跳过了选择前缀碰撞攻击消息块B, 由于消息块B的长度要远远低于655 535 个字节, 因此不用考虑注释段是否过长的问题.对于PDF 文件, 消息块B′和JPEG 文件内容被放在流对象1 0 obj 中.当从PDF 文件底部向上解析时, 应用程序根据根目录索引跳过流对象1 0 obj 的内容并直接读取对象2 0 obj 中的内容.

4.3 MP3-JPEG-PDF 文件的碰撞应用

本节将前两节的内容结合起来, 同时给出三种不同文件类型的哈希碰撞, 同时只需要调用两次选择前缀碰撞攻击.首先构建MP3 和JPEG 文件的选择前缀攻击, 选择的前缀分别为表1 和表2.

表1 JPEG 文件前缀P1Table 1 Prefix of JPEG P1

表2 MP3 文件前缀P2Table 2 Prefix of MP3 P2

利用选择前缀攻击, 可以得到碰撞消息B和B′满足Hash(P1||B) = Hash(P2||B′).然后以P2||B′为前缀记为P3 和表3 中PDF 文件的前缀P4 进行选择前缀攻击.在碰撞攻击之前需要对P4进行预处理, 随机填充一些字节使其长度和P3 一致.利用选择前缀攻击得到消息块B2 和B2′满足Hash(P3||B2)=Hash(P4||pad||B2′), 其中pad 为填充字节.消息块B2 和B2′显然也满足等式(1).

表3 PDF 文件前缀P4Table 3 Prefix of PDF P4

这样就通过两次选择前缀攻击实现了三个文件前缀的碰撞.图18 是结合前两节的内容给出MP3-JPEGPDF 三种文件的碰撞结构.只要能够实现选择前缀攻击, 该方法可实现任意MP3-JPEG-PDF 类型的文件, 且时间复杂度忽略不计.

图18 MP3-PDF-JPEG 文件哈希函数碰撞Figure 18 Hash collision for PDF-JPEG files

4.3.1 MP3-JPEG-PDF 文件的MD5 碰撞

4.1–4.2 节介绍了如何利用选择前缀攻击实现MP3-JPEG-PDF 三种文件的碰撞.为了验证方法的可行性, 利用现有的MD5 攻击工具HashClash[23]项目来实现选择前缀攻击.按照4.3 节的方法, 我们在80 线程的服务器上调用两次选择前缀攻击, 第一次攻击时间为150 min, 第二次攻击时间为122 min.两次攻击得到的消息块如表4 和表5 所示.

表4 第一次选择前缀攻击搜索的消息块Table 4 Message blocks for first chosen-prefix attack

表5 第二次碰撞攻击搜索的消息块Table 5 Message blocks for second chosen-prefix attack

相关代码和攻击得到的碰撞实例可以从 https://github.com/dragonlaaa/PDF-JPG-MP3-COLLISION-OF-MD5.git 下载.图19 中给出了碰撞文件的验证结果.

4.3.2 MP3-JPEG-PDF 文件的SHA-1 碰撞

由4.3 节的内容可以知道, 实现碰撞复杂度最高的地方集中在两次选择前缀攻击上, 其余时间复杂度基本可以忽略不计, 故实现SHA-1 碰撞应用的复杂度取决于SHA-1 选择前缀的复杂度.

相比于MD5 算法, SHA-1 的选择前缀攻击还不够成熟, 缺少自动化的工具.目前, 针对SHA-1 的首次选择前缀攻击是由Peyrin 等人[15]于2020 年实现, 其利用选择前缀攻击构建了两个PGP 密钥, 密钥的SHA-1 值是相同的但是身份签名不同.论文给出的攻击复杂度为263.4, 需要使用900 张Nvidia GTX 1060 显卡, 花费大约2 个月的时间.由于实现MP3-JPEG-PDF 文件碰撞需要两次选择前缀攻击, 所以实现MP3-JPEG-PDF 文件的SHA-1 碰撞复杂度大约为264.4.

5 总结

本文的重点在于MD 结构的哈希函数碰撞攻击在实际文件中的应用.我们在相关工作的基础上进一步给出了新文件类型的哈希函数碰撞.通过调用两次选择前缀攻击, 实现了PE-JPEG-PDF 三种文件类型的碰撞.利用已有的攻击工具实现了MD5 的三种文件碰撞应用, 总用时约为272 分钟.本文提出的碰撞方法具有通用性, 即在完成相同前缀攻击或选择前缀攻击后就可以实现任意文件碰撞.对于其它MD结构的哈希算法, 该方法通过合理选择前缀, 进行两次选择前缀攻击后同样能实现任意三个PE、JPEG和PDF 文件的碰撞.