SMS4-like結構以及NBC 算法的量子算法攻擊研究

尤啟迪, 錢 新, 周 旋, 袁 野, 吳兆陽

1. 清華大學 計算機科學與技術系, 北京100084

2. 北京衛星信息工程研究所, 北京100086

1 引言

廣義Feistel 結構是用來設計分組密碼算法的基本結構之一, 該類結構繼承了Feistel 結構[1]加解密一致的特點, 同時使得輪函數設計更加靈活、輕量. 在1989 年美密會上, 鄭等人[2]總結了三類廣義Feistel 結構, 并記為Type-1、Type-2 和Type-3 型廣義Feistel. 后來, 其他類型的廣義Feistel 或者非平衡的Feistel 結構被提出[3-5]. 基于廣義Feistel 結構設計的密碼算法有很多,包括分組密碼CAST-256[6]、CLEFIA[7]、SMS4[8], 密碼置換函數Simpira[9], 以及哈希函數MD5[10]和SHA-1[11]等. 近來, 廣義Feistel 結構還被用于設計適用于多方安全計算、同態加密等場景的分組密碼算法[12].

隨著量子計算、量子理論的發展迅速, 量子信息科學的發展為密碼學的發展也帶來了一定挑戰.Grover[13]提出了一種無序數據庫的標準搜索算法, 以Grover 算法為代表的量子搜索算法以及推廣算法的計算復雜度是經典算法的平方加速, 可用于加速密鑰的搜索, 對所有密碼產生了一定威脅; Shor 算法[14,15]可用于分解大整數、求解離散對數, 其計算復雜度是對經典算法的指數加速, 可用于相關公鑰密碼中的數學難題的加速求解,對RSA、ECC 等為代表的公鑰密碼產生了一定威脅. Kuwakado 和Morii[16]首先利用Simon 算法[17]構造了3 輪Feistel 結構的多項式時間量子區分器. 隨后, Even-Mansour 算法的量子密鑰恢復攻擊[18]、各種MAC 算法的偽造攻擊[19]、AEZ 的量子破解[20]、FX 結構的密鑰恢復攻擊[21], 以及Feistel 結構的量子密鑰恢復攻擊[22-26]和量子安全性證明[27]等相繼被提出. 廣義Feistel的結構的量子分析首先由董曉陽等[28]提出并給出了Type-1、Type-2 以及SMS4-like 的廣義Feistel 結構的量子區分攻擊以及密鑰恢復. 隨后, 倪博煜等[29,30]和羅宜元[31]對相關結果進行了改進.

SMS4[8]算法是中國無線標準中使用的分組加密算法, 于2006 年2 月發布,在2012 年被確定為國家商用分組密碼標準并更名為SM4, 服務于無線局域網認證和隱私的基礎設施安全性. SMS4 算法采用32輪Feistel 非平衡結構, 其分組長度和密鑰的長度均為128 位, 每輪輸入分組數k=4 , 其中右邊3 個分組異或后作為該輪輪函數fi的輸入. SMS4 中的密鑰擴展方案也利用了32 輪的非平衡Feistel 結構. SMS4算法的廣義形式SMS4-like 結構仍保留了SMS4 結構中將右邊k?1 個明文分組先異或, 然后再輸入到輪函數fi中的特點. NBC 算法[32]為中國全國密碼算法設計競賽分組算法第二輪入選算法之一. NBC 算法采用32 輪改進的第二類廣義Feistel 結構, 擴散層選用了新的塊置換, 在擴散效果上優于擴散層采用循環移位的第二類廣義Feistel 結構. 算法支持128/128, 128/256, 256/256 等三種分組長度和密鑰長度, 其中128 比特分組長度的NBC 算法(NBC-128) 為8 分支, 256 比特分組長度的NBC 算法(NBC-256) 為16 分支. 密鑰擴展算法的設計與S 盒類似, 采用基于n比特字的16 級非線性反饋移位寄存器.

目前對SMS4 算法的主要經典方法的代表性分析工作包括不可能差分攻擊[33]、矩陣攻擊[34]、相關密鑰攻擊[35]、多維零相關線性攻擊[36]以及線性攻擊[37]、差分攻擊[38]等, 具體見表1. 對于SMS4 算法攻擊輪數最多的方法有線性分析和差分攻擊, 均可以達到23 輪. 其中最好的線性攻擊結果是2014 年Liu 等人[37]給出的23 輪SMS4 線性攻擊, 數據復雜度為2122.7, 時間復雜度為2126.6; 2014 年Su 等人[38]給出的23 輪SMS4 差分攻擊, 數據復雜度為2118, 時間復雜度為2126.7. 在經典方法下, 張立廷、吳文玲等[39]利用可證明安全方法證明了當SMS4-like 結構的分支數d為奇數時, SMS4-like 結構不是偽隨機的. 當k為偶數時, 2d ?2 輪SMS4-like 結構不是偽隨機的, 2d ?1 輪SMS4-like 結構是偽隨機的,3d ?2 輪SMS4-like 結構是超偽隨機的. 特別地, 7 輪SMS4 結構是偽隨機的, 若輪函數f1,f2,··· ,f7滿足為相互獨立的偽隨機函數;10 輪SMS4 結構是超偽隨機的, 若輪函數f1,f2,··· ,f10滿足為相互獨立的偽隨機函數. 顯然, 在量子環境中SMS4-like 結構已不具備同樣的安全性. 表2 給出SMS4 算法的量子算法分析工作.

本文使用周期函數f構建量子區分器, 進行量子密鑰恢復攻擊, 在第3 節中針對SMS4 構造具有多項式時間的6 輪量子區分器, 進行10 輪量子密鑰恢復攻擊; 在第4 節中針對SMS4-like 結構構造具有多項式時間的(2d ?2) 輪量子區分器, 進行(3d ?2) 輪量子密鑰恢復攻擊. 同時, 本文將在第5 節中針對改進的第二類廣義Feistel 結構的代表算法NBC 進行量子算法分析. 需要指出的是, 根據Zhandry 的研究工作[40], 分組密碼的量子分析模型主要有兩種: 標準安全模型、量子安全模型. 兩種分析模型的區別在于: 在標準安全模型中, 攻擊者對預言機的查詢只能通過經典方法進行, 對數據的處理可以使用量子計算機; 在量子安全模型中, 攻擊者對預言機的查詢可以以量子疊加態的方式進行, 并獲得相應的輸出疊加態,對數據的處理也可以使用量子計算機. 本文的分析基于量子安全模型.

表1 SMS4 算法的經典方法分析工作Table 1 Main classic cryptanalytic results on SMS4

表2 SMS4 算法的量子區分攻擊Table 2 Quantum distinguishing attacks on SMS4

2 背景知識

2.1 Simon 算法

2.2 Grover 算法

2.3 量子密鑰恢復攻擊

3 對SMS4 算法的量子算法攻擊

圖1 1 輪SMS4 結構Figure 1 Structure of 1-round SMS4

4 對d 分支的SMS4-like 結構的量子算法攻擊

SMS4 算法的廣義形式SMS4-like 結構仍保留了SMS4 結構中將右邊k?1 個明文分組先異或, 然后再輸入到輪函數fi中的特點.d分支的1 輪SMS4-like 結構如圖4 所示.

對d分支的SMS4-like 結構構造得到周期函數f如下:

圖2 SMS4 的6 輪量子區分器Figure 2 6-round quantum distinguisher on SMS4

圖3 SMS4 的10 輪量子密鑰恢復攻擊Figure 3 10-round quantum key recovery attack on SMS4

圖4 d 分支的1 輪SMS4-like 結構Figure 4 Structure of 1-round SMS4-like with d branches

4.1 對NBC 算法的量子算法攻擊

NBC 算法為中國全國密碼算法設計競賽分組算法第二輪入選算法之一. NBC 算法采用32 輪改進的第二類廣義Feistel 結構, 擴散層選用了新的塊置換, 在擴散效果上優于擴散層采用循環移位的第二類廣義Feistel 結構. 1 輪NBC 算法結構如圖5 和圖6 所示.

圖5 8 分支的1 輪NBC-128 結構Figure 5 Structure of 1-round NBC-128 with d=8

圖6 16 分支的1 輪NBC-256 結構Figure 6 Structure of 1-round NBC-256 with d=16

圖7 NBC-128 的6 輪量子區分器Figure 7 6-round quantum distinguisher on NBC-128

類似的, 針對NBC-256, 借助周期函數f可以構造具有多項式時間的10 輪量子區分器, 進行16 輪量子密鑰恢復攻擊. 具體過程此處不再贅述. 從分析結果可以看出,NBC 算法作為改進的第二類廣義Feistel結構的代表算法之一, 其安全性高于第二類廣義Feistel 結構.

5 結論

本文介紹了SMS4 算法在經典方法下的分析工作以及在量子算法分析工作, 總結了利用Simon 量子算法和Grover 搜索算法對分組密碼中的部分代表性密碼結構進行量子算法攻擊的方法. 本文給出了首次對SMS4-like 結構和作為改進的第二類廣義Feistel 結構的代表算法之一的NBC 算法的量子算法攻擊.通過使用周期函數f構建量子區分器, 進行量子密鑰恢復攻擊, 對SMS4 可以構造具有多項式時間的6輪量子區分器, 進行10 輪量子密鑰恢復攻擊, 攻擊輪數較之前最優結果增加1 輪; 對SMS4-like 結構可以構造具有多項式時間的(2d ?2) 輪量子區分器, 進行(3d ?2) 輪量子密鑰恢復攻擊. 對NBC-128 可以構造具有多項式時間的6 輪量子區分器, 進行11 輪量子密鑰恢復攻擊; 對NBC-256 可以構造具有多項式時間的10 輪量子區分器, 進行16 輪量子密鑰恢復攻擊. 論證了NBC 算法作為改進的第二類廣義Feistel 結構的代表算法之一, 其安全性高于第二類廣義Feistel 結構.

圖8 NBC-128 的11 輪量子密鑰恢復攻擊Figure 8 11-round quantum key recovery attack on NBC-128