基于圖論方法的SHA-1 差分路徑的精準(zhǔn)概率計(jì)算*

李婧瑜, 楊 陽,2, 曾 光, 李德剛

1. 中國人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室, 鄭州 450001

2. 中國科學(xué)院 軟件研究所 可信計(jì)算與信息保障實(shí)驗(yàn)室, 北京 100190

1 引言

SHA-1 算法由美國國家安全局[1]設(shè)計(jì), 1994 年被美國國家標(biāo)準(zhǔn)與技術(shù)研究院(NIST) 發(fā)布作為聯(lián)邦信息處理標(biāo)準(zhǔn)(FIPS), 該算法一經(jīng)提出就受到各國密碼學(xué)家的廣泛關(guān)注. 2005 年, 王小云教授[2]通過模差分攻擊技術(shù)和消息修改技術(shù)把對SHA-1 隨機(jī)碰撞攻擊的復(fù)雜度降到了269, 這也是首次將SHA-1 隨機(jī)碰撞攻擊的復(fù)雜度降到生日攻擊以下. 隨后, 很多團(tuán)隊(duì)嘗試?yán)迷摲椒▽p輪的SHA-1 算法進(jìn)行碰撞攻擊[3–6]. 直到2017 年, Stevens 與Google[7]宣布了一個(gè)成功的SHA-1 碰撞攻擊, 并且發(fā)布了兩份內(nèi)容不同但SHA-1 散列值相同的PDF 文件作為證明. 這是目前為止對SHA-1 的最好的隨機(jī)碰撞攻擊結(jié)果.對SHA-1 的另一攻擊手段是選擇前綴碰撞攻擊, 這一類的攻擊最好結(jié)果由Leurent 和Peyrin[8]在2020年發(fā)布, 他們以263.4的復(fù)雜度完成了對SHA-1 的選擇前綴攻擊.

在對SHA-1 的隨機(jī)碰撞攻擊和選擇前綴攻擊過程中, 構(gòu)造差分路徑和根據(jù)差分路徑尋找碰撞是兩種攻擊中共同的步驟. 在構(gòu)造差分路徑方面, 現(xiàn)已由早期的手動構(gòu)造方法[2]發(fā)展為自動化的差分路徑構(gòu)造算法[9–11]. 差分路徑的成立概率很大程度上決定了尋找碰撞的成功率和復(fù)雜度, 所以對概率的高精度刻畫在攻擊過程中是十分重要的. 在早期的SHA-1 碰撞攻擊研究過程中, 往往以充分條件的個(gè)數(shù)來決定差分路徑成立概率[12,13], 設(shè)由差分路徑推導(dǎo)的充分條件的個(gè)數(shù)為k, 則認(rèn)為該差分路徑成立的概率大約為1/2k. 2007 年, Mendel 等人[14]提出了在允許比特?cái)U(kuò)展且局部碰撞之間相互獨(dú)立的條件下, 對攻擊復(fù)雜度的評估方法. 2011 年, Manuel[15]證明了目前公布的擾動向量只有Type-I 和Type-II 兩類. 隨后,Stevens[11]提出了聯(lián)合概率的概念, 給出的概率模型是在同時(shí)滿足所有局部碰撞的條件下得到的, 對差分路徑的成立概率刻畫的精度更高.

本文對Stevens 提出的基于聯(lián)合概率的差分路徑概率模型進(jìn)一步分析, 給出其中第三部分的所有結(jié)構(gòu)和相應(yīng)的概率特征, 最后給出實(shí)例以佐證.

2 SHA-1 算法

SHA-1 算法采用MD 迭代結(jié)構(gòu), 可以將任意長度的輸入消息壓縮成160 比特的Hash 值. 算法分成消息填充、消息擴(kuò)展和壓縮函數(shù)三個(gè)部分.

消息填充在輸入消息的最后先填充一個(gè)1, 再填充若干個(gè)0, 使得填充后的消息長度l滿足l ≡448 mod 512, 再將原始消息的長度轉(zhuǎn)換成64 比特二進(jìn)制的形式填充到消息末尾, 此時(shí)消息長度是512 的整數(shù)倍, 這就是消息填充過程.

消息擴(kuò)展設(shè)填充后的消息長度為512K比特, 每個(gè)512 比特為一個(gè)消息塊, 分別記為M0,M1,···,MK?1. 消息擴(kuò)展過程是將每個(gè)512 比特的消息塊擴(kuò)展成80 個(gè)32 比特的消息字. 每個(gè)消息塊由16 個(gè)32 比特的消息字組成, 將第k+1 個(gè)消息塊Mk記為W0,k,W1,k,··· ,W15,k, 則對Mk的消息擴(kuò)展準(zhǔn)則如下式, 其中RL(W,b) 代表將32 比特向量W循環(huán)左移b比特:

接下來擴(kuò)展后的消息塊依次進(jìn)入壓縮函數(shù), 當(dāng)處理第k+1 個(gè)消息塊Mk時(shí), 壓縮函數(shù)以Mk和上一個(gè)消息塊的壓縮函數(shù)輸出IHVk=(ak,bk,ck,dk,ek) 作為輸入(ak,bk,ck,dk,ek為32 比特消息字), 輸出結(jié)果為160 比特的消息摘要IHVk+1, 即IHVk+1= Compress(IHVk,Mk), 處理第一個(gè)消息塊M0的初始值取值為IHV0=(a0,b0,c0,d0,e0):

這樣, 最后一個(gè)消息塊MK?1進(jìn)入壓縮函數(shù)后的輸出結(jié)果IHVK即為最終的SHA-1 哈希值.

壓縮函數(shù)第k+1 個(gè)消息塊Mk經(jīng)過消息擴(kuò)展后進(jìn)入壓縮函數(shù)的過程如下: 由上一步的壓縮結(jié)果IHVk= (ak,bk,ck,dk,ek), 令5 個(gè)寄存器的初始值為(Q0,Q?1,Q?2,Q?3,Q?4) = (ak,bk,RR(ck,30),RR(dk,30),RR(ek,30)), 其中RR(W,b) 代表將32 比特向量W循環(huán)右移b比特.

然后進(jìn)行4 輪(每輪20 步) 迭代計(jì)算, 每次迭代均輸入一個(gè)擴(kuò)展后的消息字, 第t(0≤t ≤79) 步的迭代方程為:Qt+1=RL(Qt,5)+Ft+RL(Qt?4,30)+Wt,k+ACt. 其中:

(1)Ft=ft(Qt?1,RL(Qt?2,30),RL(Qt?3,30)),ft是以三個(gè)比特為輸入的布爾函數(shù), 其在每一輪的表達(dá)式分別為:

(2) ACt是輪常數(shù), 其在每一輪的取值如下:

80 步迭代之后, 壓縮函數(shù)的輸出為IHVk+1= (ak+1,bk+1,ck+1,dk+1,ek+1) = (ak+Q80,bk+Q79,ck+RL(Q78,30),dk+RL(Q77,30),ek+RL(Q76,30)).

3 基于聯(lián)合概率的差分路徑概率模型

為了完整性, 本節(jié)介紹文獻(xiàn)[11] 所提出的一種新的基于聯(lián)合概率的差分路徑概率模型. 該模型通過提出概率實(shí)驗(yàn)1, 從理論上對差分路徑的概率進(jìn)行了精準(zhǔn)刻畫. 進(jìn)一步, 為了方便對實(shí)驗(yàn)的成功率進(jìn)行刻畫, 將實(shí)驗(yàn)1 改進(jìn)得到概率實(shí)驗(yàn)2. 然而, 在概率實(shí)驗(yàn)1 和2 中, 都存在取值空間過大、無法窮舉的問題.為了解決這一問題, 文獻(xiàn)[11] 結(jié)合圖論方面的知識, 通過對差分路徑上的寄存器差分和布爾函數(shù)差分的拆

概率實(shí)驗(yàn)1

對于第一塊消息, 隨機(jī)選擇初始寄存器值 ?Qtb?4,··· ,?Qtb和第tb到te步的擴(kuò)展消息字?Wtb,··· ,?Wte, 然后計(jì)算第一塊消息在第tb到te步的布爾函數(shù)值并更新寄存器值, 其中t=tb,··· ,te:

然后根據(jù)SHA-1 算法的壓縮函數(shù)計(jì)算每一步的布爾函數(shù)值, 并更新寄存器值, 其中t=tb,··· ,te:

得到兩塊消息相關(guān)變量的取值后, 判斷兩個(gè)消息塊的寄存器差分和布爾函數(shù)差分是否與差分路徑吻合, 即判斷:

對于第二塊消息, 各個(gè)變量的計(jì)算方法與實(shí)驗(yàn)1 一致. 判斷實(shí)驗(yàn)是否成功的條件也與實(shí)驗(yàn)1 一致.

可以看到, 實(shí)驗(yàn)1 在第一塊消息上首先隨機(jī)選擇消息字, 再計(jì)算寄存器值. 而實(shí)驗(yàn)2 與這一過程相反,即先隨機(jī)選擇寄存器值, 再計(jì)算消息的值. 經(jīng)過實(shí)驗(yàn)1 到實(shí)驗(yàn)2 的轉(zhuǎn)變, 隨機(jī)選擇的變量完成了由兩類向一類的整合(實(shí)驗(yàn)1 需要隨機(jī)選擇寄存器值和消息值兩類變量, 而實(shí)驗(yàn)2 中需要隨機(jī)選擇的變量只有寄存器值一類).

第一部分

設(shè)差分路徑上非零的寄存器差分對應(yīng)的比特位集合為GΔQ={(j,i)|?Qj[i]?= 0, j ∈ {tb ?3,··· ,te}, i ∈{0,··· ,31}}. 對于集合GΔQ中元素(j,i), 為了取得實(shí)驗(yàn)2 的成功, 若?Qj[i] = +1,則隨機(jī)選擇的第一塊消息的 ?Qj必須滿足 ?Qj[i] = 0; 若?Qj[i] =?1, 則隨機(jī)選擇的第一塊消息的 ?Qj必須滿足 ?Qj[i] = 1, 這兩種情況的成立概率均為1/2. 所以GΔQ中的比特位滿足差分路徑的概率為pΔQ=2?|GΔQ|.

第二部分

給定差分路徑上第t步的布爾函數(shù)的三個(gè)輸入寄存器差分為?Qt?1,?Qt?2,?Qt?3, 對于滿足這三個(gè)寄存器差分的3 對寄存器取值, 將第b比特上所有可能的布爾函數(shù)輸出差分組成的集合記為Vt,b:

設(shè)SF={(t,b)||Vt,b|> 1}, 考慮滿足以下兩個(gè)條件的寄存器比特位(j,i): 1○對應(yīng)的寄存器差分為零, 即?Qj[i]=0; 2○(j+1,i),(j+2,i ?2),(j+3,i ?2) 中至少有一個(gè)在集合SF中. 即

第三部分

命題2在上述分割方法下, 差分路徑的概率分解成若干個(gè)因子的乘積:

4 基于圖論方法的精確概率特征計(jì)算

本小節(jié)對第3 節(jié)中的第三部分概率做進(jìn)一步的理論分析. 按照第3 節(jié)的分割方法, 第三部分主要考慮布爾函數(shù)輸出差分不唯一時(shí)的成立概率. 對于SHA-1 算法在后三輪所采用的布爾函數(shù)—異或函數(shù)和擇多函數(shù), 分析總結(jié)其輸出差分規(guī)律. 進(jìn)一步, 結(jié)合圖論相關(guān)知識分析第三部分中連通分支的結(jié)構(gòu)特征和概率特征. 首先提出本文所涉及的圖論的基本概念.

定義1一個(gè)集合的元素和它們之間的某種關(guān)系稱為圖. 具體地說, 圖是一個(gè)二元組(V,E), 其中集合V稱為節(jié)點(diǎn)集, 集合V中由兩個(gè)元素組成的無序?qū)Φ募螮稱為邊集. 圖的節(jié)點(diǎn)集中的元素稱為節(jié)點(diǎn),邊集中的元素稱為邊. 節(jié)點(diǎn)的數(shù)目|V| 稱為圖的階, 邊的數(shù)目|E| 稱為圖的邊數(shù).

例 1給定G= (V,E), 其中節(jié)點(diǎn)集V={v1,v2,v3,v4,v5}, 邊集E={(v1,v2),(v3,v4),(v1,v5),(v5,v5)}. 這便定義出一個(gè)圖. 節(jié)點(diǎn)v1和v2稱為邊(v1,v2) 的端點(diǎn), 反過來也稱邊(v1,v2)連接節(jié)點(diǎn)v1和v2.

定義2(點(diǎn)和點(diǎn)的相鄰) 如果圖上兩點(diǎn)被同一條邊相連, 則稱該兩點(diǎn)在圖中相鄰.

定義3(點(diǎn)和邊的關(guān)聯(lián)) 如果在圖G中節(jié)點(diǎn)v是邊e的一個(gè)端點(diǎn), 則稱節(jié)點(diǎn)v與邊e在圖G中相關(guān)聯(lián).

定義4(節(jié)點(diǎn)的度) 圖G中節(jié)點(diǎn)v所關(guān)聯(lián)的邊的數(shù)目稱為節(jié)點(diǎn)v的度, 記為dG(v) 或d(v).

定義5圖G中一個(gè)點(diǎn)邊接續(xù)交替出現(xiàn)的序列w=vi0ei1vi1ei2···eikvik稱為圖G的一條途徑, 其中vi0,vik分別稱為途徑w的起點(diǎn)和終點(diǎn),w上其余節(jié)點(diǎn)稱為中途點(diǎn). 圖G中邊不重復(fù)出現(xiàn)的途徑稱為跡. 圖G中頂點(diǎn)不重復(fù)出現(xiàn)的跡稱為路.

定義6設(shè)G是一個(gè)圖,V′?V(G). 以V′為節(jié)點(diǎn)集, 以G中兩端點(diǎn)均屬于V′的所有邊作為邊集所組成的子圖, 稱為G的由節(jié)點(diǎn)集V′導(dǎo)出的子圖, 簡稱為G的點(diǎn)導(dǎo)出子圖, 記為G|V′|.

定義7(圖中兩點(diǎn)的連通) 如果在圖G中u,v兩點(diǎn)間有路相通, 則稱節(jié)點(diǎn)u,v在圖G中連通. 若圖G中任兩節(jié)點(diǎn)都相通, 則稱圖G是連通圖.

定義8(圖的連通分支) 若圖G的節(jié)點(diǎn)集V(G) 可劃分為若干非空子集V1,V2,···Vw, 使得兩節(jié)點(diǎn)屬于同一子集當(dāng)且僅當(dāng)它們在G中連通, 則每個(gè)點(diǎn)導(dǎo)出子圖G|Vi| 為圖G的一個(gè)連通分支(i=1,2,··· ,w).G的連通分支的個(gè)數(shù)稱為G的連通分支數(shù).

在本文所涉及的圖中, 節(jié)點(diǎn)分為兩類, 一類代表寄存器比特位, 另一類代表布爾函數(shù)比特位. 另外, 圖中相鄰的兩個(gè)點(diǎn)屬于不同類節(jié)點(diǎn), 即邊的端點(diǎn)均為一個(gè)寄存器比特位和一個(gè)布爾函數(shù)比特位.

定理1對于異或函數(shù)f(X,Y,Z)=X ⊕Y ⊕Z, 給定X,Y,Z上的差分?X,?Y,?Z, 定義集合

則|Vf|> 1??X,?Y,?Z中有且僅有一個(gè)為非零, 即存在六種輸入寄存器差分的取值使得布爾函數(shù)的輸出差分不唯一, 這六種取值分別為三個(gè)輸入中的其中一個(gè)為正差分或負(fù)差分.

證明:1)|Vf|>1??X,?Y,?Z中有且僅有一個(gè)為非零.

在布爾函數(shù)f(X,Y,Z) =X ⊕Y ⊕Z的三個(gè)輸入比特上, 每個(gè)比特上的差分都有三種取值: 0、+1和?1, 所以三個(gè)輸入比特差分共有27 種取值情況. 將?X,?Y,?Z的27 種取值遍歷, 計(jì)算每種取值下的集合Vf, 將所有|Vf|> 1 的情況匯總得到表1(左), 可以從中發(fā)現(xiàn)寄存器差分的規(guī)律: 輸入寄存器差分?X,?Y,?Z中有且僅有一個(gè)為非零.

2) ?X,?Y,?Z中有且僅有一個(gè)為非零?|Vf|>1.

當(dāng)?X,?Y,?Z中有且僅有一個(gè)為非零時(shí), 由表1(左),|Vf|>1.

表1 布爾函數(shù)輸出差分不唯一的所有情況Table 1 All cases where Boolean function output difference is not unique

表注: 每個(gè)Vf中的元素下的等式或不等式是為了得到相應(yīng)的輸出差分而對兩個(gè)不存在差分的寄存器的取值提出的制約條件. 以第一行為例, 當(dāng)三個(gè)輸入寄存器比特上的差分為··+ 時(shí)(即?X=0、?Y=0和?Z=+1),集合Vf中存在兩個(gè)元素: +1 和?1. 其中,?f(X,Y,Z)=+1 時(shí)要求X′=X=Y=Y′,而?f(X,Y,Z)=?1 時(shí)要求X′=X,Y=Y′,X ?=Y.

定理2將定理1 中的異或函數(shù)替換成擇多函數(shù)f(X,Y,Z)= (X ∧Y)∨(Z ∧(X ∨Y)), 結(jié)論依然成立.

證明:將異或函數(shù)替換成擇多函數(shù)f(X,Y,Z) = (X ∧Y)∨(Z ∧(X ∨Y)), 同樣計(jì)算27 種輸入差分取值下的集合Vf, 將|Vf|>1 的情況匯總得到表1(右). 其余證明過程與定理1 同理.

根據(jù)定理1 和定理2 可以得到以下定理和推論:

定理3連通分支FQk中每個(gè)布爾函數(shù)比特位的度均為2.

證明:在連通分支FQk(k=1,2,··· ,K) 中, 對于(t,b)∈SF, 由定理1 和定理2 可知,Ft[b] 的三個(gè)輸入寄存器差分?Qt?1[b], RL(?Qt?2,30)[b], RL(?Qt?3,30)[b] 中有且僅有一個(gè)為非零, 其中20≤t<79,b=0,1,··· ,31. 即在連通分支FQk(k=1,2,··· ,K) 中, 每個(gè)布爾函數(shù)比特位(t,b)∈SF一定與兩個(gè)輸入寄存器比特位相連接, 故而該點(diǎn)在連通分支中的度為2.

定義9將含有l(wèi)個(gè)布爾函數(shù)比特位、l+1 個(gè)寄存器比特位的連通分支稱為l-l+1 型連通分支.

綜合以上分析, 所有連通分支的類型為1-2 型、2-3 型、3-4 型等. 顯然, 1-2 型和2-3 型連通分支只有一種結(jié)構(gòu), 而3-4 型連通分支由于一個(gè)寄存器比特位的度的不確定性可以分為兩種結(jié)構(gòu), 圖1 列舉了1-2型、2-3 型、3-4 型連通分支的所有結(jié)構(gòu). 在每個(gè)類型的連通分支中, 上層節(jié)點(diǎn)均為布爾函數(shù)比特位, 自左向右分別記為F1,F2,··· ,下層節(jié)點(diǎn)均為寄存器比特位, 自左向右分別記為Q1,Q2,··· .

定理4在由Type-I 和Type-II 類擾動向量得到的差分路徑中, 圖1 中3-4 型(2) 的結(jié)構(gòu)不存在.

圖1 連通分支的結(jié)構(gòu)Figure 1 Structure of connected branches

證明:首先分析一個(gè)寄存器比特位在連通分支中的結(jié)構(gòu)特點(diǎn). 對于寄存器比特Qj[i], 其中i=0,1,··· ,31 且20≤j<79, 存在三個(gè)布爾函數(shù)比特位以其作為輸入, 分別為

由集合SQ的含義以及定理3, 當(dāng)?Qj[i] = 0 且三對寄存器比特Qj?1[i+2 mod 32] 和Qj?2[i+2 mod 32]、Qj+1[i ?2 mod 32] 和Qj?1[i]、Qj+2[i ?2 mod 32] 和Qj+1[i] 中至少有一對比特上的差分為零和非零的組合時(shí), 有(j,i)∈SQ.

下面證明連通分支中一個(gè)寄存器比特位的度不可能為3.

假設(shè)(j,i)∈SQ且在連通分支中的度為3, 則(j,i)∈SQ與三個(gè)布爾函數(shù)位(分別為(j+1,i),(j+2,i ?2),(j+3,i ?2)∈SF) 相連接, 則三對寄存器比特Qj?1[i+2 mod 32] 和Qj?2[i+2 mod 32]、Qj+1[i ?2 mod 32] 和Qj?1[i]、Qj+2[i ?2 mod 32] 和Qj+1[i] 上的差分均為零和非零的組合, 具體有8種情況見表2.

表2 d((j,i))=3 時(shí)要求寄存器差分的取值情況Table 2 Value of register differential required for d((j,i))=3

針對表2 中的第一種情況進(jìn)行分析: 首先, 在后60 步差分路徑上, 寄存器上的差分(不考慮差分的正負(fù)) 與擾動向量是一致的, 即?Qj[i]?= 0 當(dāng)且僅當(dāng)擾動向量滿足DVj?1[i] = 1, 反之, ?Qj[i] = 0 當(dāng)且僅當(dāng)擾動向量滿足DVj?1[i] = 0. 所以, 表2 的第一種情況要求擾動向量滿足: 對于i= 0,1,··· ,31 和20≤j< 79, DVj?1[i],DVj?2[i+2 mod 32],DVj[i ?2 mod 32],DVj+1[i ?2 mod 32] 的取值為0, 而DVj?3[i+2 mod 32],DVj?2[i],DVj[i] 的取值為1. 文獻(xiàn)[15] 中證明了最優(yōu)擾動向量存在兩類(Type-I和Type-II), 目前為止對SHA-1 的碰撞攻擊中用到的擾動向量有

附錄列出了這些擾動向量的后60 步在通式I(K,0) 和II(K,0) 中涉及的最大范圍. 將上述條件和附錄對比發(fā)現(xiàn)Type-I 和Type-II 類擾動向量不能滿足表2 中第一種情況. 對表2 中另外7 種情況進(jìn)行同理分析, 最終結(jié)論為: 對于Type-I 和Type-II 類擾動向量, 表2 中的8 種情況均不可能存在, 故連通分支中寄存器比特位的度小于3, 即圖1 中3-4 型(2) 的結(jié)構(gòu)不存在.

定理5在由Type-I 和Type-II 類擾動向量得到的差分路徑中, 圖1 中3-4 型(1) 的結(jié)構(gòu)不存在.

證明:對于圖1 中3-4 型(1) 的結(jié)構(gòu), 固定Q2點(diǎn)為(j,i), 在此基礎(chǔ)上分析其他寄存器比特位和布爾函數(shù)位的取值情況. 與Q2點(diǎn)相連的兩個(gè)布爾函數(shù)位F1和F2從(j+1,i),(j+2,i ?2),(j+3,i ?2) 中選擇, 由于F1和F2兩點(diǎn)在3-4 型(1) 結(jié)構(gòu)中的地位是不對等的, 所以共有6 種選擇. 然后, 在F2的除Q2外的兩個(gè)輸入寄存器比特中選擇一個(gè)確定為Q3點(diǎn)(2 種選擇), 再在以Q3點(diǎn)為輸入的除F2外的兩個(gè)布爾函數(shù)位中選擇一個(gè)確定為F3(2 種選擇). 最后確定Q1和Q4(均有2 種選擇). 所以, 在固定節(jié)點(diǎn)Q2點(diǎn)后, 3-4 型(1) 結(jié)構(gòu)的連通分支上所有點(diǎn)的取值共有6×2×2×2×2=96 種情況.

與定理4 的證明過程同理, 將96 種情況對照附錄進(jìn)行分析, 發(fā)現(xiàn)Type-I 和Type-II 類擾動向量不能滿足上述條件. 另外發(fā)現(xiàn)有些情況本身就存在矛盾. 總之, 96 種情況均不可能存在, 所以3-4 型(1) 結(jié)構(gòu)的連通分支在由Type-I 和Type-II 類擾動向量得到的差分路徑中不可能存在.

推論2在由Type-I 和Type-II 類擾動向量得到的差分路徑中, 本文的概率模型的第三部分中連通分支的結(jié)構(gòu)只可能有1-2 和2-3 型兩種.

證明:假設(shè)存在l-l+1 型連通分支(l> 3), 則一定內(nèi)嵌有3-4 型(1) 和3-4 型(2) 結(jié)構(gòu). 結(jié)合定理4 和定理5, 在由Type-I 和Type-II 類擾動向量得到的差分路徑中, 只可能有1-2 和2-3 型兩種結(jié)構(gòu)的連通分支.

定理6l-l+1 型連通分支SQ中寄存器比特位的取值滿足差分路徑的概率為2/2l+1.

證明:設(shè)一個(gè)l-l+1 型連通分支SQ中的寄存器比特位分別為(j1,i1),··· ,(jl,il),(jl+1,il+1), 對應(yīng)Qj1[i1],··· ,Qjl[il],Qjl+1[il+1]. 其中一個(gè)位置Qjm[im],m=1,2,··· ,l在取定0 或1 其中一個(gè)值后,由表1 可以確定這些比特位的取值以得到差分路徑指定的布爾函數(shù)輸出差分, 即與Qjm[im] 的關(guān)系都確定為“相等” 或“不相等”. 也就是說, 當(dāng)確定Qj1[i1],··· ,Qjl[il],Qjl+1[il+1] 中的其中一個(gè)取值后, 其余比特位的取值也隨之確定. 所以Qj1[i1],··· ,Qjl[il],Qjl+1[il+1] 一共在兩種取值下可以滿足差分路徑. 而l+1 個(gè)比特位的取值空間中存在2l+1個(gè)元素, 所以這些比特位滿足差分路徑的概率為2/2l+1.

5 實(shí)例及評估

本節(jié)以三段具體的差分路徑為例, 對其分別按照實(shí)驗(yàn)的方法、計(jì)數(shù)充分條件的方法和本文第3、4 節(jié)的方法進(jìn)行概率計(jì)算, 綜合三個(gè)結(jié)果對本文的概率模型進(jìn)行評估.

實(shí)例1

2005 年,王小云[2]針對SHA-1 算法提出了模差分攻擊的方法,以269的復(fù)雜度給出了對全輪SHA-1算法的碰撞攻擊. 隨后文獻(xiàn)[16] 對其用到的差分路徑進(jìn)行了全輪分析, 本文以文獻(xiàn)[16] 整理的差分路徑進(jìn)行概率分析. 以文獻(xiàn)[16] 中Figure 3 的第46–56 步的差分路徑(記為P46–56) 為例進(jìn)行概率分析, 差分路徑及對應(yīng)的充分條件如表3, 表中的數(shù)字代表存在擾動(第2 列) 或差分不為零(第3–7 列) 的比特位,“-” 代表32 位無擾動或全零差分.

表3 第46–56 步上的差分路徑Table 3 Differential path over Steps 46–56

命題3當(dāng)按照充分條件的個(gè)數(shù)計(jì)算差分路徑的概率時(shí), Pr[P46–56]=1/219.

證明:由于在第46–56 步上的充分條件的個(gè)數(shù)為19, 根據(jù)每個(gè)充分條件成立的概率為1/2 的原則,所以差分路徑P46–56的概率為1/219.

命題4當(dāng)按照本文的差分路徑概率模型計(jì)算概率時(shí), Pr[P46–56]=1/216.

證明:當(dāng)按照第3 節(jié)和第4 節(jié)中的差分路徑概率模型, 差分路徑上寄存器差分的情況為:

(1)δRL(Q42,30)=0;

(2) ?Q43,?Q44,?Q46,?Q48,?Q50上無差分, ?Q45,?Q47,?Q49,?Q51均在第1 位上存在正差分;

(3)δQ57=0.

進(jìn)而可以確定集合GΔQ為GΔQ={(45,1),(47,1),(49,1),(51,1)}, 共四個(gè)元素, 所以這一部分對應(yīng)的概率為1/24.

然后確定集合SF的所有元素. 對于(t,b)∈SF, ?Qt?1[b],RL(?Qt?2,30)[b],RL(?Qt?3,30)[b] 中至少有一個(gè)輸入差分為非零. 故將每個(gè)非零寄存器差分作為布爾函數(shù)的輸入, 他們影響的所有布爾函數(shù)差分如表4, 其中“無” 代表布爾函數(shù)輸出的32 個(gè)比特上差分均為0.

表4 差分路徑P46–56 上非零布爾函數(shù)差分與非零輸入的關(guān)系Table 4 Nonzero Boolean function differences and nonzero inputs on differential path P46–56

這 12 個(gè)布爾函數(shù)比特位均滿足有且只有一個(gè)輸入差分非零, 根據(jù)定理1 確定集合SF={(46,1),(47,31),(48,1),(48,31),(49,31),(50,1),(50,31),(51,31),(52,1),(52,31),(53,31),(54,31)}. 進(jìn)而集合SQ={(44,3),(43,3),(46,31),(44,1),(46,3),(45,3),(47,31),(46,1),(48,31),(48,3),(47,3),(49,31),(48,1),(50,31),(50,3),(49,3),(51,31),(50,1),(52,31),(52,1),(53,31)}.SF和SQ形成集合FQ, 對于(j,i)∈SQ和(t,b)∈SF, 若Qj[i] 是Ft[b] 的一個(gè)輸入, 則在FQ 中將(j,i) 和(t,b) 連接起來.所連成的圖如圖2 所示(圖2與圖1的節(jié)點(diǎn)排列方式相同, 連通分支的布爾函數(shù)節(jié)點(diǎn)位于上層, 寄存器節(jié)點(diǎn)位于下層).

圖2 第46–56 步差分路徑的所有連通分支Figure 2 All connected branches of differential path over Steps 46–56

可以看到, FQ 中的元素一共形成9 個(gè)連通分支, 其中有6 個(gè)1-2 型連通分支和3 個(gè)2-3 型連通分支.依據(jù)定理4, 1-2 型連通分支的概率為2/22, 2-3 型連通分支的概率為2/23. 綜上, 這段第46–56 步的差分路徑成立概率為2?4×(2/23)3×(2/22)6=1/216.

實(shí)例2

本文還對文獻(xiàn)[16] 中Figure 3 中的第66–79 步的差分路徑進(jìn)行了相同過程的概率分析, 按照充分條件的個(gè)數(shù)計(jì)算得到的差分路徑的概率為1/230, 而按照第3 節(jié)和第4 節(jié)中的差分路徑概率模型計(jì)算得到的概率為1/221, 其中第三部分的連通分支結(jié)構(gòu)都是1-2 型的, 具體計(jì)算過程不再贅述.

實(shí)例3

命題5當(dāng)按照充分條件的個(gè)數(shù)計(jì)算差分路徑的概率時(shí), Pr[P8–16]=1/233.

證明:由于在第8–16 步上的充分條件的個(gè)數(shù)為33, 根據(jù)每個(gè)充分條件成立的概率為1/2 的原則, 所以差分路徑P8–16的概率為1/233.

命題6當(dāng)按照充分條件的個(gè)數(shù)計(jì)算差分路徑的概率時(shí), Pr[P8–16]=1/228.

證明:當(dāng)按照第3 節(jié)和第4 節(jié)中的差分路徑概率模型, 差分路徑上寄存器差分的情況為:

(1)δRL(Q4,30)=24+25+26+27+28?29?228+231;

(2) ?Q5–?Q16上的差分如表5;

表5 第8–16 步上的差分路徑P8–16Table 5 Differential path over Steps 8–16

(3)δQ17=231.

進(jìn)而可以確定集合GΔQ為?Q5–?Q16上所有差分為非零的比特位, 根據(jù)表5 可知GΔQ中共有18個(gè)元素, 所以這一部分對應(yīng)的概率為1/218.

然后確定集合SF的所有元素. 對于(t,b)∈SF, ?Qt?1[b], RL(?Qt?2,30)[b], RL(?Qt?3,30)[b] 中至少有一個(gè)輸入差分為非零. 將由表5 中布爾函數(shù)上的非零差分總結(jié)在表6 中, 分析非零寄存器差分的輸入情況.

表6 差分路徑P8–16 上非零布爾函數(shù)差分與非零輸入的關(guān)系Table 6 Nonzero Boolean function differences and nonzero inputs on differential path P8–16

由定理1 可知, 當(dāng)存在兩個(gè)及以上的輸入存在非零差分時(shí), 布爾函數(shù)的輸出值唯一. 所以可以確定集合SF為:

進(jìn)而集合SQ為:

SF和SQ形成集合FQ, 對于(j,i)∈SQ和(t,b)∈SF, 若Qj[i] 是Ft[b] 的一個(gè)輸入, 則在FQ 中將(j,i) 和(t,b) 連接起來. 所連成的圖如圖3 所示(圖結(jié)構(gòu)和節(jié)點(diǎn)的含義同圖2):

圖3 第6–18 步差分路徑的所有連通分支Figure 3 All connected branches of differential path over Steps 6–18

可以看到, FQ 中的元素一共形成10 個(gè)1-2 型連通分支. 依據(jù)定理6, 每個(gè)1-2 型連通分支的概率為2/22, 所以第8–16 步的差分路徑成立概率為2?18×(2/22)10=1/228.

本節(jié)的差分路徑實(shí)例從涵蓋的輪數(shù)上看, 既包含了第一輪的非線性路徑, 也包含了后三輪的線性差分路徑部分, 實(shí)驗(yàn)結(jié)果可見本文的概率模型在刻畫差分路徑成立概率上的優(yōu)越性. 從表7 的結(jié)果中可以發(fā)現(xiàn),相較本文的概率模型, 按照充分條件的個(gè)數(shù)計(jì)算得到的差分路徑概率偏小. 這是因?yàn)楸疚牡母怕誓Ｐ褪轻槍Σ罘致窂降恼w進(jìn)行概率分析的, 而充分條件個(gè)數(shù)的方法將差分路徑中的局部碰撞視為相互獨(dú)立的. 由于各個(gè)局部碰撞成立的充分條件可能會同一寄存器比特或消息比特做出約束, 充分條件之間存在內(nèi)在的聯(lián)系, 所以按照每個(gè)充分條件的成立概率均為1/2、同時(shí)所有充分條件獨(dú)立的計(jì)算方法會使計(jì)算結(jié)果偏小.

表7 差分路徑實(shí)例的不同概率分析結(jié)果對比Table 7 Comparison of different probability analysis results of differential paths instance

6 總結(jié)

在對SHA-1 的碰撞攻擊過程中, 差分路徑的構(gòu)造是非常重要的步驟, 將會直接影響后續(xù)尋找碰撞消息對的復(fù)雜度. 差分路徑的成立概率是考察其優(yōu)劣的一個(gè)重要衡量指標(biāo), 所以更精確地刻畫差分路徑成立的概率有助于對差分路徑進(jìn)行準(zhǔn)確評估, 進(jìn)而對整個(gè)碰撞攻擊的復(fù)雜度進(jìn)行精準(zhǔn)評估. 隨機(jī)碰撞分為差分路徑構(gòu)造和消息搜索兩個(gè)階段, 利用本文的概率模型對文獻(xiàn)[16] 中后三輪的差分路徑進(jìn)行分析, 得到其成立概率為1/292, 而該段差分路徑成立的充分條件個(gè)數(shù)為113 個(gè), 這說明本文方法更貼近實(shí)際概率. 需要說明的是基于該路徑, 消息搜索階段可利用消息遞歸技術(shù)和高級消息修改技術(shù)進(jìn)一步降低復(fù)雜度, 致使差分路徑概率與真實(shí)的碰撞攻擊復(fù)雜度存在差距. 本文對Stevens 提出的基于聯(lián)合概率的差分路徑概率模型進(jìn)行分析, 得出了其中第三部分連通分支的結(jié)構(gòu)特征和概率特征. 從理論上證明了對于兩類最優(yōu)擾動向量, 不存在包含3 個(gè)及以上布爾函數(shù)比特的連通分支, 明確了每一類連通分支對應(yīng)的成立概率. 完善之后的概率模型使得差分路徑的概率計(jì)算過程更為簡單, 且較之前的計(jì)算方法誤差更小.