董炳佑, 劉 泰, 崔玉龍, 倪博煜, 秦嶺月, 董曉陽

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

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

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

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

1 前言

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

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

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

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

1.1 本文貢獻(xiàn)

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

2 預(yù)備知識

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

2.1 類AES 哈希函數(shù)

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

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

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

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

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

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

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

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

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

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

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

2.2.2 Grover 算法[2]

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

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

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

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

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

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

到目前為止, 如何構(gòu)造一個可行的qRAM (至少說是大容量的qRAM) 仍舊未知. 盡管如此, 這一令人失望的事實并沒有阻止研究者在假定大容量qRAM 可用的模型下開展工作, 就像人們在經(jīng)典或量子計算機(jī)被建造出來之前早就開始研究經(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). 在入站階段, 通過中間相遇降低復(fù)雜度, 從而找到滿足入站階段差分的數(shù)據(jù)對, 該數(shù)據(jù)對被稱為起點(diǎn)(Starting Point). 然后在出站階段, 通過大量的起點(diǎn)數(shù)據(jù)對分別向前和向后推算, 找到滿足出站階段差分的數(shù)據(jù)對.

圖4 反彈攻擊Figure 4 Rebound attack

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

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

2.4 全活躍超級S 盒

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

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

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

2.5 非全活躍超級S 盒

考慮一列由d個c比特單元組成的狀態(tài)A, 經(jīng)過超級S 盒SSB = SB°MC°SB 被映射為狀態(tài)D= SSB(A), 中間狀態(tài)依次為B和C, 其中SB 是d個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)系推知其余未知項.

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

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

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

(3) 結(jié)合(ΔB,ΔC) 中s個不活躍的單元差分, 共有d單元被MC 作用的輸入輸出差分已知. 根據(jù)命題1, 可以求得這一截斷差分路徑中的所有差分.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

董曉陽等[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é)的初始條件的第一輪輸入一對消息分組和對應(yīng)輸出差分,所對應(yīng)的復(fù)雜度約是經(jīng)典情況的一半規(guī)模, 即220.

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

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

相當(dāng)于226.67/1280≈216.35次5 輪Gr?stl-512 運(yùn)算. 類似的,s=4 的SSB 有6 個, 每個對應(yīng)的時間復(fù)雜度約為212.65次5 輪Gr?stl-512 運(yùn)算, 而s ≥5 的SSB 對應(yīng)的時間復(fù)雜度可以忽略不計. 綜上, 步驟(3) 的時間復(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次, 前者相對后者可以忽略不計. 因此量子碰撞攻擊的時間復(fù)雜度為288.05×2112≈2200.05, 同時需要216大小的qRAM 來儲存DDT.

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

因為使用5 輪Gr?stl-512 (1280 個S 盒) 而非4 輪Gr?stl-512 (1024 個S 盒) 來估計時間復(fù)雜度,這里給出的復(fù)雜度結(jié)論與文獻(xiàn)[20] 中略有不同, 總體上少了大約1280/1024≈20.32.

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

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

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

首先, 需要預(yù)先計算DDT 的輸入輸出差分, 存儲在表中以便查詢, 即文獻(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

接下來著重分析反彈攻擊最后一輪中用到的非全活躍超級S 盒的差分路徑, 因為這一輪是整個碰撞攻擊過程中復(fù)雜性的主項. 以圖7 中紅框標(biāo)出的一個超級S 盒為例, 其不活躍字節(jié)數(shù)s=7, 截斷差分路徑如圖8. 從這個例子出發(fā), 整個攻擊中涉及的其他超級S 盒的差分路徑可以結(jié)合2.5 節(jié)的結(jié)論進(jìn)行類推.

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

算法2 生成非全活躍超級S 盒的輸入輸出數(shù)據(jù)對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 個非活躍字節(jié), 總計2 利用命題1, 計算ΔB[1],ΔB[2],ΔB[5],ΔB[7] 和ΔC[1],ΔC[3],ΔC[5],ΔC[7]/* 查詢DDT 獲取對應(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 個字節(jié)已經(jīng)確定*/以視作一個過濾器*//* 成功概率2-8 */

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

算法4 UFj 的實現(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對函數(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 對函數(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 振幅放大算法實現(xiàn)

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

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

5 總結(jié)

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