輕量級密碼TWINE-128 的量子密碼分析*

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

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

2. 北京電子科技學(xué)院， 北京 100070

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

1 引言

近幾年， 量子計算模型下密碼算法的安全性成為密碼研究人員關(guān)注的焦點之一. 1988 年， 3 輪Feistel結(jié)構(gòu)被證明[1]是偽隨機置換， 但2010 年3 輪Feistel 結(jié)構(gòu)被發(fā)現(xiàn)存在一個固定的周期， 通過使用Simon算法在O(n) 時間復(fù)雜度內(nèi)恢復(fù)出周期， 這一結(jié)果比經(jīng)典方法O(nn/2) 的時間復(fù)雜度有了很大的提高[2].緊接著在2012 年， 基于Simon 算法Kuwakado 等人對Even-Mansour 結(jié)構(gòu)進(jìn)行了量子分析， 將恢復(fù)密鑰的攻擊復(fù)雜度由傳統(tǒng)分析需要的指數(shù)時間降低為量子分析需要的多項式時間[3]. 2016 年美密會上，Kaplan 等人[4]對Simon 算法進(jìn)行了擴充和完善， 并對一系列密碼結(jié)構(gòu)工作模式進(jìn)行了量子攻擊， 他們的結(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)建了密鑰恢復(fù)攻擊， 并結(jié)合Simon 算法改進(jìn)了經(jīng)典的滑動攻擊. 2018 年，Hosoyamada 等人[9]對Feistel 擴展結(jié)構(gòu)進(jìn)行了量子中間相遇攻擊， 結(jié)果顯示量子計算機能夠顯著增加中間相遇攻擊的能力. 2020 年， Dong 等人[10]結(jié)合Simon 算法對滑動攻擊進(jìn)行了改進(jìn)， 并對Feistel 的一些變體和GOST 進(jìn)行了密鑰恢復(fù)攻擊. 同年， Luo 等人[11]對三輪MISTY-L 和MISTY-R 進(jìn)行了區(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)， 并對每兩個子塊應(yīng)用一次Feistel變換， 然后執(zhí)行k個子塊的循環(huán)移位. 近年來， Type-II 型GFS 因其簡單性和高并行性而受到廣泛關(guān)注.然而， 其缺點是具有較大的k時擴散特性較差. 2010 年， Tomoyasu 和Kazuhiko[13]通過用不同的置換替換循環(huán)移位來減少輪數(shù)， 可以改善Type-II 型GFS 的擴散特性， 使其達(dá)到足夠的安全級別. 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 進(jìn)行研究， 給出了改進(jìn)的多項式時間量子區(qū)分器， 并將上述區(qū)分攻擊應(yīng)用到CAST-256 分組密碼中， 得到了12 輪qCPA多項式時間量子區(qū)分器， 以及13 輪qCCA 多項式時間量子區(qū)分器， 給出19 輪CAST-256 的量子密鑰恢復(fù)攻擊. 2021 年Li 等人[15]改進(jìn)了Feisetl 結(jié)構(gòu)密碼的量子密碼分析方法， 考慮了算法的內(nèi)部輪函數(shù)， 并將該方法應(yīng)用于Camellia 算法， 提高了量子區(qū)分器輪數(shù).

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

2 預(yù)備知識

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ù). 其中每兩個塊應(yīng)用Feistel 變換(x，y)→(x，F(xiàn)(x)⊕y)， 然后對子塊執(zhí)行循環(huán)位移， 具體如圖1 所示. 然而，k值較大的Type-II 型GFS具有明顯的缺點， 即它的低擴散性， 需要大約k輪才能將輸入差分?jǐn)U散到所有的輸出子塊上， 如果輸入差分?jǐn)U散不完全， 會出現(xiàn)一些攻擊， 如不可能差分攻擊和飽和攻擊. 近年來Type-II 型GFS 密碼多采用相對較小的k值來平衡規(guī)模和效率.

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

2.3 改進(jìn)的Type-II 型GFS

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

圖2 改進(jìn)的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ù)被標(biāo)記為Fi1，F(xiàn)i2，···，F(xiàn)i16， 其中Fi1是最左邊的一個， 第i輪的輪密鑰被標(biāo)記為RKij(j= 0，1，···，7). 由于具體S 盒置換信息與密鑰恢復(fù)攻擊過程無關(guān)， 所以本文不再詳述S 盒變換.

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

3 相關(guān)工作

3.1 Simon 算法

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

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

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

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

3.2 Grover 算法

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

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

Leander 和May[6]針對FX 結(jié)構(gòu)， 結(jié)合Simon 算法和Grover 算法， 提出了一種密鑰恢復(fù)攻擊方法.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ù)不是周期性的. 在此基礎(chǔ)上， Dong 等人[8]應(yīng)用Leander 和May 的方法攻擊了廣義Feistel 結(jié)構(gòu)并給出了5 輪的量子密鑰恢復(fù)攻擊方案， 這種方法相比經(jīng)典攻擊和用Grover 算法窮搜， 時間復(fù)雜度都有所降低.

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 輪量子密鑰恢復(fù)攻擊

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

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

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

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

4 TWINE-128 的量子密鑰恢復(fù)攻擊

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 輪量子密鑰恢復(fù)攻擊

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

圖9 TWINE-128 的14 輪量子密鑰恢復(fù)攻擊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é)與展望

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

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