SM3密碼雜湊算法的安全性問題分析及應(yīng)用＊

黃 琳 弓曉鋒 周 慧 梁正華

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

0 引言

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

1 SM3雜湊密碼算法

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

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

2 偽原根攻擊

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

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

圖1 偽原根攻擊示意圖

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

3 中間相遇攻擊

中間相遇攻擊是依靠兩端逼近的方式進行解密，故稱為中間相遇攻擊。中間相遇攻擊依靠可能的加密密鑰對明文X進行加密，生成一系列的明密文對L1（X,Y1）和對應(yīng)的加密密鑰K1，然后對截獲的密文Y用可能的解密密鑰進行解密，生成一系列的明密文對L2(X2,Y)和對應(yīng)的解密密鑰對K2，如果L1和L2中有相同的明密文對，則中間相遇攻擊算法成功實施，通信雙方的密鑰對被破解。

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

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

4 差分中間相遇攻擊

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

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

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

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

6 結(jié)語

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

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