基于選擇前綴攻擊的哈希函數多文件格式碰撞*

李德剛, 楊 陽, 曾 光

信息工程大學 數學工程與先進計算國家重點實驗室, 鄭州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 文件的碰撞.