羅宜元, 閆海倫, 王 磊, 胡紅鋼, 來學(xué)嘉,5
1.惠州學(xué)院信息科學(xué)技術(shù)學(xué)院, 惠州516007
2.上海電機(jī)學(xué)院電子信息學(xué)院, 上海201306
3.上海交通大學(xué)計(jì)算機(jī)科學(xué)與工程系, 上海200240
4.中國科學(xué)技術(shù)大學(xué)電子工程與信息科學(xué)系, 合肥230027
5.衛(wèi)士通摩石實(shí)驗(yàn)室, 北京100070
隨著物理學(xué)與計(jì)算技術(shù)的進(jìn)展, 量子計(jì)算顛覆了傳統(tǒng)的計(jì)算理論并引起世界各國研究人員的廣泛關(guān)注.量子計(jì)算領(lǐng)域中一個(gè)突破性的算法就是 Shor 算法[1], 該算法能夠在多項(xiàng)式時(shí)間內(nèi)尋找有限群里一個(gè)元素的階, 并被用來分解大整數(shù)和計(jì)算離散對(duì)數(shù).由于公鑰密碼算法大多是基于大整數(shù)分解與計(jì)算離散對(duì)數(shù)這兩類困難問題, Shor 量子算法對(duì)現(xiàn)有公鑰密碼算法是一個(gè)嚴(yán)重的威脅.除了 Shor 算法以外,Simon 算法和Grover 算法均對(duì)現(xiàn)有對(duì)稱密碼算法的安全性構(gòu)成了挑戰(zhàn), 這使得對(duì)稱密碼學(xué)界也掀起了抗量子攻擊的研究熱潮.Simon 算法能夠以O(shè)(n) 次查詢獲取一個(gè)特殊函數(shù)f的周期, 并且啟發(fā)了Shor 算法的發(fā)現(xiàn)[2].Grover 算法則能夠?qū)⑷我庖粋€(gè)K比特密鑰密碼算法的窮舉復(fù)雜度降低為O(2K/2), 并且是針對(duì)任意密碼算法的通用性攻擊[3].由于量子算法強(qiáng)大的密碼攻擊能力, 國內(nèi)學(xué)術(shù)界近些年也積極開展對(duì)后量子密碼的研究, 并取得了一系列的結(jié)果[4–7].
現(xiàn)代分組密碼算法的設(shè)計(jì)思路基本上還是沿用香農(nóng)于 1949 年發(fā)表的經(jīng)典論文《保密系統(tǒng)的通信原理》中提出的混淆和擴(kuò)散理論.從設(shè)計(jì)結(jié)構(gòu)上來看, 分組密碼結(jié)構(gòu)已經(jīng)從起初經(jīng)典的 Feistel 結(jié)構(gòu)擴(kuò)展出許多變體.當(dāng)前分組密碼的結(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è)計(jì)者選擇 S 盒的范圍更加廣泛, 密碼分析的難度大大增加, 因?yàn)椴簧倜艽a分析方法, 如積分攻擊、不可能差分分析、零相關(guān)線性分析等都是利用了 S 盒的置換性質(zhì).第二個(gè)優(yōu)勢是可以通過一定的密鑰編排, 使Feistel 結(jié)構(gòu)和Lai-Massey 結(jié)構(gòu)的加密過程和解密過程相同, 往往可以節(jié)省算法實(shí)現(xiàn)的資源, 而SPN 結(jié)構(gòu)則不具備此類優(yōu)點(diǎn).
從已有的研究結(jié)果來看, 分組密碼結(jié)構(gòu)的構(gòu)造與其抗量子攻擊能力有很大的關(guān)系.在量子計(jì)算機(jī)中實(shí)現(xiàn)的分組密碼結(jié)構(gòu)的抗量子攻擊能力與其具體構(gòu)造相關(guān).在量子計(jì)算機(jī)上運(yùn)行密碼算法時(shí), 攻擊者可以在選擇明文的情形下, 對(duì)密碼算法的輸入進(jìn)行疊加狀態(tài)查詢, 這類攻擊被稱為量子選擇明文攻擊 (CPA).日本學(xué)者Kuwakado 和Morii 在2010 年首次給出了在量子計(jì)算機(jī)上實(shí)現(xiàn)的3 輪Feistel 結(jié)構(gòu)的量子CPA 查詢攻擊, 該攻擊基于 Simon 算法在多項(xiàng)式時(shí)間內(nèi)將 3 輪 Feistel 結(jié)構(gòu)與一個(gè)隨機(jī)置換區(qū)分出來[9].而在經(jīng)典計(jì)算模型下, 3 輪 Feistel 結(jié)構(gòu)被證明是在多項(xiàng)式時(shí)間內(nèi)無法與隨機(jī)置換區(qū)分的[10].在 2012 年,Kuwakado 和 Morii 又對(duì) Even-Mansour 類型的分組密碼結(jié)構(gòu)進(jìn)行了類似的分析, 分析的方法仍然是基于 Simon 算法, 結(jié)果表明在量子計(jì)算機(jī)上實(shí)現(xiàn)的 Even-Mansour 分組密碼結(jié)構(gòu)是不安全的, 量子攻擊者可以在多項(xiàng)式時(shí)間內(nèi)尋找到密鑰[11].
在 2016 年美密會(huì)上, Kaplan 等人對(duì) Simon 算法進(jìn)行了擴(kuò)充和完善, 并對(duì)一系列密碼結(jié)構(gòu)工作模式,包括常見的認(rèn)證加密結(jié)構(gòu)CBC-MAC、GCM、OCB 等進(jìn)行了量子攻擊[12].他們的結(jié)果表明在量子計(jì)算機(jī)下實(shí)現(xiàn)的這些結(jié)構(gòu)將不再安全.在同一年的FSE 上,他們也提出了量子差分和線性分析[13].在2017 年亞密會(huì)上, Leander 等人利用 Grover 算法和 Simon 算法的組合, 對(duì)分組密碼 DESX 所采用的 FX 結(jié)構(gòu)進(jìn)行了量子攻擊, 該方法用 Simon 算法作為內(nèi)部判定函數(shù), 來判定搜索到的一個(gè)密鑰是否為正確的密鑰,并且使用Grover 算法作為外部密鑰搜索算法.該結(jié)果表明在量子計(jì)算機(jī)環(huán)境下, DESX 所使用的密鑰白化方法并不能增加安全性[14].
同樣在 RSA 2018 上, Hosoyamada 和 Sasaki 分析了攻擊者對(duì)密碼結(jié)構(gòu)使用經(jīng)典計(jì)算機(jī)在線查詢,使用量子計(jì)算機(jī)進(jìn)行離線計(jì)算的情形下的復(fù)雜度, 并給出了相關(guān)的時(shí)空折中復(fù)雜度結(jié)果[15].在 SCN 2018 上, 他們對(duì) Feistel 擴(kuò)展結(jié)構(gòu)進(jìn)行了量子中間相遇攻擊, 結(jié)果顯示量子計(jì)算機(jī)能夠顯著增加中間相遇攻擊的能力[16].
國內(nèi)方面在量子對(duì)稱密碼學(xué)領(lǐng)域研究的文獻(xiàn)較少,Dong 等人在最近的《中國科學(xué)》上對(duì)一些擴(kuò)展Feistel 結(jié)構(gòu)作出了量子 Simon 算法攻擊[17], 在最近的 Eprint 上, Dong 等人結(jié)合 Simon 算法對(duì)滑動(dòng)攻擊(Slide Attack) 進(jìn)行了改進(jìn), 并對(duì)Feistel 的一些變體和GOST 進(jìn)行了密鑰恢復(fù)攻擊[18].
從最近幾年學(xué)術(shù)界發(fā)表的文獻(xiàn)趨勢來看, 分組密碼結(jié)構(gòu)的量子攻擊方法研究已經(jīng)成為各國密碼學(xué)研究的熱點(diǎn)領(lǐng)域.研究人員開始考慮到在量子計(jì)算模型下, 經(jīng)典的分組密碼結(jié)構(gòu)是否能夠達(dá)到一定的偽隨機(jī)性,或者是否存在更為簡單的通用性量子攻擊算法.在當(dāng)前已知的量子算法中, 對(duì)分組密碼結(jié)構(gòu)攻擊最有效的是Simon 算法, 所以本文主要研究常見的分組密碼結(jié)構(gòu)抵抗Simon 量子算法攻擊的安全性.
本文的工作分為以下幾部分.
(1) 梳理針對(duì)現(xiàn)有分組密碼結(jié)構(gòu)的 Simon 量子算法攻擊方法, 研究在 Simon 承諾無法完全滿足時(shí),Simon 算法的成功概率.證明了 Simon 算法中周期函數(shù)的一個(gè)特別性質(zhì), 即若一個(gè)隨機(jī)函數(shù)f具有周期, 則該函數(shù)只存在唯一周期的概率幾乎為1.
(2) 進(jìn)一步具體地指出用 Simon 算法區(qū)分三輪 Feistel 結(jié)構(gòu)時(shí), 若 Feistel 結(jié)構(gòu)中的第二輪的輪函數(shù)F為置換, 而其余兩輪的輪函數(shù)為任意的函數(shù), 就能夠構(gòu)造出完全滿足 Simon 承諾的周期函數(shù).而 Kuwakado 和 Morii 的文章則要求每一輪輪函數(shù)都為置換, 該結(jié)論也可以應(yīng)用到對(duì)其他的類Feistel 分組密碼結(jié)構(gòu), 包括對(duì)CAST256、RC6 結(jié)構(gòu)的攻擊上.
(3) 指出 Dong 等人所引用的 Simon 算法需要得到修改, 因?yàn)?Dong 等人的結(jié)果是基于 Kaplan 等人的算法, 但 Kaplan 等人的理論分析結(jié)果是在直接測量前n個(gè)量子比特的情形下獲得的.而Dong 等的 Simon 算法是要先測量后n個(gè)量子比特, 再測量前n個(gè)量子比特, 根據(jù)量子糾纏理論, 這樣將會(huì)使Kaplan 等人的分析結(jié)果更為復(fù)雜, 需要進(jìn)一步的分析.
(4) 指出Dong 等人對(duì)類RC6 分組密碼結(jié)構(gòu)的Simon 攻擊是不正確的, 并給出了正確的攻擊過程.
(5) 在 CPA 模式下, 使用 Simon 量子算法將三輪 MISTY-L 與 MISTY-R 結(jié)構(gòu)與隨機(jī)置換區(qū)分.
(6) 論證了在量子 CPA 攻擊下, 三輪 Lai-Massey 結(jié)構(gòu)能夠抵抗已知基于 Simon 量子算法的攻擊.從抗Simon 量子算法攻擊的角度講, Lai-Massey 結(jié)構(gòu)優(yōu)于Feistel 結(jié)構(gòu).
Simon 算法于 1994 年提出, 其對(duì)經(jīng)典算法作出指數(shù)級(jí)的加速并啟發(fā)了 Shor 算法的發(fā)現(xiàn)[2].Simon算法解決的問題對(duì)象被稱為Simon 問題, 表述如下.
Simon 問題:給定一個(gè)布爾函數(shù)f:{0,1}n→{0,1}n, 滿足條件x⊕y∈{0,s}?f(x)=f(y), 其中⊕表示二進(jìn)制異或操作, 該條件稱為Simon 承諾, 現(xiàn)在需求出n比特值s.
在經(jīng)典計(jì)算模型下計(jì)算s, 根據(jù)生日界, 需要對(duì)f查詢O(2n/2) 次.而 Simon 量子算法僅需要對(duì)f作出O(n) 次量子查詢.Simon 算法的量子電路如圖1 所示.
圖1 Simon 量子算法Figure 1 Simon’s quantum algorithm
Simon 算法工作步驟如下:
(1) 將 2n個(gè)量子比特的初始狀態(tài)設(shè)置為
(2) 對(duì)前n個(gè)量子比特進(jìn)行 Hadamard 變換后, 2n個(gè)量子比特的狀態(tài)轉(zhuǎn)換為疊加態(tài):
(3) 查詢Uf后, 2n個(gè)量子比特的狀態(tài)為:
(4) 對(duì)后n個(gè)量子比特進(jìn)行測量, 得到f(x) 的一個(gè)n比特隨機(jī)輸出y, 根據(jù)f的性質(zhì), 存在一對(duì)原像 {x,x⊕s} 使得f(x)=f(x⊕s)=y, 所以前n個(gè)量子比特塌縮為
(5) 對(duì)前n個(gè)量子比特再一次應(yīng)用Hadamard 變換后, 其狀態(tài)為:
若y與s的內(nèi)積y·s=1, 則根據(jù)量子相消干涉,的幅度為 0, 所以, 若測量得到一個(gè)n比特則必有y·s=0, 可以將y看作一個(gè)n比特的向量, 并將y的值存下來.
(6) 重復(fù)運(yùn)行步驟 (1–5)n? 1 次, 我們得到n? 1 個(gè)與s正交的向量y1,··· ,yn?1, 令事件Ei,1 ≤i≤n?1 為前i個(gè)向量彼此獨(dú)立的事件, 則有(排除掉向量 0), Pr[Ei|Ei?1]=
上面公式中最后一個(gè)極限可由數(shù)值軟件計(jì)算得出, 即可以至少0.288 的概率得到n?1 個(gè)獨(dú)立向量 {y1,··· ,yn?1}, 隨后也就得到一個(gè)關(guān)于變量s的 (n?1) 個(gè)獨(dú)立的線性方程, 可以在O(n3)的時(shí)間內(nèi)用高斯消元法快速求解得到s.運(yùn)行全算法m次, 尋找到正確的s的值的概率至少為1 ?(1 ?0.288)m, 當(dāng)m=20 的時(shí)候, 算法成功的概率大于 0.99.
在文獻(xiàn) [19]中, Santoli 和 Schaffner 觀察到若f函數(shù)不完全滿足 Simon 承諾, 只滿足條件x⊕y=s?f(x)=f(y),s=0 時(shí), 也可以使用Simon 算法來做區(qū)分攻擊, 但是他們宣稱弱化條件后的 Simon 算法的成功概率會(huì)下降, 這是因?yàn)樵谀承┣闆r下無法得到一系列獨(dú)立的線性方程.
在Simon 承諾條件弱化的情形下, Kaplan 等人也分析了Simon 算法成功的概率[12].在文獻(xiàn)[17]中,Dong 等人使用 Simon 算法對(duì) Feistel 的擴(kuò)展結(jié)構(gòu), 包括 CAST256、RC6 等結(jié)構(gòu)給出了區(qū)分攻擊, 并結(jié)合 Leander 等人的思路給出了對(duì)應(yīng)分組密碼結(jié)構(gòu)的密鑰恢復(fù)攻擊.在這里我們指出 Dong 等人的 Si-mon 算法需要得到修改, 因?yàn)槠浣Y(jié)果是基于 Kaplan 等人的算法, 但 Kaplan 等人的理論分析結(jié)果是在直接測量前n個(gè)量子比特的情形下獲得的.若先測量后n個(gè)量子比特, 再測量前n個(gè)量子比特, 根據(jù)量子糾纏理論, 可能會(huì)影響Kaplan 等人的分析結(jié)果, 需要對(duì)算法成功概率作出進(jìn)一步分析.
當(dāng) Simon 承諾不滿足時(shí), 可以從第 (4) 步開始修改 Simon 算法:
(4) 對(duì)前n個(gè)量子比特再一次應(yīng)用Hadamard 變換.2n個(gè)量子比特狀態(tài)為:
此時(shí), 測量前n個(gè)量子比特得到 |y?的概率為:
由于f存在周期s, 若y·s= 1, 則py的值為 0.所以, 若測量得到一個(gè)n比特 |y?, 則必有y·s=0, 且py與具體的函數(shù)f滿足 Simon 承諾的情形有關(guān).
Kaplan 等人定義了一個(gè)指標(biāo)來衡量一個(gè)函數(shù)與Simon 承諾完全滿足時(shí)的距離[12].該指標(biāo)定義如下:
定義 1對(duì)于一個(gè)存在周期s的函數(shù)f:{0,1}n→{0,1}n, 對(duì)任意的x都有f(x⊕s)=f(x), 令
在文獻(xiàn) [20]中, Daemen 和 Rijmen 給出, 對(duì)于一個(gè)隨機(jī)的函數(shù),
Kaplan 等人的主要工作是證明了如下定理.
定理 1如果?(f,s) ≤p0< 1, 則 Simon 算法在經(jīng)過cn次查詢后, 得到正確s值的概率至少為
我們進(jìn)一步研究發(fā)現(xiàn), 若一個(gè)函數(shù)存在周期, 則該函數(shù)只存在唯一周期的概率接近1.
引理 1若存在一個(gè)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ù)個(gè)數(shù)為NN/2,N=2n.在所有存在周期s的函數(shù)中隨機(jī)選取一個(gè)f,f存在唯一周期的概率為:
證明:令函數(shù)f的N個(gè)n比特輸入集合為A, 由于A可以表示為:
根據(jù)f的性質(zhì), 有所以只需計(jì)算的可能取值的個(gè)數(shù), 每一個(gè)f(xi) 值是從N個(gè) {0,1}n值里選取, 所以存在周期s的函數(shù)集合M的大小為: |M|=NN/2.
在存在周期s函數(shù)f中, 如果存在使得f(xi) 的值與都不同,則f只存在唯一周期s.也就是說, 在函數(shù)f的值域中至少存在一個(gè)y,y的值與值域中其他所有的值都不同.這是因?yàn)槿羝浯嬖诹硗庖粋€(gè)周期有f(x)=f(x⊕t), 則有
由于f(xi) 的值與都不同, 且只有f(xi⊕s) 與f(xi) 相等, 若y∈/{xi,xi⊕s},必有與我們定義的條件矛盾.所以此時(shí)的f函數(shù)必然只存在唯一周期s.
令具有唯一周期s的函數(shù)f的集合為S, 令為都不同的函數(shù)的集合, 則根據(jù)容斥原理,
可以通過 Maple 數(shù)值計(jì)算軟件得出, 當(dāng)n≥ 4, 即N≥24時(shí),P(n) > 0.99.P(n) 的值隨n的大小如圖2 所示.即當(dāng)周期函數(shù)f的輸入輸出長度大于4 時(shí), 其存在唯一周期的概率幾乎為1.
在文獻(xiàn) [9]中, Kuwakado 和 Morii 首次將 Simon 量子算法應(yīng)用到攻擊 3 輪 Feistel 結(jié)構(gòu)上, 他們的結(jié)果表明, 若3 輪Feistel 結(jié)構(gòu)中的輪函數(shù)均為彼此獨(dú)立的置換, 則3 輪的Feistel 結(jié)構(gòu)與一個(gè)隨機(jī)置換在多項(xiàng)式時(shí)間內(nèi)可以區(qū)分[10].在經(jīng)典計(jì)算模型下, 已證明3 輪Feistel 結(jié)構(gòu)與一個(gè)隨機(jī)置換在多項(xiàng)式時(shí)間內(nèi)不可區(qū)分.隨后在文獻(xiàn) [19]中, Santoli 等人給出了對(duì)Feistel 結(jié)構(gòu)在內(nèi)部函數(shù)為隨機(jī)函數(shù)時(shí)的攻擊方法,但并沒有給出詳細(xì)的理論分析.而Kaplan 等人的文章卻給出詳細(xì)的理論分析結(jié)果[12].
對(duì)一個(gè)分組密碼結(jié)構(gòu)Ek: {0,1}n→ {0,1}n使用 Simon 算法攻擊時(shí), 當(dāng)前已知的方法都是基于Ek構(gòu)造得到一個(gè)具有周期s的函數(shù)f, 攻擊者可以對(duì)f進(jìn)行量子疊加態(tài)查詢, 并且獲得了周期s就可以攻破該加密結(jié)構(gòu).當(dāng)前基于Ek構(gòu)造周期函數(shù)f的方法只有如下2 種:
在文獻(xiàn) [9]中, Kuwakado 和 Morii 基于輪函數(shù)為置換的 3 輪 Feistel 結(jié)構(gòu), 構(gòu)造了相應(yīng)的周期函數(shù),并給出對(duì)應(yīng)攻擊.3 輪 Feistel 結(jié)構(gòu)E如圖3 所示, 第i輪的輸入為輸出為令α0和α1為兩個(gè)任意的常量, 構(gòu)造得到的周期函數(shù)f為:
可以驗(yàn)證f(b,x)=f(b⊕1,x⊕F1(α0)⊕F(α1)), 即得到了一個(gè)周期為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當(dāng)F2為置換時(shí), 若X1= (b1,x1),X2= (b2,x2) 且若f(X1) =f(X2), 則有X2=X1⊕s.
證明:因?yàn)槿鬮1=b2=b∈ {0,1}, 由于f(X1) =f(X2), 所以F2(x1⊕F1(αb)) =F2(x2⊕F1(αb)).因?yàn)镕2是一個(gè)置換, 必有x1=x2, 使得X1=X2, 與已知條件矛盾.所以b1=b2, 即b1=b2⊕1.
當(dāng)b1=b2⊕1 時(shí), 由于f(X1)=f(X2), 則有F2(x1⊕F1(αb1))=F2(x2⊕F1(αb2)).因?yàn)镕2是一個(gè)置換, 必有x2=x1⊕F1(α0)⊕F1(α1).即X2=X1⊕s.
所以, 當(dāng) 3 輪 Feistel 結(jié)構(gòu)中的第二輪函數(shù)F2為一個(gè)置換時(shí), 基于此方法構(gòu)造得到的周期函數(shù)f完全滿足Simon 承諾.當(dāng)F2為一個(gè)隨機(jī)函數(shù)時(shí), Kaplan 等人給出了以近似1 的概率有此時(shí)根據(jù)定理1, 當(dāng)c=3 時(shí), 即運(yùn)行 Simon 算法3n次時(shí), 能夠以近似 1 的概率找到函數(shù)f的正確周期s.
在文獻(xiàn) [17]中, Dong 等人對(duì) 4 分支的 5 輪類 RC6 分組密碼結(jié)構(gòu)給出了 Simon 量子算法攻擊, 同時(shí)對(duì)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為
可以計(jì)算得出,f具有周期但該函數(shù)f不能夠被用來構(gòu)造成量子黑盒, 因?yàn)橐@得該函數(shù)f的輸出結(jié)果, 攻擊者需要計(jì)算其中攻擊者能夠獲取αb和但攻擊者無法獲取的值.這是因?yàn)楣粽邿o法訪問f函數(shù)內(nèi)部輪函數(shù)的輸出中間變量.若攻擊者能夠訪問f函數(shù)內(nèi)部輪函數(shù)的輸出, 則整個(gè)攻擊變?yōu)槠椒补?同樣, Dong 等人對(duì)6 分支的7 輪類RC6 分組密碼結(jié)構(gòu)的Simon 量子算法攻擊也是不正確的.
對(duì)4 分支的類RC6 分組密碼結(jié)構(gòu), 基于5 輪類RC6 結(jié)構(gòu)構(gòu)造得到正確的f函數(shù)如下:
同理, 基于7 輪6 分支類RC6 分組密碼結(jié)構(gòu)構(gòu)造得到的正確f函數(shù)如下:
在文獻(xiàn) [21,22]中, Moriai, Vaudenay 以及 Luo 等人的結(jié)果表明, 在經(jīng)典計(jì)算模型下, 4 分支類 RC6 分組密碼結(jié)構(gòu)至少需要 10 輪才能達(dá)到偽隨機(jī)性, 因此, 相對(duì)于經(jīng)典攻擊方法, 對(duì)類 RC6 結(jié)構(gòu)進(jìn)行Simon 量子算法攻擊效果并不顯著.
除了 Feistel 結(jié)構(gòu)以外, 日本學(xué)者 MATSUI 參考 Feistel 結(jié)構(gòu)提出了 MISTY 結(jié)構(gòu), 該結(jié)構(gòu)被用在分組密碼算法 MISTY1 上[23].在文獻(xiàn) [24]中, Gilbert 和 Minier 將 MISTY 結(jié)構(gòu)劃分為 MISTYL 和 MISTY-R 結(jié)構(gòu), 并且證明了 4 輪 MISTY-L 和 3 輪 MISTY-R 結(jié)構(gòu)能夠達(dá)到偽隨機(jī)性.在這里我們基于3 輪MISTY-L 和MISTY-R 結(jié)構(gòu)構(gòu)造其對(duì)應(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ù)如下:
可以計(jì)算得出, 基于該構(gòu)造得到的f函數(shù)具有周期
基于3 輪類MISTY-R 結(jié)構(gòu)構(gòu)造得到的f函數(shù)如下:
可以計(jì)算得出, 基于該構(gòu)造得到的f函數(shù)具有周期
由于在 MISTY-L 和 MISTY-R 結(jié)構(gòu)中,Fi為置換, 構(gòu)造得到的f函數(shù)完全滿足 Simon 承諾, 使得Simon 算法對(duì)這兩個(gè)分組密碼結(jié)構(gòu)完全適用.
Lai-Massey 結(jié)構(gòu)是由瑞士密碼學(xué)家Vaudenay 對(duì)IDEA 算法的結(jié)構(gòu)進(jìn)行修改得到[25].原始的IDEA算法上層結(jié)構(gòu)并不具有理論意義上的偽隨機(jī)性, Vaudenay 對(duì) IDEA 算法結(jié)構(gòu)進(jìn)行了微小改動(dòng), 添加了一個(gè)正形置換σ(x,y) = (y,x⊕y), 從而使該結(jié)構(gòu)具有理論意義上的偽隨機(jī)性, 并被稱為 Lai-Massey 結(jié)構(gòu).Lai-Massey 結(jié)構(gòu)被證明經(jīng)過三輪迭代后具有偽隨機(jī)性, 四輪迭代后具有強(qiáng)偽隨機(jī)性, 其結(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), 對(duì) Lai-Massey 結(jié)構(gòu)的通用性攻擊研究文獻(xiàn)較少.在文獻(xiàn) [26]中, Luo 等人最先給出了對(duì) Lai-Massey 結(jié)構(gòu)的 2 輪偽隨機(jī)性區(qū)分器和 3 輪強(qiáng)偽隨機(jī)性區(qū)分器.在 2011 年的 DCC 上,韓國 Yun 等人認(rèn)為 Lai-Massey 結(jié)構(gòu)和 Feistel 結(jié)構(gòu)具有相同的安全性, 屬于同一家族, 并將該家族命名為 quasi-Feistel 結(jié)構(gòu).他們宣稱在 Luby-Rackoff 模型下, 作為一個(gè)分組密碼設(shè)計(jì), Lai-Massey 結(jié)構(gòu)與 Feistel 結(jié)構(gòu)相比不具備優(yōu)勢[27].這樣的宣稱就使學(xué)術(shù)界認(rèn)為 Lai-Massey 結(jié)構(gòu)只是 Feistel 結(jié)構(gòu)的一種變換結(jié)構(gòu), 分組密碼結(jié)構(gòu)設(shè)計(jì)者使用Lai-Massey 結(jié)構(gòu)來設(shè)計(jì)算法, 相比Feistel 結(jié)構(gòu)沒有優(yōu)勢.
在文獻(xiàn)[28]中, Luo 等人指出, 在5 輪迭代以內(nèi), Lai-Massey 結(jié)構(gòu)與Feistel 結(jié)構(gòu)相比, 對(duì)抗已知通用性攻擊能力更強(qiáng).他們采用了Patarin 對(duì)Feistel 結(jié)構(gòu)分析中所使用的4-Point 攻擊技術(shù)對(duì)Lai-Massey 結(jié)構(gòu)進(jìn)行攻擊.結(jié)果表明 Patarin 對(duì) Feistel 結(jié)構(gòu)的部分攻擊在 Lai-Massey 結(jié)構(gòu)上并不成立.攻擊者攻擊3 輪、4 輪、5 輪 Lai-Massey 結(jié)構(gòu)的查詢復(fù)雜度和計(jì)算復(fù)雜度普遍要高于 Feistel 結(jié)構(gòu).這一結(jié)果表明了Lai-Massey 結(jié)構(gòu)抗現(xiàn)有通用攻擊的能力更強(qiáng).
從已有對(duì)分組密碼結(jié)構(gòu)進(jìn)行 Simon 攻擊的步驟可以得出, 如果基于一個(gè)分組密碼結(jié)構(gòu)可以構(gòu)造一個(gè)周期函數(shù)即x與x⊕s對(duì)于函數(shù)f發(fā)生了碰撞, 因?yàn)閒的內(nèi)部組件是分組密碼結(jié)構(gòu), 則必定在分組密碼結(jié)構(gòu)內(nèi)部狀態(tài)處發(fā)生了碰撞, 并且該碰撞值被用來構(gòu)造周期函數(shù)f的輸出值.
由于Simon 量子攻擊過程中需要獲取周期函數(shù)f的輸出, 若不能獲取f的輸出值, 則無法構(gòu)造量子黑盒提供攻擊者進(jìn)行量子查詢.在本文第3 節(jié)對(duì)3 輪Feistel 結(jié)構(gòu)的Simon 算法攻擊中, 攻擊者可以由明密文對(duì)生成Feistel 結(jié)構(gòu)的第二輪輪函數(shù)F2的碰撞, 并且該碰撞值可以由明文和密文計(jì)算得出, 繼而構(gòu)造周期函數(shù).若對(duì)一個(gè)分組密碼結(jié)構(gòu)進(jìn)行選擇明文攻擊時(shí), 盡管在某未知狀態(tài)處能夠產(chǎn)生碰撞, 但若無法由選擇明密文計(jì)算得出該碰撞值, 則該碰撞特性不能夠用在構(gòu)造周期函數(shù)中, 使得其能夠抵抗Simon 量子攻擊.
下面, 我們將論證三輪 Lai-Massey 結(jié)構(gòu)在選擇明文攻擊下, 其內(nèi)部的任一未知狀態(tài)都不能夠由明密文對(duì)計(jì)算得出.由圖6 可以得出, 一輪Lai-Massey 結(jié)構(gòu)實(shí)際上只產(chǎn)生一個(gè)未知狀態(tài), 即輪函數(shù)Fi的輸出,三輪 Lai-Massey 結(jié)構(gòu)實(shí)際上共有三個(gè)未知狀態(tài), 即輪函數(shù)F1,F2,F3的輸出值u,v,w, 而其他的狀態(tài)都可以由明密文和這三個(gè)未知狀態(tài)計(jì)算得到.
在選擇明攻擊中, 攻擊者可以生成一系列明密文對(duì):
由Lai-Massey 結(jié)構(gòu)的計(jì)算過程可以得出對(duì)于明密文對(duì)(ai∥bi,gi∥hi), 其對(duì)應(yīng)的三個(gè)未知狀態(tài)ui,vi,wi分別為:
由于攻擊者無法獲取三輪Lai-Massey 結(jié)構(gòu)內(nèi)部輪函數(shù)F1,F2,F3的任一輸出值, 所以三個(gè)基本的未知狀態(tài)ui,vi,wi中任意一個(gè)值都無法由選擇明密文對(duì)計(jì)算得出.這樣, 即使攻擊者能夠在某未知狀態(tài)處產(chǎn)生碰撞, 但由于該碰撞值無法由選擇明密文對(duì)計(jì)算得出, 無法使用該特性構(gòu)造碰撞函數(shù), 繼而無法構(gòu)造周期函數(shù), 所以三輪Lai-Massey 結(jié)構(gòu)能夠抵抗Simon 量子算法攻擊.
Lai-Massey 結(jié)構(gòu)與 Feistel 結(jié)構(gòu)在計(jì)算效率上相差無幾, 二者都可以通過修改密鑰調(diào)度來實(shí)現(xiàn)相同的加解密過程.在經(jīng)典計(jì)算模型下, 從已有的結(jié)果可以得出Lai-Massey 結(jié)構(gòu)比Feistel 結(jié)構(gòu)對(duì)抗已有通用攻擊更強(qiáng), 本文結(jié)果又表明在量子CPA 模型下, 相比Feistel 結(jié)構(gòu), Lai-Massey 結(jié)構(gòu)抵抗Simon 量子算法攻擊的能力更強(qiáng), 所以Lai-Massey 結(jié)構(gòu)在分組密碼算法的設(shè)計(jì)中是一個(gè)較好的候選結(jié)構(gòu).
本文對(duì) Simon 量子算法作出進(jìn)一步分析, 證明了當(dāng)Simon 承諾不完全滿足時(shí), 一個(gè)具有周期的隨機(jī)函數(shù)存在唯一周期的概率接近 1.本文同時(shí)指出對(duì) Feistel 結(jié)構(gòu)及其擴(kuò)展結(jié)構(gòu)應(yīng)用 Simon 算法時(shí), 只需要中間的輪函數(shù)為置換, 就可以構(gòu)造出完全滿足 Simon 承諾的周期函數(shù).本文也總結(jié)了 Simon 量子算法對(duì)常見分組密碼結(jié)構(gòu)的攻擊步驟, 修正了Dong 等人對(duì) RC6 算法結(jié)構(gòu)攻擊中的錯(cuò)誤, 對(duì)三輪 MISTYL 和MISTY-R 成功進(jìn)行了區(qū)分攻擊.最后, 本文論證了在量子 CPA 模型下, 三輪 Lai-Massey 結(jié)構(gòu)能夠抵抗Simon 量子算法攻擊.當(dāng)前結(jié)果表明了在抵抗已知攻擊時(shí), 同樣輪數(shù)的Lai-Massey 結(jié)構(gòu)的安全性要強(qiáng)于 Feistel 結(jié)構(gòu).我們建議分組密碼算法設(shè)計(jì)者采用 Lai-Massey 結(jié)構(gòu), 以同樣的輪數(shù)達(dá)到更高的安全性.