分組密碼結(jié)構(gòu)抗Simon量子算法攻擊研究*

羅宜元, 閆海倫, 王 磊, 胡紅鋼, 來學(xué)嘉,5

1.惠州學(xué)院信息科學(xué)技術(shù)學(xué)院, 惠州516007

2.上海電機學(xué)院電子信息學(xué)院, 上海201306

3.上海交通大學(xué)計算機科學(xué)與工程系, 上海200240

4.中國科學(xué)技術(shù)大學(xué)電子工程與信息科學(xué)系, 合肥230027

5.衛(wèi)士通摩石實驗室, 北京100070

1 引言

1.1 量子算法

隨著物理學(xué)與計算技術(shù)的進展, 量子計算顛覆了傳統(tǒng)的計算理論并引起世界各國研究人員的廣泛關(guān)注.量子計算領(lǐng)域中一個突破性的算法就是 Shor 算法[1], 該算法能夠在多項式時間內(nèi)尋找有限群里一個元素的階, 并被用來分解大整數(shù)和計算離散對數(shù).由于公鑰密碼算法大多是基于大整數(shù)分解與計算離散對數(shù)這兩類困難問題, Shor 量子算法對現(xiàn)有公鑰密碼算法是一個嚴重的威脅.除了 Shor 算法以外,Simon 算法和Grover 算法均對現(xiàn)有對稱密碼算法的安全性構(gòu)成了挑戰(zhàn), 這使得對稱密碼學(xué)界也掀起了抗量子攻擊的研究熱潮.Simon 算法能夠以O(shè)(n) 次查詢獲取一個特殊函數(shù)f的周期, 并且啟發(fā)了Shor 算法的發(fā)現(xiàn)[2].Grover 算法則能夠?qū)⑷我庖粋€K比特密鑰密碼算法的窮舉復(fù)雜度降低為O(2K/2), 并且是針對任意密碼算法的通用性攻擊[3].由于量子算法強大的密碼攻擊能力, 國內(nèi)學(xué)術(shù)界近些年也積極開展對后量子密碼的研究, 并取得了一系列的結(jié)果[4–7].

1.2 分組密碼結(jié)構(gòu)

現(xiàn)代分組密碼算法的設(shè)計思路基本上還是沿用香農(nóng)于 1949 年發(fā)表的經(jīng)典論文《保密系統(tǒng)的通信原理》中提出的混淆和擴散理論.從設(shè)計結(jié)構(gòu)上來看, 分組密碼結(jié)構(gòu)已經(jīng)從起初經(jīng)典的 Feistel 結(jié)構(gòu)擴展出許多變體.當前分組密碼的結(jié)構(gòu)基本分為三大類, 一類是Feistel 結(jié)構(gòu)及其變體, 此類結(jié)構(gòu)最為常見; 第二類是代換置換網(wǎng)絡(luò)結(jié)構(gòu)SPN; 還有一類是 Lai-Massey 結(jié)構(gòu), 如FOX 算法[8].相比 SPN 結(jié)構(gòu), Feistel 結(jié)構(gòu)和Lai-Massey 結(jié)構(gòu)的優(yōu)勢有兩方面: 一是不要求內(nèi)部輪函數(shù)為置換, 從而內(nèi)部S 盒等非線性模塊可以不必為置換.設(shè)計者選擇 S 盒的范圍更加廣泛, 密碼分析的難度大大增加, 因為不少密碼分析方法, 如積分攻擊、不可能差分分析、零相關(guān)線性分析等都是利用了 S 盒的置換性質(zhì).第二個優(yōu)勢是可以通過一定的密鑰編排, 使Feistel 結(jié)構(gòu)和Lai-Massey 結(jié)構(gòu)的加密過程和解密過程相同, 往往可以節(jié)省算法實現(xiàn)的資源, 而SPN 結(jié)構(gòu)則不具備此類優(yōu)點.

1.3 現(xiàn)有分組密碼結(jié)構(gòu)的量子攻擊

從已有的研究結(jié)果來看, 分組密碼結(jié)構(gòu)的構(gòu)造與其抗量子攻擊能力有很大的關(guān)系.在量子計算機中實現(xiàn)的分組密碼結(jié)構(gòu)的抗量子攻擊能力與其具體構(gòu)造相關(guān).在量子計算機上運行密碼算法時, 攻擊者可以在選擇明文的情形下, 對密碼算法的輸入進行疊加狀態(tài)查詢, 這類攻擊被稱為量子選擇明文攻擊 (CPA).日本學(xué)者Kuwakado 和Morii 在2010 年首次給出了在量子計算機上實現(xiàn)的3 輪Feistel 結(jié)構(gòu)的量子CPA 查詢攻擊, 該攻擊基于 Simon 算法在多項式時間內(nèi)將 3 輪 Feistel 結(jié)構(gòu)與一個隨機置換區(qū)分出來[9].而在經(jīng)典計算模型下, 3 輪 Feistel 結(jié)構(gòu)被證明是在多項式時間內(nèi)無法與隨機置換區(qū)分的[10].在 2012 年,Kuwakado 和 Morii 又對 Even-Mansour 類型的分組密碼結(jié)構(gòu)進行了類似的分析, 分析的方法仍然是基于 Simon 算法, 結(jié)果表明在量子計算機上實現(xiàn)的 Even-Mansour 分組密碼結(jié)構(gòu)是不安全的, 量子攻擊者可以在多項式時間內(nèi)尋找到密鑰[11].

在 2016 年美密會上, Kaplan 等人對 Simon 算法進行了擴充和完善, 并對一系列密碼結(jié)構(gòu)工作模式,包括常見的認證加密結(jié)構(gòu)CBC-MAC、GCM、OCB 等進行了量子攻擊[12].他們的結(jié)果表明在量子計算機下實現(xiàn)的這些結(jié)構(gòu)將不再安全.在同一年的FSE 上,他們也提出了量子差分和線性分析[13].在2017 年亞密會上, Leander 等人利用 Grover 算法和 Simon 算法的組合, 對分組密碼 DESX 所采用的 FX 結(jié)構(gòu)進行了量子攻擊, 該方法用 Simon 算法作為內(nèi)部判定函數(shù), 來判定搜索到的一個密鑰是否為正確的密鑰,并且使用Grover 算法作為外部密鑰搜索算法.該結(jié)果表明在量子計算機環(huán)境下, DESX 所使用的密鑰白化方法并不能增加安全性[14].

同樣在 RSA 2018 上, Hosoyamada 和 Sasaki 分析了攻擊者對密碼結(jié)構(gòu)使用經(jīng)典計算機在線查詢,使用量子計算機進行離線計算的情形下的復(fù)雜度, 并給出了相關(guān)的時空折中復(fù)雜度結(jié)果[15].在 SCN 2018 上, 他們對 Feistel 擴展結(jié)構(gòu)進行了量子中間相遇攻擊, 結(jié)果顯示量子計算機能夠顯著增加中間相遇攻擊的能力[16].

國內(nèi)方面在量子對稱密碼學(xué)領(lǐng)域研究的文獻較少,Dong 等人在最近的《中國科學(xué)》上對一些擴展Feistel 結(jié)構(gòu)作出了量子 Simon 算法攻擊[17], 在最近的 Eprint 上, Dong 等人結(jié)合 Simon 算法對滑動攻擊(Slide Attack) 進行了改進, 并對Feistel 的一些變體和GOST 進行了密鑰恢復(fù)攻擊[18].

從最近幾年學(xué)術(shù)界發(fā)表的文獻趨勢來看, 分組密碼結(jié)構(gòu)的量子攻擊方法研究已經(jīng)成為各國密碼學(xué)研究的熱點領(lǐng)域.研究人員開始考慮到在量子計算模型下, 經(jīng)典的分組密碼結(jié)構(gòu)是否能夠達到一定的偽隨機性,或者是否存在更為簡單的通用性量子攻擊算法.在當前已知的量子算法中, 對分組密碼結(jié)構(gòu)攻擊最有效的是Simon 算法, 所以本文主要研究常見的分組密碼結(jié)構(gòu)抵抗Simon 量子算法攻擊的安全性.

1.4 本文貢獻

本文的工作分為以下幾部分.

(1) 梳理針對現(xiàn)有分組密碼結(jié)構(gòu)的 Simon 量子算法攻擊方法, 研究在 Simon 承諾無法完全滿足時,Simon 算法的成功概率.證明了 Simon 算法中周期函數(shù)的一個特別性質(zhì), 即若一個隨機函數(shù)f具有周期, 則該函數(shù)只存在唯一周期的概率幾乎為1.

(2) 進一步具體地指出用 Simon 算法區(qū)分三輪 Feistel 結(jié)構(gòu)時, 若 Feistel 結(jié)構(gòu)中的第二輪的輪函數(shù)F為置換, 而其余兩輪的輪函數(shù)為任意的函數(shù), 就能夠構(gòu)造出完全滿足 Simon 承諾的周期函數(shù).而 Kuwakado 和 Morii 的文章則要求每一輪輪函數(shù)都為置換, 該結(jié)論也可以應(yīng)用到對其他的類Feistel 分組密碼結(jié)構(gòu), 包括對CAST256、RC6 結(jié)構(gòu)的攻擊上.

(3) 指出 Dong 等人所引用的 Simon 算法需要得到修改, 因為 Dong 等人的結(jié)果是基于 Kaplan 等人的算法, 但 Kaplan 等人的理論分析結(jié)果是在直接測量前n個量子比特的情形下獲得的.而Dong 等的 Simon 算法是要先測量后n個量子比特, 再測量前n個量子比特, 根據(jù)量子糾纏理論, 這樣將會使Kaplan 等人的分析結(jié)果更為復(fù)雜, 需要進一步的分析.

(4) 指出Dong 等人對類RC6 分組密碼結(jié)構(gòu)的Simon 攻擊是不正確的, 并給出了正確的攻擊過程.

(5) 在 CPA 模式下, 使用 Simon 量子算法將三輪 MISTY-L 與 MISTY-R 結(jié)構(gòu)與隨機置換區(qū)分.

(6) 論證了在量子 CPA 攻擊下, 三輪 Lai-Massey 結(jié)構(gòu)能夠抵抗已知基于 Simon 量子算法的攻擊.從抗Simon 量子算法攻擊的角度講, Lai-Massey 結(jié)構(gòu)優(yōu)于Feistel 結(jié)構(gòu).

2 基礎(chǔ)知識

2.1 Simon量子算法

Simon 算法于 1994 年提出, 其對經(jīng)典算法作出指數(shù)級的加速并啟發(fā)了 Shor 算法的發(fā)現(xiàn)[2].Simon算法解決的問題對象被稱為Simon 問題, 表述如下.

Simon 問題:給定一個布爾函數(shù)f:{0,1}n→{0,1}n, 滿足條件x⊕y∈{0,s}?f(x)=f(y), 其中⊕表示二進制異或操作, 該條件稱為Simon 承諾, 現(xiàn)在需求出n比特值s.

在經(jīng)典計算模型下計算s, 根據(jù)生日界, 需要對f查詢O(2n/2) 次.而 Simon 量子算法僅需要對f作出O(n) 次量子查詢.Simon 算法的量子電路如圖1 所示.

圖1 Simon 量子算法Figure 1 Simon’s quantum algorithm

Simon 算法工作步驟如下:

(1) 將 2n個量子比特的初始狀態(tài)設(shè)置為

(2) 對前n個量子比特進行 Hadamard 變換后, 2n個量子比特的狀態(tài)轉(zhuǎn)換為疊加態(tài):

(3) 查詢Uf后, 2n個量子比特的狀態(tài)為:

(4) 對后n個量子比特進行測量, 得到f(x) 的一個n比特隨機輸出y, 根據(jù)f的性質(zhì), 存在一對原像 {x,x⊕s} 使得f(x)=f(x⊕s)=y, 所以前n個量子比特塌縮為

(5) 對前n個量子比特再一次應(yīng)用Hadamard 變換后, 其狀態(tài)為:

若y與s的內(nèi)積y·s=1, 則根據(jù)量子相消干涉,的幅度為 0, 所以, 若測量得到一個n比特則必有y·s=0, 可以將y看作一個n比特的向量, 并將y的值存下來.

(6) 重復(fù)運行步驟 (1–5)n? 1 次, 我們得到n? 1 個與s正交的向量y1,··· ,yn?1, 令事件Ei,1 ≤i≤n?1 為前i個向量彼此獨立的事件, 則有(排除掉向量 0), Pr[Ei|Ei?1]=

上面公式中最后一個極限可由數(shù)值軟件計算得出, 即可以至少0.288 的概率得到n?1 個獨立向量 {y1,··· ,yn?1}, 隨后也就得到一個關(guān)于變量s的 (n?1) 個獨立的線性方程, 可以在O(n3)的時間內(nèi)用高斯消元法快速求解得到s.運行全算法m次, 尋找到正確的s的值的概率至少為1 ?(1 ?0.288)m, 當m=20 的時候, 算法成功的概率大于 0.99.

2.2 Simon承諾條件的弱化情形

在文獻 [19]中, Santoli 和 Schaffner 觀察到若f函數(shù)不完全滿足 Simon 承諾, 只滿足條件x⊕y=s?f(x)=f(y),s=0 時, 也可以使用Simon 算法來做區(qū)分攻擊, 但是他們宣稱弱化條件后的 Simon 算法的成功概率會下降, 這是因為在某些情況下無法得到一系列獨立的線性方程.

在Simon 承諾條件弱化的情形下, Kaplan 等人也分析了Simon 算法成功的概率[12].在文獻[17]中,Dong 等人使用 Simon 算法對 Feistel 的擴展結(jié)構(gòu), 包括 CAST256、RC6 等結(jié)構(gòu)給出了區(qū)分攻擊, 并結(jié)合 Leander 等人的思路給出了對應(yīng)分組密碼結(jié)構(gòu)的密鑰恢復(fù)攻擊.在這里我們指出 Dong 等人的 Si-mon 算法需要得到修改, 因為其結(jié)果是基于 Kaplan 等人的算法, 但 Kaplan 等人的理論分析結(jié)果是在直接測量前n個量子比特的情形下獲得的.若先測量后n個量子比特, 再測量前n個量子比特, 根據(jù)量子糾纏理論, 可能會影響Kaplan 等人的分析結(jié)果, 需要對算法成功概率作出進一步分析.

當 Simon 承諾不滿足時, 可以從第 (4) 步開始修改 Simon 算法:

(4) 對前n個量子比特再一次應(yīng)用Hadamard 變換.2n個量子比特狀態(tài)為:

此時, 測量前n個量子比特得到 |y?的概率為:

由于f存在周期s, 若y·s= 1, 則py的值為 0.所以, 若測量得到一個n比特 |y?, 則必有y·s=0, 且py與具體的函數(shù)f滿足 Simon 承諾的情形有關(guān).

Kaplan 等人定義了一個指標來衡量一個函數(shù)與Simon 承諾完全滿足時的距離[12].該指標定義如下:

定義 1對于一個存在周期s的函數(shù)f:{0,1}n→{0,1}n, 對任意的x都有f(x⊕s)=f(x), 令

在文獻 [20]中, Daemen 和 Rijmen 給出, 對于一個隨機的函數(shù),

Kaplan 等人的主要工作是證明了如下定理.

定理 1如果?(f,s) ≤p0< 1, 則 Simon 算法在經(jīng)過cn次查詢后, 得到正確s值的概率至少為

2.3 對Simon承諾中f函數(shù)的周期進一步研究

我們進一步研究發(fā)現(xiàn), 若一個函數(shù)存在周期, 則該函數(shù)只存在唯一周期的概率接近1.

引理 1若存在一個n比特常數(shù)s0, 使得函數(shù)f:{0,1}n→{0,1}n滿足條件x⊕y=s?f(x)=f(y), 則稱s稱為f的周期.在所有 {0,1}n→ {0,1}n的函數(shù)中, 存在周期s的函數(shù)個數(shù)為NN/2,N=2n.在所有存在周期s的函數(shù)中隨機選取一個f,f存在唯一周期的概率為:

證明:令函數(shù)f的N個n比特輸入集合為A, 由于A可以表示為:

根據(jù)f的性質(zhì), 有所以只需計算的可能取值的個數(shù), 每一個f(xi) 值是從N個 {0,1}n值里選取, 所以存在周期s的函數(shù)集合M的大小為: |M|=NN/2.

在存在周期s函數(shù)f中, 如果存在使得f(xi) 的值與都不同,則f只存在唯一周期s.也就是說, 在函數(shù)f的值域中至少存在一個y,y的值與值域中其他所有的值都不同.這是因為若其存在另外一個周期有f(x)=f(x⊕t), 則有

由于f(xi) 的值與都不同, 且只有f(xi⊕s) 與f(xi) 相等, 若y∈/{xi,xi⊕s},必有與我們定義的條件矛盾.所以此時的f函數(shù)必然只存在唯一周期s.

令具有唯一周期s的函數(shù)f的集合為S, 令為都不同的函數(shù)的集合, 則根據(jù)容斥原理,

可以通過 Maple 數(shù)值計算軟件得出, 當n≥ 4, 即N≥24時,P(n) > 0.99.P(n) 的值隨n的大小如圖2 所示.即當周期函數(shù)f的輸入輸出長度大于4 時, 其存在唯一周期的概率幾乎為1.

3 常見分組密碼結(jié)構(gòu)的Simon量子算法攻擊

在文獻 [9]中, Kuwakado 和 Morii 首次將 Simon 量子算法應(yīng)用到攻擊 3 輪 Feistel 結(jié)構(gòu)上, 他們的結(jié)果表明, 若3 輪Feistel 結(jié)構(gòu)中的輪函數(shù)均為彼此獨立的置換, 則3 輪的Feistel 結(jié)構(gòu)與一個隨機置換在多項式時間內(nèi)可以區(qū)分[10].在經(jīng)典計算模型下, 已證明3 輪Feistel 結(jié)構(gòu)與一個隨機置換在多項式時間內(nèi)不可區(qū)分.隨后在文獻 [19]中, Santoli 等人給出了對Feistel 結(jié)構(gòu)在內(nèi)部函數(shù)為隨機函數(shù)時的攻擊方法,但并沒有給出詳細的理論分析.而Kaplan 等人的文章卻給出詳細的理論分析結(jié)果[12].

對一個分組密碼結(jié)構(gòu)Ek: {0,1}n→ {0,1}n使用 Simon 算法攻擊時, 當前已知的方法都是基于Ek構(gòu)造得到一個具有周期s的函數(shù)f, 攻擊者可以對f進行量子疊加態(tài)查詢, 并且獲得了周期s就可以攻破該加密結(jié)構(gòu).當前基于Ek構(gòu)造周期函數(shù)f的方法只有如下2 種:

3.1 對3輪Feistel結(jié)構(gòu)的區(qū)分攻擊

在文獻 [9]中, Kuwakado 和 Morii 基于輪函數(shù)為置換的 3 輪 Feistel 結(jié)構(gòu), 構(gòu)造了相應(yīng)的周期函數(shù),并給出對應(yīng)攻擊.3 輪 Feistel 結(jié)構(gòu)E如圖3 所示, 第i輪的輸入為輸出為令α0和α1為兩個任意的常量, 構(gòu)造得到的周期函數(shù)f為:

可以驗證f(b,x)=f(b⊕1,x⊕F1(α0)⊕F(α1)), 即得到了一個周期為s=(1,F1(α0)⊕F1(α1)) 的函數(shù).

圖2 P(n) 的值Figure 2 Value of P(n)

圖3 三輪 Feistel 結(jié)構(gòu)Figure 3 Three-round Feistel structure

定理 2當F2為置換時, 若X1= (b1,x1),X2= (b2,x2) 且若f(X1) =f(X2), 則有X2=X1⊕s.

證明:因為若b1=b2=b∈ {0,1}, 由于f(X1) =f(X2), 所以F2(x1⊕F1(αb)) =F2(x2⊕F1(αb)).因為F2是一個置換, 必有x1=x2, 使得X1=X2, 與已知條件矛盾.所以b1=b2, 即b1=b2⊕1.

當b1=b2⊕1 時, 由于f(X1)=f(X2), 則有F2(x1⊕F1(αb1))=F2(x2⊕F1(αb2)).因為F2是一個置換, 必有x2=x1⊕F1(α0)⊕F1(α1).即X2=X1⊕s.

所以, 當 3 輪 Feistel 結(jié)構(gòu)中的第二輪函數(shù)F2為一個置換時, 基于此方法構(gòu)造得到的周期函數(shù)f完全滿足Simon 承諾.當F2為一個隨機函數(shù)時, Kaplan 等人給出了以近似1 的概率有此時根據(jù)定理1, 當c=3 時, 即運行 Simon 算法3n次時, 能夠以近似 1 的概率找到函數(shù)f的正確周期s.

3.2 對類RC6結(jié)構(gòu)Simon量子算法攻擊的修正

在文獻 [17]中, Dong 等人對 4 分支的 5 輪類 RC6 分組密碼結(jié)構(gòu)給出了 Simon 量子算法攻擊, 同時對6 分支的7 輪類RC6 分組密碼結(jié)構(gòu)給出了Simon 量子算法攻擊.

5 輪類 RC6 結(jié)構(gòu)圖如圖4 所示.

圖4 五輪 RC6-like 結(jié)構(gòu)Figure 4 Five-round RC6-like structure

Dong 等人基于此結(jié)構(gòu)構(gòu)造出的周期函數(shù)f為

可以計算得出,f具有周期但該函數(shù)f不能夠被用來構(gòu)造成量子黑盒, 因為要獲得該函數(shù)f的輸出結(jié)果, 攻擊者需要計算其中攻擊者能夠獲取αb和但攻擊者無法獲取的值.這是因為攻擊者無法訪問f函數(shù)內(nèi)部輪函數(shù)的輸出中間變量.若攻擊者能夠訪問f函數(shù)內(nèi)部輪函數(shù)的輸出, 則整個攻擊變?yōu)槠椒补?同樣, Dong 等人對6 分支的7 輪類RC6 分組密碼結(jié)構(gòu)的Simon 量子算法攻擊也是不正確的.

對4 分支的類RC6 分組密碼結(jié)構(gòu), 基于5 輪類RC6 結(jié)構(gòu)構(gòu)造得到正確的f函數(shù)如下:

同理, 基于7 輪6 分支類RC6 分組密碼結(jié)構(gòu)構(gòu)造得到的正確f函數(shù)如下:

在文獻 [21,22]中, Moriai, Vaudenay 以及 Luo 等人的結(jié)果表明, 在經(jīng)典計算模型下, 4 分支類 RC6 分組密碼結(jié)構(gòu)至少需要 10 輪才能達到偽隨機性, 因此, 相對于經(jīng)典攻擊方法, 對類 RC6 結(jié)構(gòu)進行Simon 量子算法攻擊效果并不顯著.

3.3 對MISTY-L和MISTY-R結(jié)構(gòu)的Simon算法攻擊

除了 Feistel 結(jié)構(gòu)以外, 日本學(xué)者 MATSUI 參考 Feistel 結(jié)構(gòu)提出了 MISTY 結(jié)構(gòu), 該結(jié)構(gòu)被用在分組密碼算法 MISTY1 上[23].在文獻 [24]中, Gilbert 和 Minier 將 MISTY 結(jié)構(gòu)劃分為 MISTYL 和 MISTY-R 結(jié)構(gòu), 并且證明了 4 輪 MISTY-L 和 3 輪 MISTY-R 結(jié)構(gòu)能夠達到偽隨機性.在這里我們基于3 輪MISTY-L 和MISTY-R 結(jié)構(gòu)構(gòu)造其對應(yīng)的周期函數(shù), 從而構(gòu)造相應(yīng)的Simon 量子算法攻擊,3 輪 MISTY-L 和 MISTY-R 結(jié)構(gòu)如圖5 所示.

圖5 三輪 MISTY-L 結(jié)構(gòu) (左) 與 MISTY-R 結(jié)構(gòu) (右)Figure 5 Three-round MISTY-L structure (Left) and MISTY-R structure (Right)

基于3 輪類MISTY-L 結(jié)構(gòu)構(gòu)造得到的f函數(shù)如下:

可以計算得出, 基于該構(gòu)造得到的f函數(shù)具有周期

基于3 輪類MISTY-R 結(jié)構(gòu)構(gòu)造得到的f函數(shù)如下:

可以計算得出, 基于該構(gòu)造得到的f函數(shù)具有周期

由于在 MISTY-L 和 MISTY-R 結(jié)構(gòu)中,Fi為置換, 構(gòu)造得到的f函數(shù)完全滿足 Simon 承諾, 使得Simon 算法對這兩個分組密碼結(jié)構(gòu)完全適用.

4 Lai-Massey結(jié)構(gòu)抗Simon量子算法攻擊分析

Lai-Massey 結(jié)構(gòu)是由瑞士密碼學(xué)家Vaudenay 對IDEA 算法的結(jié)構(gòu)進行修改得到[25].原始的IDEA算法上層結(jié)構(gòu)并不具有理論意義上的偽隨機性, Vaudenay 對 IDEA 算法結(jié)構(gòu)進行了微小改動, 添加了一個正形置換σ(x,y) = (y,x⊕y), 從而使該結(jié)構(gòu)具有理論意義上的偽隨機性, 并被稱為 Lai-Massey 結(jié)構(gòu).Lai-Massey 結(jié)構(gòu)被證明經(jīng)過三輪迭代后具有偽隨機性, 四輪迭代后具有強偽隨機性, 其結(jié)構(gòu)如圖6 所示.

圖6 三輪 Lai-Massey 結(jié)構(gòu), σ(x,y)=(y,x ⊕y)Figure 6 Three-round Lai-Massey structure

相比 Feistel 結(jié)構(gòu), 對 Lai-Massey 結(jié)構(gòu)的通用性攻擊研究文獻較少.在文獻 [26]中, Luo 等人最先給出了對 Lai-Massey 結(jié)構(gòu)的 2 輪偽隨機性區(qū)分器和 3 輪強偽隨機性區(qū)分器.在 2011 年的 DCC 上,韓國 Yun 等人認為 Lai-Massey 結(jié)構(gòu)和 Feistel 結(jié)構(gòu)具有相同的安全性, 屬于同一家族, 并將該家族命名為 quasi-Feistel 結(jié)構(gòu).他們宣稱在 Luby-Rackoff 模型下, 作為一個分組密碼設(shè)計, Lai-Massey 結(jié)構(gòu)與 Feistel 結(jié)構(gòu)相比不具備優(yōu)勢[27].這樣的宣稱就使學(xué)術(shù)界認為 Lai-Massey 結(jié)構(gòu)只是 Feistel 結(jié)構(gòu)的一種變換結(jié)構(gòu), 分組密碼結(jié)構(gòu)設(shè)計者使用Lai-Massey 結(jié)構(gòu)來設(shè)計算法, 相比Feistel 結(jié)構(gòu)沒有優(yōu)勢.

在文獻[28]中, Luo 等人指出, 在5 輪迭代以內(nèi), Lai-Massey 結(jié)構(gòu)與Feistel 結(jié)構(gòu)相比, 對抗已知通用性攻擊能力更強.他們采用了Patarin 對Feistel 結(jié)構(gòu)分析中所使用的4-Point 攻擊技術(shù)對Lai-Massey 結(jié)構(gòu)進行攻擊.結(jié)果表明 Patarin 對 Feistel 結(jié)構(gòu)的部分攻擊在 Lai-Massey 結(jié)構(gòu)上并不成立.攻擊者攻擊3 輪、4 輪、5 輪 Lai-Massey 結(jié)構(gòu)的查詢復(fù)雜度和計算復(fù)雜度普遍要高于 Feistel 結(jié)構(gòu).這一結(jié)果表明了Lai-Massey 結(jié)構(gòu)抗現(xiàn)有通用攻擊的能力更強.

從已有對分組密碼結(jié)構(gòu)進行 Simon 攻擊的步驟可以得出, 如果基于一個分組密碼結(jié)構(gòu)可以構(gòu)造一個周期函數(shù)即x與x⊕s對于函數(shù)f發(fā)生了碰撞, 因為f的內(nèi)部組件是分組密碼結(jié)構(gòu), 則必定在分組密碼結(jié)構(gòu)內(nèi)部狀態(tài)處發(fā)生了碰撞, 并且該碰撞值被用來構(gòu)造周期函數(shù)f的輸出值.

由于Simon 量子攻擊過程中需要獲取周期函數(shù)f的輸出, 若不能獲取f的輸出值, 則無法構(gòu)造量子黑盒提供攻擊者進行量子查詢.在本文第3 節(jié)對3 輪Feistel 結(jié)構(gòu)的Simon 算法攻擊中, 攻擊者可以由明密文對生成Feistel 結(jié)構(gòu)的第二輪輪函數(shù)F2的碰撞, 并且該碰撞值可以由明文和密文計算得出, 繼而構(gòu)造周期函數(shù).若對一個分組密碼結(jié)構(gòu)進行選擇明文攻擊時, 盡管在某未知狀態(tài)處能夠產(chǎn)生碰撞, 但若無法由選擇明密文計算得出該碰撞值, 則該碰撞特性不能夠用在構(gòu)造周期函數(shù)中, 使得其能夠抵抗Simon 量子攻擊.

下面, 我們將論證三輪 Lai-Massey 結(jié)構(gòu)在選擇明文攻擊下, 其內(nèi)部的任一未知狀態(tài)都不能夠由明密文對計算得出.由圖6 可以得出, 一輪Lai-Massey 結(jié)構(gòu)實際上只產(chǎn)生一個未知狀態(tài), 即輪函數(shù)Fi的輸出,三輪 Lai-Massey 結(jié)構(gòu)實際上共有三個未知狀態(tài), 即輪函數(shù)F1,F2,F3的輸出值u,v,w, 而其他的狀態(tài)都可以由明密文和這三個未知狀態(tài)計算得到.

在選擇明攻擊中, 攻擊者可以生成一系列明密文對:

由Lai-Massey 結(jié)構(gòu)的計算過程可以得出對于明密文對(ai∥bi,gi∥hi), 其對應(yīng)的三個未知狀態(tài)ui,vi,wi分別為:

由于攻擊者無法獲取三輪Lai-Massey 結(jié)構(gòu)內(nèi)部輪函數(shù)F1,F2,F3的任一輸出值, 所以三個基本的未知狀態(tài)ui,vi,wi中任意一個值都無法由選擇明密文對計算得出.這樣, 即使攻擊者能夠在某未知狀態(tài)處產(chǎn)生碰撞, 但由于該碰撞值無法由選擇明密文對計算得出, 無法使用該特性構(gòu)造碰撞函數(shù), 繼而無法構(gòu)造周期函數(shù), 所以三輪Lai-Massey 結(jié)構(gòu)能夠抵抗Simon 量子算法攻擊.

Lai-Massey 結(jié)構(gòu)與 Feistel 結(jié)構(gòu)在計算效率上相差無幾, 二者都可以通過修改密鑰調(diào)度來實現(xiàn)相同的加解密過程.在經(jīng)典計算模型下, 從已有的結(jié)果可以得出Lai-Massey 結(jié)構(gòu)比Feistel 結(jié)構(gòu)對抗已有通用攻擊更強, 本文結(jié)果又表明在量子CPA 模型下, 相比Feistel 結(jié)構(gòu), Lai-Massey 結(jié)構(gòu)抵抗Simon 量子算法攻擊的能力更強, 所以Lai-Massey 結(jié)構(gòu)在分組密碼算法的設(shè)計中是一個較好的候選結(jié)構(gòu).

5 結(jié)論

本文對 Simon 量子算法作出進一步分析, 證明了當Simon 承諾不完全滿足時, 一個具有周期的隨機函數(shù)存在唯一周期的概率接近 1.本文同時指出對 Feistel 結(jié)構(gòu)及其擴展結(jié)構(gòu)應(yīng)用 Simon 算法時, 只需要中間的輪函數(shù)為置換, 就可以構(gòu)造出完全滿足 Simon 承諾的周期函數(shù).本文也總結(jié)了 Simon 量子算法對常見分組密碼結(jié)構(gòu)的攻擊步驟, 修正了Dong 等人對 RC6 算法結(jié)構(gòu)攻擊中的錯誤, 對三輪 MISTYL 和MISTY-R 成功進行了區(qū)分攻擊.最后, 本文論證了在量子 CPA 模型下, 三輪 Lai-Massey 結(jié)構(gòu)能夠抵抗Simon 量子算法攻擊.當前結(jié)果表明了在抵抗已知攻擊時, 同樣輪數(shù)的Lai-Massey 結(jié)構(gòu)的安全性要強于 Feistel 結(jié)構(gòu).我們建議分組密碼算法設(shè)計者采用 Lai-Massey 結(jié)構(gòu), 以同樣的輪數(shù)達到更高的安全性.