李艷俊， 易子晗， 汪 振， 劉 健

1. 中國電子科技集團公司第十五研究所 信息產(chǎn)業(yè)信息安全測評中心， 北京 100083

2. 北京電子科技學院， 北京 100070

3. 桂林電子科技大學 廣西密碼學與信息安全重點實驗室， 桂林 541004

1 引言

近幾年， 量子計算模型下密碼算法的安全性成為密碼研究人員關注的焦點之一. 1988 年， 3 輪Feistel結(jié)構(gòu)被證明[1]是偽隨機置換， 但2010 年3 輪Feistel 結(jié)構(gòu)被發(fā)現(xiàn)存在一個固定的周期， 通過使用Simon算法在O(n) 時間復雜度內(nèi)恢復出周期， 這一結(jié)果比經(jīng)典方法O(nn/2) 的時間復雜度有了很大的提高[2].緊接著在2012 年， 基于Simon 算法Kuwakado 等人對Even-Mansour 結(jié)構(gòu)進行了量子分析， 將恢復密鑰的攻擊復雜度由傳統(tǒng)分析需要的指數(shù)時間降低為量子分析需要的多項式時間[3]. 2016 年美密會上，Kaplan 等人[4]對Simon 算法進行了擴充和完善， 并對一系列密碼結(jié)構(gòu)工作模式進行了量子攻擊， 他們的結(jié)果表明在量子計算機下實現(xiàn)的這些結(jié)構(gòu)將不再安全. 在同一年的FSE 上， 他們也提出了量子差分和線性分析[5]. 2017 年， Leander 等人[6]用Simon 算法和Grover 算法組合來攻擊FX 結(jié)構(gòu). 國內(nèi)的Dong等人[7，8]對廣義Feistel 結(jié)構(gòu)構(gòu)建了密鑰恢復攻擊， 并結(jié)合Simon 算法改進了經(jīng)典的滑動攻擊. 2018 年，Hosoyamada 等人[9]對Feistel 擴展結(jié)構(gòu)進行了量子中間相遇攻擊， 結(jié)果顯示量子計算機能夠顯著增加中間相遇攻擊的能力. 2020 年， Dong 等人[10]結(jié)合Simon 算法對滑動攻擊進行了改進， 并對Feistel 的一些變體和GOST 進行了密鑰恢復攻擊. 同年， Luo 等人[11]對三輪MISTY-L 和MISTY-R 進行了區(qū)分攻擊， 最后論證了在選擇明文攻擊下， 三輪Lai-Massey 結(jié)構(gòu)能夠抵抗Simon 量子算法攻擊.

1989 年美密會上， Zheng 等人[12]將一些廣義的Feistel 結(jié)構(gòu)總結(jié)為Type-I/II/III 型GFS， CAST-256 基于Type-I 型GFS，CLEFIA 和RC6 基于Type-II 型GFS，MARS 基于Type-III 型GFS.其中較為流行版本被稱為Type-II 型GFS， 它將消息劃分為k個子塊(k ＞2)， 并對每兩個子塊應用一次Feistel變換， 然后執(zhí)行k個子塊的循環(huán)移位. 近年來， Type-II 型GFS 因其簡單性和高并行性而受到廣泛關注.然而， 其缺點是具有較大的k時擴散特性較差. 2010 年， Tomoyasu 和Kazuhiko[13]通過用不同的置換替換循環(huán)移位來減少輪數(shù)， 可以改善Type-II 型GFS 的擴散特性， 使其達到足夠的安全級別. 2019 年，Dong 等人[8]研究了一些廣義Feistel 結(jié)構(gòu)的量子區(qū)分器， 對于d分支Type-II 型GFS (類似CAST-256的結(jié)構(gòu))， 引入了具有多項式時間的(2d-1) 輪多項式時間量子區(qū)分器. 對于2d分支Type-II 型GFS (類似RC6/CLEFIA 的結(jié)構(gòu))， 給出了具有多項式時間的(2d+1) 輪量子區(qū)分器. 2020 年， Ni 等人[14]在量子選擇明文攻擊(qCPA)條件下和量子選擇密文攻擊(qCCA)條件下， 對Type-I 型GFS 進行研究， 給出了改進的多項式時間量子區(qū)分器， 并將上述區(qū)分攻擊應用到CAST-256 分組密碼中， 得到了12 輪qCPA多項式時間量子區(qū)分器， 以及13 輪qCCA 多項式時間量子區(qū)分器， 給出19 輪CAST-256 的量子密鑰恢復攻擊. 2021 年Li 等人[15]改進了Feisetl 結(jié)構(gòu)密碼的量子密碼分析方法， 考慮了算法的內(nèi)部輪函數(shù)， 并將該方法應用于Camellia 算法， 提高了量子區(qū)分器輪數(shù).

TWINE 算法是2012 年SAC 會議上提出的具有廣義Feistel 結(jié)構(gòu)的輕量級分組密碼， 旨在保護資源受限的終端設備的數(shù)據(jù)安全[16]， 分組長度為64 bit， 主密鑰長度為80 bit 或128 bit， 分別表示為TWINE-80 版本和TWINE-128 版本. 現(xiàn)有的TWINE 的傳統(tǒng)密碼分析包括不可能差分故障分析、飽和分析、Biclique 分析、零相關線性分析、中間相遇分析等[17-19]. TWINE 作為廣義Feistel 結(jié)構(gòu)的典型密碼之一， 目前國內(nèi)外都沒有針對該密碼的量子密碼分析的相關研究， 本文在改進的Type-II 型GFS 量子區(qū)分器的基礎上， 將相關區(qū)分攻擊應用到TWINE-128 上， 設計并實現(xiàn)7 輪區(qū)分器， 構(gòu)造出相關的14 輪密鑰恢復攻擊路徑， 從而降低了攻擊代價， 有效地提高了攻擊效率. 該方法的提出對于分析輕量級密碼算法的安全性具有參考價值.

2 預備知識

2.1 符號說明

2.2 Type-II 型GFS

Type-II 型GFS 中明文輸入被分為2d個分支， 用x0j(1≤j ≤2d) 表示， 每個分支為n比特，所以分組長度為2d×n，F(xiàn)ij(0≤j ≤d- 1) 表示第i輪輪函數(shù). 其中每兩個塊應用Feistel 變換(x，y)→(x，F(xiàn)(x)⊕y)， 然后對子塊執(zhí)行循環(huán)位移， 具體如圖1 所示. 然而，k值較大的Type-II 型GFS具有明顯的缺點， 即它的低擴散性， 需要大約k輪才能將輸入差分擴散到所有的輸出子塊上， 如果輸入差分擴散不完全， 會出現(xiàn)一些攻擊， 如不可能差分攻擊和飽和攻擊. 近年來Type-II 型GFS 密碼多采用相對較小的k值來平衡規(guī)模和效率.

圖1 Type-II 型GFS 的一輪加密Figure 1 Encrypt round of Type-II GFS

2.3 改進的Type-II 型GFS

2010 年， Suzaki 和Minematsu[13]找到比循環(huán)位移有更好擴散性的塊移位方法， 以此提出一種改進的Type-II 型GFS (如圖2). 他們用不同的置換替換循環(huán)移位， 并證明了這種Type-II 型GFS 具有更快的擴散速度， 使用較少的輪數(shù)就可以抵抗不可能差分分析、積分分析等攻擊.

圖2 改進的Type-II 型GFS 的一輪加密Figure 2 Encrypt round of improved Type-II GFS

2.4 TWINE 算法

TWINE 是一種支持80 位和128 位密鑰的64 位輕量級密碼， 根據(jù)密鑰長度的不同， 算法分別記為TWINE-80 以及TWINE-128. TWINE 算法采用16 分支的廣義Feistel 結(jié)構(gòu)， 兩種密鑰長度下， 算法迭代輪數(shù)均為36 輪. 輪函數(shù)包括3 種操作， 即輪密鑰加、4 bit 的S 盒變換以及P 置換， 具體過程如圖3 所示， 我們使用以下符號: 第i輪的輪函數(shù)被標記為Fi1，F(xiàn)i2，···，F(xiàn)i16， 其中Fi1是最左邊的一個， 第i輪的輪密鑰被標記為RKij(j= 0，1，···，7). 由于具體S 盒置換信息與密鑰恢復攻擊過程無關， 所以本文不再詳述S 盒變換.

圖3 TWINE 算法的一輪加密圖Figure 3 Encrypt round of TWINE

3 相關工作

3.1 Simon 算法

給定布爾函數(shù)f:{0，1}→{0，1}n， 滿足f(x)=f(y)??x ⊕y ∈{0，s}， 即存在周期s， 經(jīng)典計算下， 解決上述問題的最優(yōu)時間復雜度為O(2n/2). Simon 提出一種量子算法， 該算法可提供指數(shù)級加速， 并只需要O(n) 量子查詢即可找到周期s， 即Simon 算法. 該算法具體步驟如下:

(1) 初始化兩個n比特量子寄存器的狀態(tài)為|0〉n|0〉n;

如果y·s=1， 則|y〉的振幅為0， 因此測量到的y的值都應該滿足y·s=0;

(6) 重復前五步(n-1) 次， 可得(n-1) 個線性方程， 解方程即可得周期s.

3.2 Grover 算法

給定布爾函數(shù)f:{0，1}→{0，1}n， 存在x滿足f(x)=1， 目標是找到符合這個條件的x， Grover 算法可以提供二次加速， 在使用O(n) 個量子比特和O(2n/2) 次查詢的情況下解決此類數(shù)據(jù)庫搜索問題， 該算法具體步驟如下:

3.3 Simon 和Grover 結(jié)合算法

Leander 和May[6]針對FX 結(jié)構(gòu)， 結(jié)合Simon 算法和Grover 算法， 提出了一種密鑰恢復攻擊方法.FX 結(jié)構(gòu)如圖4 所示: Enc(x)=Ek0(x ⊕k1)⊕k2.

圖4 FX 結(jié)構(gòu)Figure 4 FX constructions

構(gòu)造函數(shù)f(k，x) = Enc(x)⊕Ek(x) =Ek0(x ⊕k1)⊕k2⊕Ek(x)， 在猜測正確的密鑰k=k0情況下， 對所有x均存在f(k，x) =f(k，x ⊕k1)， 即函數(shù)大概率是周期性的; 但對于k/=k0， 函數(shù)不是周期性的. 在此基礎上， Dong 等人[8]應用Leander 和May 的方法攻擊了廣義Feistel 結(jié)構(gòu)并給出了5 輪的量子密鑰恢復攻擊方案， 這種方法相比經(jīng)典攻擊和用Grover 算法窮搜， 時間復雜度都有所降低.

3.4 Feistel 結(jié)構(gòu)的3 輪量子區(qū)分器

易證f(b，x)=f(b ⊕1，x ⊕F1(α0)⊕F1(α1))， 即周期s=(1，F(xiàn)1(α0)⊕F1(α1)). 通過Simon 算法可在多項時間內(nèi)獲得周期s.

3.5 Feistel 結(jié)構(gòu)的5 輪量子密鑰恢復攻擊

圖5 3 輪量子區(qū)分器Figure 5 3-round quantum distinguisher

圖6 5 輪量子密鑰恢復攻擊Figure 6 5-round quantum key-recovery attack

3.6 改進的Type-II 型GFS 的7 輪量子區(qū)分器

圖7 改進的Type-II 型GFS 結(jié)構(gòu)的7 輪量子區(qū)分器Figure 7 7-round quantum distinguisher of improved Type-II GFS

4 TWINE-128 的量子密鑰恢復攻擊

4.1 TWINE-128 的7 輪量子區(qū)分器

圖8 TWINE-128 的7 輪量子區(qū)分器Figure8 7-round quantum distinguisher of TWINE-128

構(gòu)造周期函數(shù)f如下:

4.2 TWINE-128 的14 輪量子密鑰恢復攻擊

基于上述提出的7 輪量子區(qū)分器對TWINE-128 做量子密鑰恢復攻擊，采用Simon 和Grover 的結(jié)合算法， 在7 輪量子區(qū)分器下附加了7 輪來發(fā)動攻擊. 如圖9 所示， 這里有108 比特的密鑰需要用到Grover算法進行猜測， 他們被用紅色的橢圓線標注了出來， 所以14 輪的密鑰恢復攻擊需要2(27×4)/2= 254次量子查詢. 如果用r表示輪數(shù)， 當我們的攻擊輪數(shù)r ＞14 輪時， 我們需要猜測108+32(r-14) 比特密鑰，量子查詢次數(shù)為254+16(r-14). 根據(jù)文獻[15]， 密鑰恢復攻擊所需要的量子比特數(shù)可以用以下公式來計算:

圖9 TWINE-128 的14 輪量子密鑰恢復攻擊Figure 9 14-round quantum key-recovery attack of TWINE-128

其中nk為密鑰長度，～n為周期的長度，nin為周期函數(shù)輸入長度，nout為周期函數(shù)輸出長度， 本文中猜測密鑰的長度為108， 周期長度～n= 1+4 = 5， 周期函數(shù)輸入長度nin= 1+4 = 5， 周期函數(shù)輸出長度nout=4， 所以計算可得sum=108+5×15+4×15=243.

5 總結(jié)與展望

本文首次在量子計算模型的基礎上， 對TWINE-128 進行了密碼分析， 通過構(gòu)造周期函數(shù)找到其7 輪量子區(qū)分器，然后使用Simon 算法和Grover 算法的結(jié)合算法對其進行14 輪量子密鑰恢復攻擊，該過程所需的量子比特數(shù)為243， 時間復雜度為254， 當輪數(shù)增加時， 時間復雜度將以每輪216進行遞增， 當r ＞14時， 密鑰恢復的時間復雜度為254+16(r-14).

下一步工作計劃: 我們將在現(xiàn)有研究成果的基礎上， 繼續(xù)探討可以抵抗量子攻擊的分組密碼算法的設計方案， 并進一步研究量子密鑰恢復攻擊技術以減少時間復雜度.