SMS4-like結(jié)構(gòu)以及NBC 算法的量子算法攻擊研究

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

1. 清華大學(xué) 計算機科學(xué)與技術(shù)系, 北京100084

2. 北京衛(wèi)星信息工程研究所, 北京100086

1 引言

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

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

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

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

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

表1 SMS4 算法的經(jīng)典方法分析工作Table 1 Main classic cryptanalytic results on SMS4

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

2 背景知識

2.1 Simon 算法

2.2 Grover 算法

2.3 量子密鑰恢復(fù)攻擊

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

圖1 1 輪SMS4 結(jié)構(gòu)Figure 1 Structure of 1-round SMS4

4 對d 分支的SMS4-like 結(jié)構(gòu)的量子算法攻擊

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

對d分支的SMS4-like 結(jié)構(gòu)構(gòu)造得到周期函數(shù)f如下:

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

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

圖4 d 分支的1 輪SMS4-like 結(jié)構(gòu)Figure 4 Structure of 1-round SMS4-like with d branches

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

NBC 算法為中國全國密碼算法設(shè)計競賽分組算法第二輪入選算法之一. NBC 算法采用32 輪改進(jìn)的第二類廣義Feistel 結(jié)構(gòu), 擴散層選用了新的塊置換, 在擴散效果上優(yōu)于擴散層采用循環(huán)移位的第二類廣義Feistel 結(jié)構(gòu). 1 輪NBC 算法結(jié)構(gòu)如圖5 和圖6 所示.

圖5 8 分支的1 輪NBC-128 結(jié)構(gòu)Figure 5 Structure of 1-round NBC-128 with d=8

圖6 16 分支的1 輪NBC-256 結(jié)構(gòu)Figure 6 Structure of 1-round NBC-256 with d=16

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

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

5 結(jié)論

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

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