帶消息填充的29步SM3算法原根和偽碰撞攻擊

王高麗，申延召

（1.東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620；2.中國(guó)科學(xué)院 信息工程研究所 信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100093）

1 引言

雜湊函數(shù)在密碼學(xué)中具有重要的地位，安全的雜湊函數(shù)能夠抵抗碰撞攻擊、原根攻擊和第二原根攻擊等。對(duì)于雜湊函數(shù)的攻擊方法有很多，例如基于模差分的碰撞攻擊[1,2]方法、基于中間相遇攻擊[3]的原根攻擊[4]方法等。對(duì)于雜湊函數(shù)的攻擊中最為顯著的是王小云等學(xué)者提出的對(duì)于MD5和SHA-1等國(guó)際通用雜湊函數(shù)的碰撞攻擊[1,2]。隨著MD5和SHA-1被破解[1,2]，美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究所(NIST)于 2007年啟動(dòng)了新的雜湊函數(shù)標(biāo)準(zhǔn) SHA-3的征集活動(dòng)[5]，并于2012年10月公布了新一代雜湊函數(shù)標(biāo)準(zhǔn)——Keccak算法。

隨著SHA-3征集活動(dòng)的進(jìn)行，各國(guó)都在制定自己的雜湊算法標(biāo)準(zhǔn)。2010年中國(guó)國(guó)家密碼管理局公布了中國(guó)商用密碼雜湊算法標(biāo)準(zhǔn)——SM3密碼雜湊函數(shù)[6]。該算法由王小云等學(xué)者設(shè)計(jì)，消息分組長(zhǎng)度為512 bit，輸出雜湊值長(zhǎng)度為256 bit，采用Merkle-Damgard結(jié)構(gòu)。就壓縮函數(shù)而言，SM3密碼雜湊函數(shù)與SHA-256具有相似的結(jié)構(gòu)，但是SM3算法的壓縮函數(shù)的每一步都使用2個(gè)消息字，每一步的擴(kuò)散能力更強(qiáng)。

文獻(xiàn)[7]首次給出了對(duì)于縮減頻數(shù)的 SM3算法的原根攻擊。其中，對(duì)于從第1步開始的28步SM3算法的原根攻擊的時(shí)間復(fù)雜度為2241.5；對(duì)于從第7步開始的30步SM3算法的原根攻擊的時(shí)間復(fù)雜度為2249。因?yàn)榍?6步 SM3算法中的函數(shù) FF(·)和 GG(·)均為異或函數(shù)，其性質(zhì)不利于分析的進(jìn)行，所以文獻(xiàn)[7]用到了第 16步以后的函數(shù) FF(·)和 GG(·)的性質(zhì)，因此，對(duì)于 30步 SM3算法的原根攻擊不能從第1步開始。文獻(xiàn)[8]給出了對(duì)于35步SM3算法的飛來(lái)去器攻擊，其時(shí)間復(fù)雜度為2117.1，證明了從第1步開始的35步SM3算法是非隨機(jī)的。文獻(xiàn)[9]使用差分—中間相遇攻擊給出了對(duì)29步、30步、31步和32步SM3算法的原根攻擊和偽碰撞攻擊，均從第1步開始。但是，文獻(xiàn)[9]在構(gòu)造差分特征時(shí)用到了消息填充所需的消息字，因此文獻(xiàn)[9]的攻擊不能包含有效的消息填充。

在深入分析 SM3算法的特點(diǎn)后，本文提出了一種帶消息填充的、從第1步開始的29步SM3算法的原根攻擊和偽碰撞攻擊方法。本文采用中間相遇技術(shù)進(jìn)行原根攻擊，且攻擊過(guò)程不依賴于 SM3算法中函數(shù) FF(·)和 GG(·)的性質(zhì)，另外，對(duì)于 29步SM3算法的原根攻擊可以轉(zhuǎn)化為對(duì)于29步SM3算法的偽碰撞攻擊。帶消息填充的、從第1步開始的29步SM3的原根攻擊和偽碰撞攻擊的時(shí)間復(fù)雜度分別為2254和2125。

2 SM3算法

SM3算法將長(zhǎng)度為l(l＜264)的消息 M(比特串)進(jìn)行壓縮，輸出256 bit的雜湊值。對(duì)于消息M，SM3算法首先執(zhí)行一個(gè)消息填充過(guò)程，在M 后添加 1個(gè)“1”和k個(gè)“0”，再添加上64 bit l的二進(jìn)制表示，k為等式l+k+65≡448mod512的最小正整數(shù)解。這樣把M填充成長(zhǎng)度為512倍數(shù)的新消息M'。接著將 M'按照 512 bit進(jìn)行分組，假定 M'=(B(0),B(1),…,B(n?1))，CF(·)為SM3 算法的壓縮函數(shù)，則 M雜湊值的計(jì)算過(guò)程如下

其中，IV為初始值，Vn為M的雜湊值。SM3算法的壓縮函數(shù) Vi=CF(Vi?1,B(i?1))由消息擴(kuò)展過(guò)程和變量更新過(guò)程組成。

2.1 消息擴(kuò)展過(guò)程

SM3算法的消息擴(kuò)展過(guò)程首先將 B(i?1)分成 16個(gè)長(zhǎng)度為32 bit的消息字wi，0≤i≤15，然后將其擴(kuò)展成 68個(gè)消息字 wi(0≤i≤67)和 64個(gè)消息字wi'(0≤i≤63)。具體過(guò)程如下。

i從 16～67:

i從 0～63:

wi'=wi⊕wi+4

其中，P1(X)=X⊕(X＜＜＜15)⊕(X＜＜＜23)。

2.2 變量更新過(guò)程

對(duì)于給定的初始值 IV=(A0,B0,C0,D0,E0,F0,G0,H0)，SM3算法變量更新的具體過(guò)程如下。

對(duì)于i從0～63:

其中，P0(X)=X⊕(X＜＜＜9)⊕(X＜＜＜17)。

FFi(Ai,Bi,Ci)和GGi(Ei,Fi,Gi)的定義如下

2.3 符號(hào)說(shuō)明

以下對(duì)本文所使用的符號(hào)進(jìn)行說(shuō)明。

1)(Ai,Bi,Ci,Di,Ei,Fi,Gi,Hi)表示第 i?1 步的輸出變量值。特別地，(A0,B0,C0,D0,E0,F0,G0,H0)表示壓縮函數(shù)的初始值。

2)pi[a～b]表示32 bit字pi的第a比特到第b比特的值，pi可以為Ai，Bi，Ci，Di，Ei，F(xiàn)i，Gi，Hi，wi或wi'，0≤a≤b≤31，第0比特為最低位，第31比特為最高位。

3)h=(A,B,C,D,E,F,G,H)表示 256 bit的雜湊值。

4)pi[a～b,c～d]表示 32 比特字 pi的第 a 比特到第b比特和第c比特到第d比特，pi可以為A，B，C，D，E，F(xiàn)，G，H，Ai，Bi，Ci，Di，Ei，F(xiàn)i，Gi，Hi，wi或 wi'，0≤a≤b≤c≤d≤31。

3 相關(guān)技術(shù)介紹

3.1 中間相遇攻擊

中間相遇攻擊由文獻(xiàn)[3]提出，文獻(xiàn)[4]第一次將中間相遇攻擊用于原根攻擊，圖 1展示了文獻(xiàn)[9]中的中間相遇攻擊過(guò)程，其具體描述如下。

1)選擇中立的消息字wf和wb，將壓縮函數(shù)分為cf和cb兩部分，使cf不依賴于wb,cb不依賴于wf。

3)對(duì)于所有的 wf，向后計(jì)算至相遇點(diǎn)，保存相遇點(diǎn)的變量值，記為L(zhǎng)f。類似地，對(duì)于所有的wb，向前計(jì)算至相遇點(diǎn)，保存相遇點(diǎn)的變量值，記為L(zhǎng)b。

4)重復(fù)步驟2)和步驟3)，直到一個(gè)完全匹配產(chǎn)生為止。

圖1 中間相遇攻擊示意

3.2 偽原根轉(zhuǎn)化為原根

給定壓縮值h，若能找到(IV',M')，使得在初始值IV'下壓縮M'得到壓縮值h，則稱M'為h的偽原根，其中，IV'不等于標(biāo)準(zhǔn)初始值IV。文獻(xiàn)[10]提出一種將偽原根攻擊轉(zhuǎn)化成原根攻擊的方法，其基本過(guò)程如下：假設(shè)雜湊值的長(zhǎng)度為n，偽原根攻擊的復(fù)雜度為2k，一方面，在標(biāo)準(zhǔn)初始值IV下壓縮2(n+k)/2個(gè)隨機(jī)的消息，另一方面，計(jì)算出壓縮值h的2(n?k)/2個(gè)偽原根，根據(jù)生日攻擊可知，中間相遇的期望值的個(gè)數(shù)是2(n+k)/2×2(n?k)/2/2n=1，從而找到原根的計(jì)算復(fù)雜度為2(n+k)/2+2(n?k)/2×2k=2(n+k)/2+1次雜湊運(yùn)算。

3.3 偽原根轉(zhuǎn)化為偽碰撞

記雜湊函數(shù)為H，如果能找到(IV,IV',M,M')，使得 H(IV,M)=H(IV',M')，其中，(IV,M)≠(IV',M')，則稱找到了雜湊函數(shù) H的偽碰撞。偽原根轉(zhuǎn)化成偽碰撞[11]的方法可以概括為：對(duì)于一個(gè)輸出長(zhǎng)度為n的雜湊函數(shù)，假定存在一個(gè)復(fù)雜度為2k、部分匹配為t bit的偽原根攻擊，并且部分匹配位于壓縮函數(shù)的最后一步的輸出。對(duì)于給定的雜湊值，使用偽原根攻擊的方法找到 2(n?t)/2個(gè)不同的 t bit部分匹配消息，則根據(jù)生日攻擊的原理，這些消息以很高的概率存在一個(gè)偽碰撞。此時(shí)，得到一個(gè)偽碰撞所需的復(fù)雜度為2(n?t)/2×2k。例如，令部分匹配長(zhǎng)度t=6，向前向后計(jì)算的過(guò)程各進(jìn)行25次，這樣可以得到24(=25+5/26)個(gè)6 bit的部分匹配，也就是說(shuō)，得到一個(gè) 6 bit的部分匹配所需的復(fù)雜度為2(=25/24)，從而得到一個(gè)偽碰撞所需的復(fù)雜度為2(n?6)/2×2。

4 29步SM3算法的原根攻擊和偽碰撞攻擊

對(duì)于從第1步開始的29步SM3算法進(jìn)行原根攻擊時(shí)，向后的計(jì)算過(guò)程從第15步到第29步，向前的計(jì)算過(guò)程從第14步到第1步，這種分割方法使得中間相遇攻擊中的部分匹配能夠在第 29步進(jìn)行，從而保證偽碰撞攻擊順利進(jìn)行，也為中間消息字的選取提供參考。中立的消息字為wb=w13[26～31]，wf=w2[26～31]，這樣選擇中立消息字的優(yōu)點(diǎn)在于使抵消中立消息字的條件相對(duì)較少，同時(shí)這些條件不影響消息的填充過(guò)程。其中，在向前的計(jì)算過(guò)程中，wf=w2[26～31]未知；在向后的計(jì)算過(guò)程中，wb=w13[26～31]未知。

4.1 設(shè)置消息字

根據(jù)消息拓展過(guò)程可知，w16～w29的拓展過(guò)程如下

由上述拓展過(guò)程可知，1)從w16～w29首先受到w2影響的消息字為w18，另一方面，在向前的計(jì)算過(guò)程中，從第14步到第4步不受w2的影響；2)受w13影響的消息字為w16、w19、w22、w26和 w29(w16～w29)，可以通過(guò)以下的條件來(lái)抵消w13對(duì)w16、w19、w22和w26的影響。

由于事故車轉(zhuǎn)彎半徑過(guò)小，經(jīng)測(cè)量，其弦高h(yuǎn)無(wú)法準(zhǔn)確讀出兩位有效數(shù)字，故使用側(cè)滑速度與車輛碰撞固定物相結(jié)合的公式來(lái)計(jì)算事故車發(fā)生側(cè)滑前的行駛速度。

抵消w13對(duì)w26的影響。

由于 w26=P1(w10⊕w17⊕(w23＜＜＜15))⊕(w13＜＜＜7)⊕w20，首先用 w10抵消 w13對(duì) w26的影響，需要增加條件

由條件(1)可知w10受到w13的影響，又根據(jù)w23的表達(dá)式可知，w23受到w13的影響，筆者用條件(2)抵消w13對(duì)w23的影響，即

類似地，根據(jù) w20和 w17的表達(dá)式可知：w20和 w17受到w13的影響，筆者用條件(3)和條件(4)抵消w20和 w17受到的影響，即

綜上可知：w14～w28中除w16、w19和w22之外，其他消息字均不受w13的影響。

抵消w13對(duì)w22、w19和w16的影響。根據(jù)w22=P1(w6⊕w13⊕(w19＜＜＜15))⊕(w9＜＜＜7)⊕w16，w19=P1(w3⊕w10⊕(w16＜＜＜15))⊕(w6＜＜＜7)⊕ w13，w16=P1(w0⊕w7⊕(w13＜＜＜15))⊕(w3＜＜＜7)⊕ w10，首先用條件(5)抵消w13對(duì)w22的影響。

然后用條件(6)抵消w13對(duì)w19的影響。

由前面的分析可知：w16表達(dá)式中的w3、w7和w10均受到 w13的影響，所以用條件(7)抵消 w13對(duì)w16的影響。

綜上可知：通過(guò)條件(1)到條件(7)對(duì) w0、w1、w3、w4、w6、w7和 w10進(jìn)行了設(shè)定，使得 w14～w28均不受w13的影響。因此，在向后的計(jì)算過(guò)程中，從第15步到第25步不受w13的影響。其中，C1，…，C7為常數(shù)。

4.2 第14步到第1步的計(jì)算

因?yàn)樵谙蚯暗挠?jì)算過(guò)程中，w2[26～31]未知，根據(jù)消息擴(kuò)展算法可知，w16和w17已知，w18未知，從而wi和wi'已知(i=3,…,13）,故從分割處的中間變量值(A14,B14,C14,D14,E14,F14,G14,H14)向前逆向計(jì)算，可以很容易得到(A3,B3,C3,D3,E3,F3,G3,H3)。由此再向前的計(jì)算受w2的影響，其過(guò)程如下。首先考慮

由于w2參與此步的運(yùn)算，且w2[26～31]未知，故可以計(jì)算出 A2,B2,C2，D2[0～25],E2,F2,G2和H2[0～25]。然后考慮

根據(jù) SM3算法，易知：A1、B1、C1[0～25]、D1[0～25]、E1、F1、G1[0～25]和 H1[0～25]能夠計(jì)算出來(lái)。最后考慮

根據(jù) SM3 算法，易知：A0、B0[0～16,23～31]、C0[0～25]、D0[0～16]、E0、F0[0～6,13～31]、G0[0～25]和H0[0～6]能夠計(jì)算出來(lái)。

4.3 第15步到第29步的計(jì)算

因?yàn)樵谙蚝蟮挠?jì)算過(guò)程中，w13[26～31]未知，根據(jù) 4.1節(jié)消息字的設(shè)置可得，wi和 wi'已知(i=14,…,24)，故從分割處的中間變量值(A14,B14,C14,D14,E14,F14,G14,H14)向后計(jì)算，很容易得到(A25,B25,C25,D25,E25,F25,G25,H25)的值。

因?yàn)閰⑴c第26步計(jì)算的消息字為w25和w25'=w25⊕w29，而 w29受 w13的影響，所以 A26受 w13的影響，而(B26,C26,D26,E26,F26,G26,H26)不受w13的影響。特別地，E26不受w13的影響，亦即可以得到E26的值，從而根據(jù) SM3算法可知：H29=G28=F27＜＜＜19=E26＜＜＜19 可以計(jì)算出來(lái)。

綜合第14步到第1步的計(jì)算過(guò)程和第14步到第 29步的計(jì)算過(guò)程，可以得到部分匹配的檢測(cè)條件為H0[0～6]⊕H29[0～6]=H[0～6]是否成立。

4.4 29步SM3算法的原根攻擊

通過(guò)以上的分析可知，為了保證w13對(duì)w16、w19、w22和w26不產(chǎn)生影響，需要限定7個(gè)消息字w0、w1、w3、w4、w6、w7和w10的條件，一共224(=7×32)bit。對(duì)于一個(gè)消息分組來(lái)說(shuō)，消息字剩余的自由度為276(=512–224–2×6)，進(jìn)一步考慮消息填充過(guò)程中用到的w13的第0位，w14和w15共65 bit，最終剩余的消息字的自由度為211(=276–65)。另一方面，中間變量(A14,B14,C14,D14,E14,F14,G14,H14)沒有任何條件限制，因此可以增加256個(gè)自由度，從而可用的自由度為467(=211+256)＞256。顯然有足夠的自由度來(lái)構(gòu)造出一個(gè)有效的對(duì)29步SM3算法的偽原根攻擊。對(duì)于給定的雜湊值h=(A,B,C,D,E,F,G,H)，29步的SM3算法的偽原根攻擊過(guò)程如下。

1)隨機(jī)選取中間變量(A14,B14,C14,D14,E14,F14,G14,H14)。對(duì)于消息字w0～w15，隨機(jī)賦值給除w2[26～31]和 w13[26～31]之外的其他消息字，使得 4.1節(jié)的條件(1)～條件(7)滿足，且消息填充滿足。

2)對(duì)于所有的 w13[26～31]，向前計(jì)算得(A3,B3,C3,D3,E3,F3,G3,H3)。用(w2∧03ffffff)代替 w2向前計(jì)算得 (A0,B0,C0,D0,E0,F0,G0,H0)。保存(A3,B3,C3,D3,E3,F3,G3,H3,H0,w13[26～31])到列表Lb中。

3)對(duì)于所有的 w2[26～31]，向后計(jì)算得 (A25,B25,C25,D25,E25,F25,G25,H25)。在第26步，計(jì)算E26的值。保存(A25,B25,C25,D25,E25,F25,G25,H25,E26＜＜＜19,w2[26～31])到列表 Lf中。

4)判斷 H0[0～6]⊕H29[0～6]是否等于 H[0～6]。若相等，則使用相應(yīng)的(A3,B3,C3,D3,E3,F3,G3,H3)和w2[26～31]向前計(jì)算得(A0,B0,C0,D0,E0,F0,G0,H0)；使用相應(yīng)的(A25,B25,C25,D25,E25,F25,G25,H25)和w13[26～31]向后計(jì)算得(A29,B29,C29,D29,E29,F29,G29,H29)。

5)判斷(A0,B0,C0,D0,E0,F0,G0,H0)⊕(A29,B29,C29,D29,E29,F29,G29,H29)是否等于h。若相等，則相應(yīng)的消息分組(w0,…,w15)即為29步 SM3算法的一個(gè)偽原根。若不相等，則重復(fù)步驟1)～步驟4)，直到找到一個(gè)29步SM3的偽原根。

上述攻擊的時(shí)間復(fù)雜度估計(jì)如下：由步驟2)和步驟3)可知，共有26×26=212個(gè)組合，而步驟4)“中間相遇”的概率是 2?7，故做一次步驟2)和步驟3)可以得到 212?7=25個(gè)“中間相遇”，而做一次步驟2)和步驟3)的復(fù)雜度約為26次29步SM3算法壓縮操作，故得到 7 bit“中間相遇”值的復(fù)雜度是26/25=2。從而29步SM3算法的偽原根攻擊的復(fù)雜度為2256?7×2=2250。

使用偽原根攻擊轉(zhuǎn)化原根攻擊的方法(見 3.2節(jié))，可以得到對(duì)29步SM3算法的原根攻擊，其時(shí)間復(fù)雜度為2254(=2256+250)/2+1)。

4.5 29步SM3算法的偽碰撞攻擊

根據(jù)偽原根攻擊轉(zhuǎn)化為偽碰撞攻擊的方法(見3.3節(jié))，為了提高效率，把偽原根攻擊中部分匹配的判斷條件改為H0[0～5]⊕H29[0～5]是否等于 H[0～5]，可以得到29步SM3算法的偽碰撞攻擊，其時(shí)間復(fù)雜度為2125=2(256?6)/2×20，具體 SM3算法的攻擊結(jié)果如表1所示。

表1 SM3算法的攻擊結(jié)果

5 結(jié)束語(yǔ)

本文給出了29步SM3算法的原根攻擊，并把它轉(zhuǎn)化為對(duì)29步SM3算法的偽碰撞攻擊。與已知的攻擊結(jié)果相比，本文的攻擊是從第1步開始的，且滿足消息填充。表1給出了SM3算法的攻擊結(jié)果比較。雖然從第1步開始的29步SM3算法不能有效地抵抗原根攻擊和偽碰撞攻擊，但是由于SM3算法的快速擴(kuò)散能力，完整的 SM3算法仍具有抵抗各種已知攻擊的能力，具有非常高的安全性。如何發(fā)現(xiàn)并利用 SM3的其他特點(diǎn)來(lái)分析更多步數(shù)的算法是下一步的研究重點(diǎn)。

[1]WANG X,YU H. How to break MD5 and other hash functions[A].EUROCRYPT 2005[C]. Aarhus,Denmark,2005. 19-35.

[2]WANG X,YIN Y,YU H. Finding collisions in the full SHA-1[A].CRYPTO 2005[C]. Santa Barbara,California,USA,2005. 17-36.

[3]DIFFIE W,HELLMAN M. Exhaustive cryptanalysis of the NBS data encryption standard[J]. Computer,1977,10(6):74-84.

[4]AOKI K,SASAKI Y. Preimage attacks on one-block MD4,63-step MD5 and more[A]. SAC 2008[C]. New Brunswick,Canada,2008.103-119.

[5]National Institute of Standards and Technology. Announcing request for candidate algorithm nominations for a new cryptographic hash algorithm (SHA-3)family[EB/OL]. http://csrc.nist.gov/ groups/ST/hash/documents/ FR_ Notice_Nov07.pdf,2008.

[6]SM3 hash function[EB/OL]. http://www.oscca.gov.cn/UpFile/20101222141857786.pdf/,2010.

[7]ZOU J,WU W,WU S,et al. Preimage attacks on step-reduced SM3 hash function[A]. ICISC 2011[C]. Seoul Korea,2011.375-390.

[8]KIRCANSKI A,SHEN Y,WANG G,et al. Boomerang and sliderotational analysis of SM3 hash function[A]. SAC 2012[C]. Windsor,Canada,2012.305-321.

[9]WANG G,SHEN Y. Preimage and pseudo-collision attacks on stepreduced SM3 hash function[EB/OL]. http://eprint.iacr.org/2012/640/,2012.

[10]MENEZES A J,OORSCHOT P C,VANSTONE S. Handbook of Applied Cryptography[M]. CRC Press,1996.

[11]LI J,ISOBE T,SHIBUTANI K. Converting meetin-the-middle preimage attack into pseudo collision attack: application to SHA-2[A].FSE 2012[C]. Washington DC,USA,2012.264-286.