MIBS 算法量子密碼分析*

李艷俊, 林 昊, 易子晗, 謝惠琴

1. 北京電子科技學院, 北京 100070

2. 密碼科學技術(shù)國家重點實驗室, 北京 100878

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

1 引言

隨著量子計算機的不斷發(fā)展, 密碼領(lǐng)域?qū)⒚媾R巨大革新. 一方面, 上世紀90 年代Shor 算法[1]的提出使得公鑰密碼受到量子計算的嚴重威脅, 這促使公鑰領(lǐng)域?qū)ふ腋嗔孔影踩慕鉀Q方案, 后量子密碼算法研究迅速崛起. 另一方面, 量子計算對對稱密鑰密碼的影響也逐步擴大, 如Grover 算法[2]提升了二次方根的量子搜索速度, Simon 算法[3]可以構(gòu)造量子區(qū)分器等.

根據(jù)Zhandry[4]給出的在量子環(huán)境中的PRF (偽隨機函數(shù), pseudorandom function) 安全性的概念, Kaplan 等人[5]提出了兩種不同的模型來對對稱密碼進行量子密碼分析:

· 標準安全性(表示為Q1 模型): 如果沒有有效的量子算法能夠僅通過經(jīng)典查詢將分組密碼與PRP(偽隨機置換, pseudorandom permutation) (或PRF) 區(qū)分開, 則分組密碼對于量子敵手是標準安全的.

· 量子安全性(表示為Q2 模型): 如果沒有有效的量子算法即使通過量子查詢也無法將分組密碼與PRP (或PRF) 區(qū)分開, 則分組密碼對于量子敵手是量子安全的.

在Q1 模型中, 敵手使用經(jīng)典方法收集數(shù)據(jù)并利用量子運算處理它們, 而在Q2 模型中, 敵手可以直接利用經(jīng)典輸入構(gòu)造量子疊加態(tài)查詢密碼Oracle, 并接收相應輸出的疊加態(tài). 近年來, 許多學者在Q2 模型下評估了許多特定對稱密碼的安全性. 在2010 年, Kuwakado 等人基于Simon 算法[3]構(gòu)造了Feistel結(jié)構(gòu)的周期函數(shù)[6], 提出了對稱密碼算法量子分析技術(shù), 緊接著證明了Even-Mansour 結(jié)構(gòu)在量子疊加態(tài)詢問機制下是不安全的[7]; 2016 年美密會上, Kaplan 等人[8]繼續(xù)推進分組密碼領(lǐng)域的量子分析技術(shù), 給出了對LRW 結(jié)構(gòu)以及分組密碼工作模式的量子周期函數(shù)構(gòu)造, 將復雜度由O(2n/2) 減少到O(n); 緊接著在2017 年亞密會上, Leander 和May 結(jié)合了Simon 和Grover 的算法來攻擊FX 結(jié)構(gòu)的分組密碼[9].Dong 等人也給出了廣義Feistel 結(jié)構(gòu)的量子周期函數(shù)構(gòu)造方法[10]和量子密鑰恢復攻擊[11]. Bonnetain等人研究了AES 的量子安全性分析, 并提出了一種新的結(jié)構(gòu)化搜索框架[12]. Hosoamada 和Sasaki 在2020 年的歐密會上提出了第一個專門針對哈希函數(shù)的量子攻擊[13]. 隨后Dong 等人證明了Hosoamada和Sasaki 提出的量子攻擊所需要的量子隨機存取存儲器的數(shù)量可以顯著減少, 提出了第一次專門針對哈希函數(shù)的量子碰撞攻擊[14], 同時也有其他學者對不同的哈希函數(shù)提出了專門的量子攻擊, 這種方法越來越受到學術(shù)界的關(guān)注和應用. 本文對MIBS 算法進行量子攻擊就是專門針對其內(nèi)部輪函數(shù)進行了量子攻擊, 在此之前Dong 等人[15]就針對Feistel 結(jié)構(gòu)的具體輪函數(shù)提出了量子攻擊方法, 并應用到了DES 和GOST 算法上.

本文將針對MIBS 算法構(gòu)建更多輪數(shù)的量子區(qū)分器, 并進行量子密鑰恢復攻擊. MIBS 是一個Feistel結(jié)構(gòu)的輕量級分組密碼算法[16], 其設(shè)計目標是普遍適用于資源受限的環(huán)境, 如RFID 標簽和傳感器網(wǎng)絡(luò).MIBS 密碼的分組長度為64 比特, 支持64 和80 比特的密鑰長度, 分別記為MIBS-64 和MIBS-80, 迭代輪數(shù)為32 輪. 其輪函數(shù)與Camellia[17]密碼算法類似. 目前對于MIBS 的分析有線性分析[18]、差分分析[18]、不可能差分分析[18]和積分分析[19]等. 此前還未有文獻對MIBS 算法進行量子密碼分析.

在這項工作中, 我們使用MIBS 輪函數(shù)的特定內(nèi)部結(jié)構(gòu)來構(gòu)造量子區(qū)分器, 并研究其在Q2 模型中的量子密鑰恢復攻擊, 本文的主要貢獻如下:

(1) 我們充分利用了MIBS 算法的輪函數(shù)及其線性變換P的性質(zhì), 基于Simon 算法提出了MIBS 的5 輪量子區(qū)分器.

(2) 介紹Leander 和May[9]提出的Simon 和Grover 算法的結(jié)合算法, 引入通用量子密鑰恢復攻擊方法. 使用上述量子區(qū)分器, 構(gòu)造MIBS 的特殊量子密鑰恢復攻擊. 令r表示為MIBS 的輪數(shù),當r=7 時, 我們的攻擊需要212次量子查詢; 當r ＞7 時, 我們的攻擊需要212+16(r-7)次量子查詢. 我們的攻擊降低了時間復雜度和量子比特數(shù)量. 表1 中總結(jié)了針對MIBS 算法的經(jīng)典攻擊和量子攻擊的結(jié)果, 其中所列經(jīng)典攻擊結(jié)果為MIBS-64 的攻擊結(jié)果.

(3) 同時進一步探究量子密碼分析方法的研究方向, 給出具體思路及其研究目標.

表1 MIBS 算法攻擊結(jié)果Table 1 Attack results for MIBS

本文整體結(jié)構(gòu)如下: 第2 節(jié)介紹MIBS 算法及其符號說明; 第3 節(jié)介紹量子區(qū)分器和量子密鑰恢復攻擊的相關(guān)工作; 第4 節(jié)給出MIBS 算法的5 輪量子區(qū)分器和7 輪量子密鑰恢復攻擊的時間復雜度; 第5 節(jié)總結(jié)全文并給出下一步工作計劃.

2 預備知識

2.1 符號說明

2.2 MIBS 算法簡介

MIBS 是Feistel 結(jié)構(gòu)的輕量級分組密碼算法[16], 如圖1 所示. MIBS 分組長度為64 比特, 支持64和80 比特的密鑰長度, 分別記為MIBS-64 和MIBS-80, 迭代輪數(shù)為32 輪. MIBS 中所有迭代操作都是基于半字節(jié)的, 也就是4 比特. MIBS 的輪函數(shù)為SPN 結(jié)構(gòu), 如圖2 所示輪函數(shù)F包括異或子密鑰、S盒層和線性層P.

圖1 MIBS 加密圖Figure 1 Encrypt round of MIBS

圖2 MIBS 輪函數(shù)結(jié)構(gòu)圖Figure 2 Round function of MIBS

在攻擊中我們將用到線性層P的逆P-1, 表示如下:

矩陣形式表示為:

3 相關(guān)工作

3.1 Simon 算法

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

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

3.2 Grover 算法及其與Simon 結(jié)合算法

與傳統(tǒng)算法相比, Grover 算法[2]可以在數(shù)據(jù)庫搜索問題上實現(xiàn)二次加速. 讓我們考慮以下問題:

問題1 給定黑盒中的函數(shù)f:{0,1}n →{0,1}, 存在x使得f(x)=1, 目標是查找x使得f(x)=1.

Grover 算法能夠使用O(n) 個量子比特和O(2n/2) 次f查詢解決上述問題. 該算法由復雜度為O(1)的f的基本步驟迭代組成, 并且容易實現(xiàn)并行化. 算法具體步驟如下:

2017 年亞密會上, Leander 和May[9]結(jié)合Simon 算法和Grover 算法, 提出了一種針對FX 結(jié)構(gòu)的量子密鑰恢復攻擊方法. FX 結(jié)構(gòu)如圖3 所示: Enc(x)=Ek0(x ⊕k1)⊕k2.

圖3 FX 結(jié)構(gòu)圖Figure 3 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); 但對于k/=k0,f(k,·)不是周期性的. 他們結(jié)合了Simon和Grover 的算法, 在qCPA 場景下攻擊了幾種基于FX 的密碼(PRINCE[20], PRIDE[21], DESX[22]),其復雜度約為232.

在此基礎(chǔ)上, Dong 等人[11]和Hosoyamada 等人[23]分別獨立地應用Leander 和May 的方法攻擊了通用Feistel 結(jié)構(gòu). 他們給出了5 輪Feistel 結(jié)構(gòu)的量子密鑰恢復攻擊, 該攻擊需要2nr/4-3n/4次量子查詢, 與量子暴力搜索相比時間復雜度降低了20.75n, 與最好的經(jīng)典攻擊相比時間復雜度降低了20.5n, 且不會產(chǎn)生任何內(nèi)存成本.

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

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

令α0,α1為任意常數(shù), 構(gòu)造周期函數(shù)f如下所示.

易證f(b,x) =f(b ⊕1,x ⊕F1(α0)⊕F1(α1)), 即周期s= (1,F1(α0)⊕F1(α1)). 然后, 通過Simon算法在多項式時間內(nèi)可以獲得周期s.

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

Dong 等人提出了5 輪Feistel 結(jié)構(gòu)的密鑰恢復攻擊[11], 如圖5 所示,=F4(k4,F5(k5,X52)⊕)⊕.

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

根據(jù)3 輪量子區(qū)分器的周期函數(shù), 可得:

4 MIBS 量子密碼分析

4.1 MIBS 的5 輪量子區(qū)分器

本節(jié)主要介紹如何構(gòu)造MIBS 的5 輪量子區(qū)分器, 并證明其可行性. 如圖6 所示, 我們將MIBS 的輸入按半字節(jié)劃分, 0000000αb為第1 分支的輸入, 其中αb是最低半字節(jié).P(0000000x) 為第2 分支的輸入, 其中P(0000000x) 是0000000x經(jīng)過線性變換P得到的, 并且x是最低半字節(jié).

根據(jù)輸入, 可得:

其中*=s(αb)⊕x, s為4×4 的S 盒. 為構(gòu)造周期函數(shù)需先證明定理1 成立.

“要做到客戶去找你，而不是你去找客戶，這樣才能使企業(yè)實現(xiàn)長遠發(fā)展。”夏碎娒的一席話給我們留下了深刻印象。

定理1令h(*,αb)=F3(F2(P(0000000*))⊕(0000000αb)),h(*,αb) 的第2 個和第4 個半字節(jié)只與* 有關(guān), 其中*=s(αb)⊕x.

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

證明:根據(jù)矩陣P可得:

其中ci表示該值僅與* 相關(guān),di表示該值與*,αb均相關(guān). 由上式計算結(jié)果可知h(*,αb) 的第2 個和第4 個半字節(jié)只與* 有關(guān).

根據(jù)定理1 和量子區(qū)分器構(gòu)造原理, 可構(gòu)造如下函數(shù):

其中*=s(αb)⊕x,P(0000000*)4的值不包含*,Si表示第i輪的S 盒操作, ()4表示第4 個半字節(jié).

定理2函數(shù)f(b,x) 為周期函數(shù), 周期s=1||s(α0)⊕s(α1), 即f(b,x)=f(b ⊕1,x ⊕s(α0)⊕s(α1)).

證明:由定理1 可知h(*,αb) 的第2 個和第4 個半字節(jié)只與* 有關(guān), 函數(shù)f(b,x) 包含h(*,αb) 的第4 個半字節(jié), 且其余變量均與* 有關(guān), 所以函數(shù)f(b,x) 的值僅與* 有關(guān).

當b=1 時,f(b,x), 此時*=s(α1)⊕x; 對于f(b ⊕1,x ⊕s(α0)⊕s(α1)), 此時*=s(α1⊕1)⊕x ⊕s(α0)⊕s(α1)=s(α1)⊕x. 故兩函數(shù)對應的* 值相同, 所以f(1,x)=f(1⊕1,x ⊕s(α0)⊕s(α1)).

綜上, 可以證明f(b,x)=f(b ⊕1,x ⊕s(α0)⊕s(α1)), 并且存在周期s, 周期s的長度為5 比特.

上述過程是我們根據(jù)h(*,αb) 的第4 個半字節(jié)只與* 有關(guān)的性質(zhì)得到了一條MIBS 的5 輪量子區(qū)分器, 同理根據(jù)定理1 中h(*,αb) 的第2 個半字節(jié)只與* 有關(guān)的性質(zhì)也可以得到另一條MIBS 的5 輪量子區(qū)分器.

4.2 MIBS 的7 輪量子密鑰恢復攻擊

本節(jié)主要基于上述提出的5 輪量子區(qū)分器對MIBS 做量子密鑰恢復攻擊. 我們將在3.4 節(jié)中量子密鑰恢復攻擊方法的基礎(chǔ)上引入擴充層P, 創(chuàng)新密鑰恢復攻擊方法并以此減小量子比特數(shù)和時間復雜度. 首先在5 輪量子區(qū)分器上加上2 輪進行攻擊, 如圖7 所示.

圖7 MIBS 的7 輪量子密鑰恢復攻擊Figure 7 7-round quantum key-recovery attack on MIBS

其次, 定義如下函數(shù):

改變表示形式, 得函數(shù):

根據(jù)周期函數(shù), 我們只考慮第4 個半字節(jié), 進一步可得:

證明:根據(jù)文獻[9], 可知密鑰恢復攻擊所需量子比特數(shù)公式如下:

其中sum 表示所需量子數(shù)的總和,nk表示密鑰的長度,nin表示周期函數(shù)的輸入長度,nout表示周期函數(shù)的輸出長度, ?n表示周期s的長度.

上述為MIBS 的7 輪量子密鑰恢復攻擊, 當輪數(shù)增加時, 時間復雜度將以每輪216進行遞增. 如令r表示為MIBS 的輪數(shù), 當r ＞7 時, 我們的攻擊需要212+16(r-7)次量子查詢.

5 總結(jié)與展望

Kuwakado 和Morii 研究了Feistel 的的3 輪量子區(qū)分器, 但并沒有考慮到密碼算法的輪函數(shù), 使得區(qū)分器的輪數(shù)不夠長. 本文研究的新型量子區(qū)分器構(gòu)造方法, 充分考慮了輪函數(shù)的具體構(gòu)造, 構(gòu)造了更長輪數(shù)的量子區(qū)分器. 同時也將密碼算法的擴充層P引入密鑰恢復攻擊過程中, 創(chuàng)新了密鑰恢復攻擊方法并減小了量子比特和時間復雜度. 針對MIBS 算法, 我們提出了5 輪量子區(qū)分器和7 輪量子密鑰恢復攻擊, 其時間復雜度為212.

下一步工作計劃: 在Q2 模型下研究如何增加經(jīng)典分組密碼量子區(qū)分器的輪數(shù), 并進一步研究量子密鑰恢復攻擊技術(shù)以減少時間復雜度. 在上述量子密碼分析的基礎(chǔ)上, 繼續(xù)探討可以抵抗量子攻擊的分組密碼算法的設(shè)計方案.