黃 琳 弓曉鋒 周 慧 梁正華

（1.貴州省科技信息中心，貴州貴陽 550002；2.貴州省科技創(chuàng)新中心有限責(zé)任公司，貴州貴陽 550002）

0 引言

雜湊函數(shù)在密碼學(xué)中具有重要的地位，安全的雜湊函數(shù)能夠抵抗碰撞攻擊、原根攻擊和第二原根攻擊等[1]。很多的方式能夠攻擊雜湊函數(shù)，比如基于模差分的碰撞攻擊[2-3]方法、基于中間相遇攻擊[4]的原根攻擊[5]方法等。各個(gè)國家早已制定相關(guān)的雜湊算法標(biāo)準(zhǔn)，我國于2010年公布了中國商用雜湊算法標(biāo)準(zhǔn)，并且命名為SM3雜湊算法。該算法能夠?qū)斎朊魑男畔⑦M(jìn)行填充分塊，將明文分為有限個(gè)512bit的數(shù)據(jù)塊，再將生成的數(shù)據(jù)塊進(jìn)行擴(kuò)展，隨后進(jìn)行迭代加密，最終輸出密文數(shù)據(jù)。因?yàn)槊恳惠喌牡鷫嚎s過程生成的密文長(zhǎng)度是固定的，所以理論上SM3雜湊算法是一定能夠受到偽原根攻擊，攻擊輪數(shù)不同，時(shí)間復(fù)雜度也會(huì)不同。在加密時(shí)，SM3雜湊算法部分輪數(shù)是不隨機(jī)的，所以攻擊輪數(shù)的減少對(duì)于攻擊算法的隨機(jī)性影響較大。

1 SM3雜湊密碼算法

密碼雜湊算法是類基礎(chǔ)密碼算法之一，該算法于2012年發(fā)布為密碼行業(yè)標(biāo)準(zhǔn)（GM/T 0004-2012），2016 年發(fā)布為國家密碼雜湊算法標(biāo)準(zhǔn)（GB/T 32905-2016），它可以將任意長(zhǎng)度的消息壓縮成固定長(zhǎng)度的摘要，主要用于數(shù)據(jù)的安全傳輸?shù)?。雜湊函數(shù)需要滿足碰撞穩(wěn)固性，即對(duì)于任意兩個(gè)不同的輸入，其輸出也應(yīng)該是不同的。目前，對(duì)SM3密碼雜湊算法的攻擊還比較少，尚未發(fā)現(xiàn)明顯的碰撞攻擊方法。原根穩(wěn)固性和第二原根穩(wěn)固性是評(píng)價(jià)雜湊函數(shù)安全性的重要指標(biāo)，SM3密碼雜湊算法在設(shè)計(jì)上已經(jīng)考慮了這些特性，使其對(duì)原根攻擊和第二原根攻擊具有一定的抵御能力。

SM3密碼雜湊算法的消息分組長(zhǎng)度為512b，輸出摘要長(zhǎng)度為256b[6]。SM3算法的壓縮函數(shù)與國際常用的SHA256雜湊算法的壓縮函數(shù)具有相似性，SM3算法是在SHA-256基礎(chǔ)上改進(jìn)的一種商用密碼算法，應(yīng)用于安全傳輸和數(shù)字簽名等方面。但SM3雜湊算法的壓縮函數(shù)具有自己的特點(diǎn)，其結(jié)構(gòu)及消息擴(kuò)展流程設(shè)計(jì)思路更加復(fù)雜。例如，SM3算法的壓縮函數(shù)每一輪使用2個(gè)消息字，消息擴(kuò)展使用5個(gè)消息字。因此，SM3國產(chǎn)密碼算法相對(duì)于MD5、SHA0、SHA1、SHA256等常見雜湊算法，在安全性方面優(yōu)勢(shì)突出。算法的實(shí)施流程主要可以分為4個(gè)方面，即消息填充、消息擴(kuò)展、迭代壓縮和結(jié)果輸出。

2 偽原根攻擊

偽原根攻擊的原理是基于對(duì)偽隨機(jī)數(shù)生成器輸出模式的分析。攻擊者通過觀察和分析生成的偽隨機(jī)數(shù)序列，試圖發(fā)現(xiàn)其中的規(guī)律或模式。攻擊者可以利用各種統(tǒng)計(jì)方法、頻率分析、模式識(shí)別等技術(shù)實(shí)現(xiàn)。一旦攻擊者成功識(shí)別出偽隨機(jī)數(shù)生成器的模式，即可利用這個(gè)信息推測(cè)密鑰、預(yù)測(cè)未來的隨機(jī)數(shù)序列，或者執(zhí)行其他惡意操作，這可能導(dǎo)致加密數(shù)據(jù)的解密、身份驗(yàn)證的繞過或其他安全漏洞的利用。

SM3雜湊算法輸入的是明文，輸出的是密文，可以將其看作是一個(gè)大型的Hash映射，只要輸出長(zhǎng)度確定，就一定會(huì)出現(xiàn)不同的明文映射為同一個(gè)密文。偽原根攻擊的原理也是如此，依靠計(jì)算機(jī)計(jì)算出不同輸入值，通過Hash函數(shù)映射到同一輸出值，從而擬定一份虛假的明文通過Hash算法映射為相同的密文，發(fā)送給接收方，從而達(dá)到欺詐的目的。偽原根攻擊示意圖如圖1所示。

圖1 偽原根攻擊示意圖

可以看到攔截方攔截了發(fā)送方的密文Y后，偽造了一份明文X′，但是明文X′經(jīng)過HASH算法生成了與發(fā)送方發(fā)送的密文Y一樣的密文。

3 中間相遇攻擊

中間相遇攻擊是依靠?jī)啥吮平姆绞竭M(jìn)行解密，故稱為中間相遇攻擊。中間相遇攻擊依靠可能的加密密鑰對(duì)明文X進(jìn)行加密，生成一系列的明密文對(duì)L1（X,Y1）和對(duì)應(yīng)的加密密鑰K1，然后對(duì)截獲的密文Y用可能的解密密鑰進(jìn)行解密，生成一系列的明密文對(duì)L2(X2,Y)和對(duì)應(yīng)的解密密鑰對(duì)K2，如果L1和L2中有相同的明密文對(duì)，則中間相遇攻擊算法成功實(shí)施，通信雙方的密鑰對(duì)被破解。

因?yàn)镾M3雜湊算法是迭代壓縮，且用到的雜湊函數(shù)均是同一個(gè)，加密方式唯一，所以上一輪的密文是下一輪加密的明文，但是根據(jù)其加密規(guī)則，前后加密的消息之間存在依賴，加密的具體輪數(shù)不同，前后的依賴關(guān)系也有差異，“最薄弱”的部分也有所不同。SM3雜湊算法的中間相遇攻擊，挑選消息傳遞中前后依賴較少的部分進(jìn)行攻擊，挑選這部分進(jìn)行攻擊，相應(yīng)的計(jì)算復(fù)雜度較小。

對(duì)于28輪的偽原根攻擊，第13輪的迭代壓縮最為“薄弱”，前后依賴較小，所以可選擇從兩端向中間計(jì)算的方式進(jìn)行計(jì)算。首先對(duì)前14輪進(jìn)行計(jì)算，再計(jì)算15～28輪，由兩端向中間計(jì)算。這樣的方式可以同時(shí)進(jìn)行并行計(jì)算，縮短計(jì)算時(shí)間。同時(shí)，在每一輪的計(jì)算中，采取中間相遇攻擊的方式進(jìn)行計(jì)算。中間相遇的偽原根攻擊方法就是把中間相遇的攻擊思想用到偽原根攻擊中，目的是用空間換時(shí)間，進(jìn)行并行計(jì)算，縮短計(jì)算時(shí)間。

4 差分中間相遇攻擊

差分中間相遇攻擊實(shí)際是利用差分的思想實(shí)現(xiàn)中間相遇攻擊。差分是用來衡量?jī)蓚€(gè)對(duì)象之間的差異性，差分通常是一個(gè)固定的值，可以用來區(qū)分兩個(gè)不同的明文。攻擊者選擇兩個(gè)明文，并計(jì)算它們之間的差分。使用相同的密鑰對(duì)兩個(gè)明文進(jìn)行加密，得到兩個(gè)密文，然后計(jì)算這兩個(gè)密文之間的差分。由于加密算法的雪崩效應(yīng)，即使明文差分很小，密文差分也可能很大。攻擊者通過窮舉所有可能的密鑰，生成大量的中間結(jié)果，并將這些結(jié)果存儲(chǔ)在一個(gè)列表中。列表通常很大，需要占用大量的存儲(chǔ)空間。同時(shí)，攻擊者使用另一個(gè)列表存儲(chǔ)所有可能的密文差分，并對(duì)這兩個(gè)列表進(jìn)行比對(duì)。當(dāng)找到一個(gè)匹配項(xiàng)時(shí)，就意味著找到了一個(gè)正確的密鑰。再使用找到的密鑰對(duì)其他明密文對(duì)進(jìn)行驗(yàn)證，確保找到的密鑰的準(zhǔn)確性。可以將SM3雜湊函數(shù)中的壓縮函數(shù)分為兩部分，即CF1和CF2。利用兩個(gè)壓縮函數(shù)，在兩個(gè)獨(dú)立的線性空間依靠差分的思想尋找一個(gè)原像映射，使真實(shí)的原像與偽原像建立一個(gè)映射，從而使偽原像能和原像有一樣的密文輸出。偽原像和原像的映射依靠差分思想實(shí)現(xiàn)，映射的情況依靠中間相遇攻擊的思想實(shí)現(xiàn)。

5 攻擊輪數(shù)減少的隨機(jī)性分析

攻擊輪數(shù)減少的隨機(jī)性分析可以幫助理解算法在遭受攻擊后是否仍然能夠提供足夠的安全性。在密碼學(xué)中，攻擊輪數(shù)是一個(gè)重要的指標(biāo)，它指的是攻擊者需要進(jìn)行多少次嘗試或迭代才能破解系統(tǒng)或獲取敏感信息。當(dāng)攻擊輪數(shù)減少時(shí)，意味著攻擊者需要較少的嘗試就能成功，降低了系統(tǒng)的安全性。隨機(jī)性是密碼學(xué)算法的一個(gè)重要屬性，通過一個(gè)良好的隨機(jī)數(shù)生成器能夠產(chǎn)生看似隨機(jī)的數(shù)值序列，使攻擊者難以預(yù)測(cè)未來的數(shù)值或識(shí)別出任何模式。然而，當(dāng)攻擊輪數(shù)減少時(shí)，隨機(jī)性可能會(huì)受到影響。攻擊輪數(shù)減少可能導(dǎo)致隨機(jī)性的降低，因?yàn)楣粽呖梢酝ㄟ^分析較少的迭代次數(shù)更容易地識(shí)別出模式或規(guī)律。例如，在偽原根攻擊中，攻擊者通過分析偽隨機(jī)數(shù)生成器的輸出模式推測(cè)密鑰或預(yù)測(cè)未來的隨機(jī)數(shù)序列。如果攻擊輪數(shù)減少，攻擊者可能只需要分析較少的輸出就能找到模式，從而增加了破解成功的可能性。對(duì)于密碼學(xué)算法的安全性和隨機(jī)性評(píng)估，需要綜合考慮攻擊輪數(shù)減少對(duì)系統(tǒng)安全性的影響，并采取適當(dāng)?shù)陌踩胧?yīng)對(duì)潛在的威脅和攻擊。

SM3算法本身從第1輪到35輪是不隨機(jī)的[7]，所以對(duì)于SM3算法的偽原根攻擊在最后輸出雜湊值位數(shù)固定的情況下是不隨機(jī)的。只要攻擊輪數(shù)不超過35輪，在28輪的基礎(chǔ)上減少攻擊輪數(shù)，其攻擊算法和SM3雜湊算法都不是隨機(jī)的，為偽原根攻擊提供新的方案，對(duì)于迭代壓縮輪數(shù)不高于35輪的SM3算法，可以通過破解中間消息的迭代壓縮過程破解全部壓縮過程，所以SM3雜湊算法應(yīng)該盡可能避免加密輪數(shù)低于35輪，從而避免密鑰對(duì)的泄露。

6 結(jié)語

SM3雜湊算法在我國加密算法體系當(dāng)中占據(jù)較為重要的地位，其安全性分析十分有必要而且有意義。本文對(duì)雜湊算法進(jìn)行了簡(jiǎn)要介紹，并且分析了部分雜湊算法中偽原根攻擊的部分方法，對(duì)28輪偽原根攻擊的攻擊輪數(shù)減少后的隨機(jī)性進(jìn)行了分析，得出了隨機(jī)性分析的結(jié)論，即前28輪偽原根攻擊隨著攻擊輪數(shù)的減少，隨機(jī)性不受影響，并且前28輪偽原根攻擊是不隨機(jī)的。

SM3密碼雜湊算法可以用于生成數(shù)字簽名，確保消息的完整性和發(fā)送者的身份。通過該算法，也可以對(duì)消息進(jìn)行認(rèn)證，驗(yàn)證消息是否被篡改。同時(shí)，該算法還可以用于檢測(cè)數(shù)據(jù)的完整性，確保數(shù)據(jù)在傳輸或存儲(chǔ)過程中沒有被修改。SM3密碼雜湊算法在安全性方面具有良好的表現(xiàn)，并已得到廣泛應(yīng)用。