改進(jìn)的五輪Gr?stl-512 的量子碰撞攻擊*

董炳佑, 劉 泰, 崔玉龍, 倪博煜, 秦嶺月, 董曉陽(yáng)

1. 清華大學(xué)高等研究院, 北京 100084

2. 中車青島四方機(jī)車車輛股份有限公司, 青島 266111

3. 山東大學(xué)密碼技術(shù)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室, 濟(jì)南 250199

4. 山東大學(xué)網(wǎng)絡(luò)空間安全學(xué)院, 青島 266237

1 前言

在1994 年, Shor 算法[1]的提出, 說(shuō)明一個(gè)足夠大的量子計(jì)算機(jī)可以在多項(xiàng)式時(shí)間內(nèi)分解大整數(shù)、計(jì)算離散對(duì)數(shù)問(wèn)題等, 對(duì)目前使用的許多公鑰密碼方案都帶來(lái)重大安全影響. 這激起了大家對(duì)抗量子計(jì)算機(jī)攻擊的密碼的研究興趣, 公鑰密碼學(xué)社區(qū)和標(biāo)準(zhǔn)化組織在后量子公鑰密碼學(xué)的研究上投入了大量的精力.相比之下, 人們普遍認(rèn)為, 量子計(jì)算攻擊對(duì)對(duì)稱密碼安全性影響有限, 因?yàn)楫?dāng)攻擊者使用量子計(jì)算機(jī)攻擊對(duì)稱密碼時(shí), 優(yōu)勢(shì)是使用Grover 算法[2]來(lái)加速密鑰的搜索, 然而將密鑰長(zhǎng)度加倍就可以解決這個(gè)問(wèn)題.直到2010 年, Kuwakado 和Morii 證明了經(jīng)典可證明安全的Even-Mansour 結(jié)構(gòu)密碼和三輪Feistel 結(jié)構(gòu)可以在量子計(jì)算機(jī)的幫助下在多項(xiàng)式時(shí)間內(nèi)被破解[3,4]. 接下來(lái)的幾年, 更多的對(duì)稱密碼設(shè)計(jì)結(jié)構(gòu)被量子計(jì)算算法攻擊[5–13]. 幾乎所有這些指數(shù)級(jí)加速的攻擊都是通過(guò)Simon 的算法[14]來(lái)找到一個(gè)依賴于密鑰的隱藏周期, 在尋找這個(gè)隱藏周期時(shí), 需要以量子明文疊加態(tài)訪問(wèn)加密算法, 并獲得密文疊加態(tài). 這是一個(gè)相當(dāng)強(qiáng)的要求, 敵手需要在線訪問(wèn)一個(gè)用量子電路實(shí)現(xiàn)的加密算法. 因此, 如果不需要對(duì)密鑰原語(yǔ)的量子疊加預(yù)言機(jī)進(jìn)行在線查詢, 那么使用更高復(fù)雜度的量子計(jì)算攻擊仍然是有意義的[7,15].

與加密算法不同, 哈希函數(shù)不需要密鑰. 因此敵手可以離線實(shí)現(xiàn)哈希函數(shù)的量子電路, 并利用量子疊加態(tài)訪問(wèn)該量子電路, 并獲得量子疊加態(tài). 一個(gè)安全哈希函數(shù)需要具備抗碰撞攻擊、抗原象攻擊和抗第二原象攻擊等安全屬性, 本文針對(duì)AES 類哈希函數(shù)抗碰撞攻擊的安全性展開(kāi)研究. AES 類哈希函數(shù)采用類似于AES 的輪函數(shù)設(shè)計(jì), 典型AES 類哈希算法包括AES 哈希模式AES-MMO/MP、Gr?stl[16]、Whirlpool[17]等. 經(jīng)典計(jì)算環(huán)境下, 反彈攻擊[18]是分析AES 類哈希函數(shù)的有效手段. 在量子計(jì)算環(huán)境下, Hosoyamada 和Sasaki[19]在2020 年歐密會(huì)上提出反彈攻擊的量子實(shí)現(xiàn)算法, 給出了7 輪AESMMO 和6 輪Whirlpool[17]的量子碰撞攻擊. 在2020 年亞密會(huì)上, 董曉陽(yáng)等[20]提出了不使用qRAM的量子碰撞攻擊, 首次超越Chailloux 等[21]給出的一般碰撞攻擊界. 在2021 年美密會(huì)上, Hosoyamada和Sasaki[22]提出了一些列減輪SHA-2 算法的量子碰撞攻擊. 在ToSC 2020 上, Chauhan 等[23]研究了雙塊AES 壓縮函數(shù)模式的量子碰撞攻擊. 在ToSC 2021 上, 倪博煜等[24]研究了Simpira v2 哈希模式的量子碰撞攻擊. 在2021 年亞密會(huì)上, 董曉陽(yáng)等[25]研究了哈希函數(shù)的自由起始的量子碰撞攻擊.

對(duì)于一個(gè)輸出為n比特摘要值的哈希函數(shù), 在經(jīng)典環(huán)境下, 需要O(2n/2) 的時(shí)間復(fù)雜度來(lái)尋找碰撞.在量子計(jì)算環(huán)境下, 根據(jù)已有的量子算法可以得到以下碰撞的一般界:

(3) CNS 算法[21]需要時(shí)間復(fù)雜度T=22n/5來(lái)找到一組碰撞, 另外需要大小為2n/5的經(jīng)典內(nèi)存.那么, 一個(gè)成功的量子碰撞攻擊必須優(yōu)于至少一種量子碰撞攻擊一般界.

1.1 本文貢獻(xiàn)

表1 針對(duì)Gr?stl 的經(jīng)典與量子碰撞攻擊Table 1 Classical and quantum collision attacks on Gr?stl

2 預(yù)備知識(shí)

本節(jié)簡(jiǎn)要介紹類AES 哈希函數(shù)、反彈攻擊、量子計(jì)算和量子隨機(jī)存儲(chǔ)器(quantum random access memory, qRAM), 以及一些常用的量子算法.

2.1 類AES 哈希函數(shù)

為明確起見(jiàn), 首先回顧AES-128 的輪函數(shù). 它作用在排列成矩陣的16 字節(jié)狀態(tài)上, 包括四個(gè)主要的變換: 字節(jié)替換SubBytes(SB)、行位移ShiftRows(SR)、列混合MixColumns(MC) 和密鑰加AddRoundKey(AK), 如圖1 所示. 對(duì)這些變換適當(dāng)修改, 就可以改變輪函數(shù)的參數(shù), 如矩陣的行列數(shù)量、單元的大小、變換作用的順序, 乃至交換行列排列(亦即將矩陣轉(zhuǎn)置), 進(jìn)而新參數(shù)可以生成新的輪函數(shù)設(shè)計(jì).這種在AES 輪函數(shù)上進(jìn)行修改的設(shè)計(jì)可以粗略稱為類AES 輪函數(shù). 本文假定列混合(MC) 是將狀態(tài)矩陣的每一列乘上一個(gè)MDS 矩陣的操作.

圖1 AES 輪函數(shù)Figure 1 Round function of AES

Gr?stl 算法是SHA-3 最終候選哈希函數(shù)之一, 有Gr?stl-256 和Gr?stl-512 兩個(gè)版本. 處理兩個(gè)消息分組的的結(jié)構(gòu)如圖2, 其中P和Q是兩個(gè)n比特的類AES 置換. 在算法輸出哈希值之前,一個(gè)基于P的輸出變換和一個(gè)截?cái)嗪瘮?shù)Ω :→會(huì)作用在h2上. 更多算法設(shè)計(jì)細(xì)節(jié)讀者可以參考文獻(xiàn)[16].

董曉陽(yáng)等[20]給出了Gr?stl-512 的4 輪、5 輪經(jīng)典和量子碰撞攻擊. 圖3 展示了Gr?stl 的等價(jià)描述.令P-和Q-為去掉最后一個(gè)MixBytes(MB) 操作的類AES 置換, 有如下等價(jià)表示, 其中1≤i ≤t,

圖2 處理兩個(gè)消息分組的Gr?stl-Figure 2 Gr?stl- with two message blocks

圖3 處理兩個(gè)消息分組的Gr?stl-: 等價(jià)表示Figure 3 Alternative descriptionofGr?stl-n withtwomessage blocks

2.2 量子計(jì)算和量子隨機(jī)存儲(chǔ)器

一個(gè)擁有n個(gè)量子比特的系統(tǒng)狀態(tài)可以描述為 C2n空間上的一個(gè)單位向量, 可取一組正交基{|0···00〉,|0···01〉,··· ,|1···11〉}來(lái)表示, 稱為計(jì)算基(computational basis). 它是量子計(jì)算中常用的一組基, 亦可記為{|i〉: 0≤i ＜2n}. 一般來(lái)說(shuō), 量子算法的實(shí)現(xiàn)即是利用一系列的酉變換和測(cè)量對(duì)量子系統(tǒng)進(jìn)行操控, 而所有的酉變換可以用一組單量子比特和雙量子比特變換來(lái)表示. 這種表示即是標(biāo)準(zhǔn)量子電路模型下的量子門表示, 一個(gè)量子算法的效率就可以用表示該算法需要使用的量子門數(shù)量來(lái)定量描述.

2.2.1 經(jīng)典電路的疊加態(tài)預(yù)言機(jī)

給定一個(gè)經(jīng)典的布爾函數(shù):f:→F2.f的疊加態(tài)預(yù)言機(jī)定義為作用在一個(gè)(n+1)-量子比特的系統(tǒng)上的酉變換Uf, 它將基態(tài)|x,y〉變?yōu)閨x,y ⊕f(x)〉, 其中x ∈,y ∈F2. 作為一個(gè)線性算子,Uf作用在疊加態(tài)上將得到

注意到, 只要存在一個(gè)高效的經(jīng)典電路可以計(jì)算f, 那么Uf就可以用量子電路模型高效實(shí)現(xiàn), 而如前所述, 這只需要找到一個(gè)實(shí)現(xiàn)f的高效可逆電路, 再將其中的可逆門電路用量子門替代就可以了.

2.2.2 Grover 算法[2]

這里存在一個(gè)漏洞: Grover 算法的整體復(fù)雜性可能被隱藏在所調(diào)用的預(yù)言機(jī)電路的構(gòu)造開(kāi)銷中了.除非預(yù)言機(jī)的電路可以被高效實(shí)現(xiàn), 否則算法對(duì)于搜索的加速將會(huì)沒(méi)有作用. 因此, 明確實(shí)現(xiàn)這樣的預(yù)言機(jī)需要怎樣的資源是十分重要的, 例如高效實(shí)現(xiàn)預(yù)言機(jī)可能需要一個(gè)大容量的qRAM.

2.2.3 量子振幅放大算法[31]

量子振幅放大可以視作Grover 算法的一種推廣, 后者限制A產(chǎn)生所有基向量的均一疊加態(tài). 類似地, 在分析量子振幅放大的復(fù)雜度時(shí), 應(yīng)當(dāng)計(jì)入實(shí)現(xiàn)UP和A的復(fù)雜度.

2.2.4 量子隨機(jī)存儲(chǔ)器(qRAM)

量子隨機(jī)存儲(chǔ)器(qRAM) 是經(jīng)典隨機(jī)存儲(chǔ)器(RAM) 的量子版本, 它使用n量子比特來(lái)表示任何2n個(gè)存儲(chǔ)單元構(gòu)成的量子疊加態(tài). 給定一列經(jīng)典數(shù)據(jù)L={x0,x1,··· ,x2n-1}, 其中xi ∈Fm2,L對(duì)應(yīng)的qRAM 可以用一個(gè)酉變換

其中i ∈,y ∈, 且|·〉A(chǔ)ddr和|·〉Out分別是地址和輸出存儲(chǔ)器. 這樣一來(lái), 就可以訪問(wèn)這些數(shù)據(jù)的任意量子疊加態(tài), 輸入對(duì)應(yīng)地址的量子疊加態(tài)就能得到:

到目前為止, 如何構(gòu)造一個(gè)可行的qRAM (至少說(shuō)是大容量的qRAM) 仍舊未知. 盡管如此, 這一令人失望的事實(shí)并沒(méi)有阻止研究者在假定大容量qRAM 可用的模型下開(kāi)展工作, 就像人們?cè)诮?jīng)典或量子計(jì)算機(jī)被建造出來(lái)之前早就開(kāi)始研究經(jīng)典或量子算法一樣. 另一方面, 大容量qRAM 尚未出現(xiàn), 而規(guī)模O(n) 的qRAM 可以用規(guī)模O(n) 的量子電路進(jìn)行模擬, 因此嘗試減少甚至避免qRAM 在量子算法中的使用進(jìn)行研究是相當(dāng)有意義的.

2.3 反彈攻擊及其改進(jìn)

反彈攻擊是由文獻(xiàn)[18] 首先引入的, 如圖4 所示, 它包含入站階段(Inbound) 和出站階段(Outbound). 在入站階段, 通過(guò)中間相遇降低復(fù)雜度, 從而找到滿足入站階段差分的數(shù)據(jù)對(duì), 該數(shù)據(jù)對(duì)被稱為起點(diǎn)(Starting Point). 然后在出站階段, 通過(guò)大量的起點(diǎn)數(shù)據(jù)對(duì)分別向前和向后推算, 找到滿足出站階段差分的數(shù)據(jù)對(duì).

圖4 反彈攻擊Figure 4 Rebound attack

為了提升入站階段的差分路徑可以覆蓋的輪數(shù), 文獻(xiàn)[32,33] 分別獨(dú)立地提出了超級(jí)S 盒技術(shù), 把連續(xù)兩輪類AES 輪函數(shù)視作一個(gè)由超級(jí)S 盒構(gòu)成的整體. 后來(lái)文獻(xiàn)[34] 指出利用非全活躍超級(jí)S 盒的差分性質(zhì)可以顯著地降低反彈攻擊所需要的空間復(fù)雜度.

下面考慮更一般的情況: 某密碼系統(tǒng)的內(nèi)部狀態(tài)是一個(gè)d×d矩陣, 每個(gè)單元代表c比特?cái)?shù)據(jù). 參考圖5 是d=4 的情況, 對(duì)應(yīng)有d=4 個(gè)超級(jí)S 盒.

2.4 全活躍超級(jí)S 盒

沿用圖5 中的記號(hào), 利用全活躍超級(jí)S 盒的反彈攻擊的入站階段, 步驟如下:

圖5 全活躍與非全活躍超級(jí)S 盒差分路徑對(duì)比Figure 5 Differential of full-active and non-full-active super S-box

對(duì)于給定的Δin, 可以生成2d·c對(duì)起點(diǎn), 需要d×2d·c的空間來(lái)儲(chǔ)存d個(gè)列表, 生成一對(duì)起點(diǎn)的平均時(shí)間復(fù)雜度為O(1).

2.5 非全活躍超級(jí)S 盒

考慮一列由d個(gè)c比特單元組成的狀態(tài)A, 經(jīng)過(guò)超級(jí)S 盒SSB = SB°MC°SB 被映射為狀態(tài)D= SSB(A), 中間狀態(tài)依次為B和C, 其中SB 是d個(gè)c×c的小S 盒的并聯(lián), 而MC : Fd2c →Fd2c是分支數(shù)為n+1 的MDS 線性變換, 那么有命題1 成立.

命題1(MDS 性質(zhì)) 令MC·(X[0],X[1],··· ,X[d-1])T= (Y[0],Y[1],··· ,Y[d-1])T, 若X[0],X[1],··· ,X[d-1],Y[0],Y[1],··· ,Y[d-1] 中至少一半已知, 那么可以由等式關(guān)系推知其余未知項(xiàng).

假設(shè)一個(gè)差分輸入超級(jí)S 盒, 使得其中有s個(gè)c×c的S 盒不活躍, 那么活躍的S 盒有2d-s個(gè). 而S 盒不會(huì)改變作用前后狀態(tài)中各單元的差分, 所以(A,D) 和(B,C) 都各有s個(gè)單元不活躍. 為了生成一對(duì)數(shù)據(jù), 使其滿足給定的輸入輸出差分(ΔA,ΔD), 進(jìn)行以下操作:

(1) 猜測(cè)(A,D) 的活躍單元中的d-s個(gè)單元.

(2) 由(A,D) 猜測(cè)的d-s個(gè)單元計(jì)算(B,C) 中對(duì)應(yīng)的d-s個(gè)單元, 并計(jì)算差分(ΔB,ΔC).

(3) 結(jié)合(ΔB,ΔC) 中s個(gè)不活躍的單元差分, 共有d單元被MC 作用的輸入輸出差分已知. 根據(jù)命題1, 可以求得這一截?cái)嗖罘致窂街械乃胁罘?

(4) 現(xiàn)在(B,C) 中d-s個(gè)單元已被確定, 另需確定s個(gè)單元才能通過(guò)MC 完全確定(B,C) 的全部單元. 通過(guò)查詢DDTs次來(lái)獲得這s個(gè)單元, 引入s比特輔助變量β來(lái)區(qū)分2s種可能的選擇.

(5) 結(jié)合步驟(2) 獲得(B,C) 的d-s個(gè)單元和由DDT 獲得的s個(gè)單元, 根據(jù)命題1 可以確定余下的d個(gè)單元.

(6) 至此, 剩余未用的活躍S 盒數(shù)目為

可以當(dāng)做一個(gè)(d-s)c比特的篩選器, 滿足差分的過(guò)篩概率為2-(d-s)c. 這樣就得到了滿足給定SSB 差分的完整數(shù)據(jù)對(duì)(A,D) 和(A′,D′).

上述操作的復(fù)雜度包含s次DDT 查詢和4(d-s) 次S 盒計(jì)算. 平均意義上, 成功找到一對(duì)數(shù)據(jù)需要重復(fù)操作2(d-s)c×2s次以遍歷初始猜測(cè)和s比特輔助變量β, 對(duì)應(yīng)大約2(d-s)c+s×s次DDT 查詢和2(d-s)c+s×4(d-s) 次S 盒計(jì)算. 假設(shè)一次DDT 查詢相當(dāng)于一次S 盒計(jì)算, 那么經(jīng)典設(shè)定下的整體時(shí)間復(fù)雜度為:

而在量子設(shè)定下, 利用Grover 算法得到加速后的時(shí)間復(fù)雜度(包括逆運(yùn)算) 為:

同時(shí)需要216大小的qRAM 來(lái)存儲(chǔ)DDT. 詳細(xì)定義及實(shí)現(xiàn)參見(jiàn)文獻(xiàn)[20].

根據(jù)式公式(1) 與(2), 復(fù)雜度主項(xiàng)為2(d-s)c(在本文中c=8), 因此最大化s可以降低復(fù)雜度.

3 董曉陽(yáng)等的5 輪Gr?stl-512 的碰撞攻擊[20]

3.1 5 輪經(jīng)典碰撞攻擊

(1) 隨機(jī)選取240對(duì)消息分組(m0,m′0), 計(jì)算差分Δv1=v1⊕v′1, 使得藍(lán)色字節(jié)對(duì)應(yīng)的差分滿足初始條件, 平均而言可以得到一組滿足條件的(m0,m′0) 和Δv1.

(2) 針對(duì)消息分組m1進(jìn)行反彈攻擊. 注意到輸入差分Δin由Δv1唯一確定, 而輸出差分Δout有8個(gè)活躍字節(jié), 因此利用全活躍超級(jí)S 盒技術(shù), 可以找到264個(gè)m1滿足對(duì)應(yīng)的入站階段的差分路徑. 而對(duì)于出站階段的差分路徑, 后向的截?cái)嗖罘致窂?128→64→8→1→8→8) 成立的概率為2-56, 而前向的差分傳播經(jīng)過(guò)一次前饋8 字節(jié)異或, 差分抵消的概率為2-64. 因此可以以概率264×2-56×2-64=2-56確定滿足要求的差分路徑和中間狀態(tài)v2, 對(duì)應(yīng)的時(shí)間復(fù)雜度為264.如果沒(méi)有求得所需差分, 那么用下一個(gè)消息分組和之前產(chǎn)生的中間狀態(tài)來(lái)重復(fù)同樣的攻擊. 平均而言, 在對(duì)256個(gè)消息分組進(jìn)行計(jì)算之后會(huì)成功消去差分, 得到正確的路徑.

(3) 重復(fù)步驟(2), 不斷逐列消去中間狀態(tài)包含的活躍差分, 直到剩余兩列活躍差分.

(4) 可以利用步驟(2) 的技巧同時(shí)消去最后兩列活躍差分, 但反彈攻擊的成功概率有所不同. 因?yàn)槿胝倦A段的差分的輸出狀態(tài)中有16 個(gè)活躍字節(jié), 可以利用全活躍超級(jí)S 盒技術(shù)得到216×8= 2128個(gè)起點(diǎn), 對(duì)應(yīng)的時(shí)間復(fù)雜度為2128. 接著考慮出站階段的差分, 相應(yīng)的截?cái)嗖罘致窂?88→96→16→2→16→16) 成立的概率為2-112, 而兩列之間的相互消去發(fā)生的概率為2-128. 因此在步驟(4) 之內(nèi), 有2128×2-112×2-128=2-112的概率得到滿足要求的碰撞, 對(duì)應(yīng)的時(shí)間復(fù)雜度為2128. 同樣地, 在平均意義上用2112個(gè)消息分組重復(fù)步驟(4) 就能得到碰撞.

上述攻擊的時(shí)間復(fù)雜度主項(xiàng)是步驟(4), 可以估計(jì)為2112×2128=2240. 存儲(chǔ)超級(jí)S 盒需要空間復(fù)雜度264. 最終, 獲得一組碰撞使用了2112個(gè)消息分組計(jì)算.

3.2 5 輪Gr?stl-512 量子碰撞攻擊

董曉陽(yáng)等[20]中基于上述5 輪經(jīng)典碰撞攻擊, 利用量子算法可以得到加速后的5 輪量子碰撞攻擊, 即用Grover 算法替代經(jīng)典攻擊中的窮舉搜索.

圖6 5 輪Grostl-512 的碰撞攻擊Figure 6 Collision attacks on 5-round Grostl-512

(1) 利用Grover 算法,找到符合藍(lán)色字節(jié)的初始條件的第一輪輸入一對(duì)消息分組和對(duì)應(yīng)輸出差分,所對(duì)應(yīng)的復(fù)雜度約是經(jīng)典情況的一半規(guī)模, 即220.

(2) 逐列消去中間狀態(tài)差分的多輪反彈攻擊, 每一輪都需要檢查264對(duì)起點(diǎn)(Δin,Δout) 是否能推導(dǎo)出8 個(gè)活躍字節(jié)的消除. 這里整個(gè)狀態(tài)空間大小為264, SB 操作涉及16 個(gè)獨(dú)立聯(lián)合作用的超級(jí)S 盒, 利用2.5 節(jié)的技術(shù), 需要增加15 比特的輔助變量α, 因而搜索空間擴(kuò)大到264×215=279.

(3) 最后一輪反彈攻擊同時(shí)消去兩列差分, 與步驟(2) 相似, 也需要15 比特的輔助變量α, 搜索空間相應(yīng)地?cái)U(kuò)大到2128×215輪Gr?stl-512 中有5×2×128 = 1280 次S 盒計(jì)算, 這里與文獻(xiàn)[20] 中用4 輪Gr?stl-512 來(lái)估計(jì)不同., 這一部分是復(fù)雜性的主項(xiàng).

相當(dāng)于226.67/1280≈216.35次5 輪Gr?stl-512 運(yùn)算. 類似的,s=4 的SSB 有6 個(gè), 每個(gè)對(duì)應(yīng)的時(shí)間復(fù)雜度約為212.65次5 輪Gr?stl-512 運(yùn)算, 而s ≥5 的SSB 對(duì)應(yīng)的時(shí)間復(fù)雜度可以忽略不計(jì). 綜上, 步驟(3) 的時(shí)間復(fù)雜度為

圖7 五輪Gr?stl-512 的碰撞攻擊中的最后一輪反彈攻擊差分路徑示意圖[20]Figure 7 Inbound phase of last step of collision attack on Gr?stl-512 [20]

平均意義上, 成功找到一組碰撞需要運(yùn)行14 輪步驟(2), 每輪重復(fù)256次, 還需要將步驟(3) 重復(fù)運(yùn)行2112次, 前者相對(duì)后者可以忽略不計(jì). 因此量子碰撞攻擊的時(shí)間復(fù)雜度為288.05×2112≈2200.05, 同時(shí)需要216大小的qRAM 來(lái)儲(chǔ)存DDT.

類似地, 為了成功找到一組碰撞平均需要將步驟(3) 重復(fù)運(yùn)行2112次, 因此不需要qRAM 的量子碰撞攻擊總的時(shí)間復(fù)雜度為289.00×2112≈2201.0.

因?yàn)槭褂? 輪Gr?stl-512 (1280 個(gè)S 盒) 而非4 輪Gr?stl-512 (1024 個(gè)S 盒) 來(lái)估計(jì)時(shí)間復(fù)雜度,這里給出的復(fù)雜度結(jié)論與文獻(xiàn)[20] 中略有不同, 總體上少了大約1280/1024≈20.32.

4 改進(jìn)的5 輪Gr?stl-512 量子碰撞攻擊

4.1 基本算法實(shí)現(xiàn)細(xì)節(jié)

為了明確使用振幅放大算法進(jìn)行碰撞攻擊的細(xì)節(jié), 首先推導(dǎo)文獻(xiàn)[20] 中Gr?stl-512 碰撞攻擊的實(shí)現(xiàn)細(xì)節(jié), 這部分在文獻(xiàn)[20] 作為利用非全活躍超級(jí)S 盒的AES-MMO 碰撞攻擊的推廣沒(méi)有明確給出.

首先, 需要預(yù)先計(jì)算DDT 的輸入輸出差分, 存儲(chǔ)在表中以便查詢, 即文獻(xiàn)[20] 中的算法1.

算法1 S 盒S(x) 的輸入輸出差分分布表[20]Output: T 1 Let T be an empty dictionary;2 for δin ∈F82 do 3for x ∈F82 do 4 x′ ←x ⊕δin, y ←S(x), y′ ←S(x′), δout ←y ⊕y′;5 if x ≤x′ then 6 Insert (x,x′,y,y′) into T[(δin,δout)];end 8end 9 end 10 return T;7

接下來(lái)著重分析反彈攻擊最后一輪中用到的非全活躍超級(jí)S 盒的差分路徑, 因?yàn)檫@一輪是整個(gè)碰撞攻擊過(guò)程中復(fù)雜性的主項(xiàng). 以圖7 中紅框標(biāo)出的一個(gè)超級(jí)S 盒為例, 其不活躍字節(jié)數(shù)s=7, 截?cái)嗖罘致窂饺鐖D8. 從這個(gè)例子出發(fā), 整個(gè)攻擊中涉及的其他超級(jí)S 盒的差分路徑可以結(jié)合2.5 節(jié)的結(jié)論進(jìn)行類推.

圖8 Gr?stl-512 最后一輪反彈攻擊中一個(gè)非全活躍超級(jí)S 盒的截?cái)嗖罘致窂紽igure 8 Differential of one non-full-active super S-box in last round rebound attack of Gr?stl-512

根據(jù)2.5 節(jié)的一般化討論, 取Gr?stl-512 對(duì)應(yīng)的參數(shù)為d=8,c=8, 則可利用命題1 生成滿足該SSB的差分路徑的數(shù)據(jù)對(duì), 具體步驟如算法2 所示. 這需要先猜測(cè)d-s= 1 個(gè)(A,D) 中的活躍字節(jié)(不妨設(shè)為A[0]), 作為輸入傳遞給算法2 最終輸出所需數(shù)據(jù)對(duì). 算法2 的成功概率為2-7×2-8=2-15, 因此在平均意義下遍歷15 比特輸入(A[0],β) 后可以輸出1 對(duì)滿足SSB 輸入輸出差分的數(shù)據(jù)對(duì). 算法2 運(yùn)行一次需要執(zhí)行s= 7 次DDT 訪問(wèn)(步驟3 到9) 和4 次S 盒計(jì)算(步驟1 和25), 因此輸出所需數(shù)據(jù)對(duì)的平均復(fù)雜度為215×11, 這符合將d=8,c=8,s=7 代入公式(1)的結(jié)果.

算法2 生成非全活躍超級(jí)S 盒的輸入輸出數(shù)據(jù)對(duì)Input: (ΔA,ΔD), A[0], β = (β0,··· ,β7)Output: 數(shù)據(jù)A 滿足SSB(A)⊕SSB(A ⊕ΔA) = ΔD 1 B[0] = S(A[0]), B′[0] = S(A[0]⊕ΔA[0]), ΔB[0] = B[0]⊕B′[0]/* 算上(ΔB,ΔC) 中7 個(gè)非活躍字節(jié), 總計(jì)2 利用命題1, 計(jì)算ΔB[1],ΔB[2],ΔB[5],ΔB[7] 和ΔC[1],ΔC[3],ΔC[5],ΔC[7]/* 查詢DDT 獲取對(duì)應(yīng)輸入輸出差分的數(shù)據(jù),3 (A[2],A′[2],B[2],B′[2]) ←T[(ΔA[2],ΔB[2])]4 for i ∈{3,5,7} do 5(A[i],A′[i],B[i],B′[i]) ←T[(ΔA[i],ΔB[i])]6(C[i],C′[i],D[i],D′[i]) ←T[(ΔC[i],ΔD[i])]7 end/* 按β 的值選取(A[2],A[3],A[5],A[7],C[3],C[5],C[7]) 的組合: 若β0 = 0 則取β0 = 1 則取β0 ·ΔA[2] = ΔA[2] */8 A[2] = A[2]⊕β0 ·ΔA[2], A′[2] = A[2]⊕ΔA[2];9 B[2] = B[2]⊕β0 ·ΔB[2], B′[2] = B[2]⊕ΔB[2];10 for (i,j) ∈{(3,1),(5,2),(7,3)} do 11A[i] = A[i]⊕βj ·ΔA[i], A′[i] = A[i]⊕ΔA[i];12B[i] = B[i]⊕βj ·ΔB[i], B′[i] = B[i]⊕ΔB[i];13C[i] = C[i]⊕βj ·ΔC[i], C′[i] = C[i]⊕ΔC[i];14D[i] = D[i]⊕βj ·ΔD[i], D′[i] = D[i]⊕ΔD[i];15 end/* 加上步驟1 得到的B[0], (B,C) 有16 利用命題1, 求出B 和C 的所有值/* 在所有活躍的S 盒中, 只剩下(ΔC[1],ΔD[1]) 尚未考慮, 可17 if S(C[1])⊕S(C[1]⊕ΔC[1]) = ΔD[1]18 then 19return A ←SB-1(B) and A ⊕ΔA 20 end有8 字節(jié)差分已知*/成功的概率為2-7 */β0 ·ΔA[2] = 0, 若8 個(gè)字節(jié)已經(jīng)確定*/以視作一個(gè)過(guò)濾器*//* 成功概率2-8 */

2注意到給定(Δvj,mj,Δuj) 推導(dǎo)16 個(gè)超級(jí)S 盒的輸入輸出差分時(shí), 若對(duì)每個(gè)超級(jí)S 盒都存在一對(duì)滿足條件的輸入輸出, 那么由此可以組合出216/2 = 215 種不同的起點(diǎn), 因此需要引入15 比特的指標(biāo)αj 來(lái)指示如何選擇起點(diǎn).

算法4 UFj 的實(shí)現(xiàn)Input: |mj,Δvj,Δuj;α〉|y〉, α = (α0,··· ,α14) ∈F152 Output: |mj,Δvj,Δuj;α〉|y ⊕Fj(mj,Δvj,Δuj;α)〉1 for k ∈{0,·,14} do 2ΔA(k)j ←Δvj; ΔD(k)j ←Δuj;3對(duì)函數(shù)G(k)j (mj,ΔA(k)j ,ΔD(k)j ;·) 運(yùn)行Grover 搜索, 輸出A(k)j [0] ∈F82 和β(k) ∈F7 2 j ←P(i)(mj,ΔA(k)j ,ΔD(k)j ,A(k)j {d-s},β(k),αj)5 end 6 ΔA(15)4A(k)j←Δvj; ΔD(15)j←Δuj;7 對(duì)函數(shù)G(15)j (mj,ΔA(15)j ,ΔD(15)j ;·) 運(yùn)行Grover 搜索, 輸出A(15)j {d-s} ∈F82 和β(15) ∈F7 2 8 A(15)j←P(i)(mj,ΔA(15)j ,ΔD(15)j ,A(15)j {d-s},β(15))/* 從|mj,Δvj,Δuj;α〉 生成反彈攻擊起點(diǎn)*/9 A ←(A(0)j ,··· ,A(15)j )10 A′ ←(A(0)j ⊕ΔA(0)j ,··· ,A(15)j⊕ΔA(15)j )11 if (A,A′)滿足出站差分路徑then 12return |mj,Δvj,Δuj;α〉|y ⊕1〉13 else 14return |mj,Δvj,Δuj;α〉|y〉15 end

4.2 振幅放大算法實(shí)現(xiàn)

在3.2 節(jié)中,通過(guò)重復(fù)運(yùn)行步驟(2)和步驟(3)來(lái)提高算法的成功概率,也即反復(fù)運(yùn)行對(duì)UFj的Grover搜索. 注意到在量子環(huán)境下, 還可以利用振幅放大算法來(lái)改進(jìn)提高成功概率的過(guò)程. 這就是說(shuō), 把步驟(1)和(2) 聯(lián)合起來(lái)不進(jìn)行重復(fù)運(yùn)行, 整體可以看做一個(gè)過(guò)程, 它不需要給定輸入而是進(jìn)行一系列隨機(jī)數(shù)據(jù)選取和操作, 最后(隨機(jī)) 輸出一對(duì)消息分組m0,m′0和一系列中間值, 使得得到反彈攻擊最后一輪前只剩兩列差分沒(méi)有消去的狀態(tài)vi-1, 而vi-1滿足最后一輪88→96→16→2→16→16 的差分路線并最終得到一組碰撞的概率是2-112. 根據(jù)5 輪經(jīng)典攻擊的描述, 在經(jīng)典環(huán)境下, 上述過(guò)程需要2128時(shí)間復(fù)雜度;而根據(jù)3.2 節(jié), 在量子環(huán)境下, 上述過(guò)程需要288.05時(shí)間復(fù)雜度.

4.3 不使用qRAM 的改進(jìn)量子碰撞算法

5 總結(jié)

我們利用振幅放大算法改進(jìn)了文獻(xiàn)[20] 中針對(duì)Gr?stl-512 的5 輪量子碰撞攻擊, 主要是優(yōu)化了這一隨機(jī)算法提高成功概率的流程,復(fù)雜度降低為原來(lái)的.可以看到,在構(gòu)造與本文攻擊類似地,基于反彈攻擊的量子碰撞攻擊時(shí), 振幅放大算法的使用應(yīng)當(dāng)納入考慮之中,它可以有效優(yōu)化算法流程、提高運(yùn)行效率. 振幅放大算法在這一方面仍有更大的應(yīng)用空間, 值得進(jìn)一步研究.