多輪EM結構的量子差分碰撞密鑰恢復攻擊

張中亞 吳文玲 鄒 劍

1(中國科學院軟件研究所可信計算與信息保障實驗室 北京 100190) 2(中國科學院大學 北京 100049) 3(洛陽師范學院 河南洛陽 471934) 4(福州大學數學與計算機科學學院 福州 350108)

量子計算機的發展及量子算法的應用對密碼算法的設計和分析產生了巨大而深遠的影響[1]，在量子環境下對對稱密碼的安全性評估已成為密碼學研究中的一個熱點問題.已有的量子算法中針對對稱密碼的分析方法主要有Grover量子算法[2]、Simon量子算法[3]以及Grover和Simon量子算法相結合的量子攻擊[4]等.已有的公開文獻中基于上述量子算法的加速優勢，對各類對稱密碼結構進行了基于不同模型、不同條件下的量子分析.

Kuwakado等人[5]對3輪Feistel結構進行了量子條件下的區分攻擊，3輪Feistel結構與隨機置換可以在多項式時間內區分，而在經典條件下，已證明3輪Feistel結構與隨機置換不能在多項式時間內區分.Kuwakado等人[6]對EM(Even，Mansour)結構[7]進行了基于Simon量子算法的量子分析，在量子條件下，單輪EM結構是不安全的，量子敵手可以在多項式時間內找到密鑰.Kaplan等人[8]利用Simon量子算法在多項式時間內破解了一系列廣泛使用的基于分組密碼的認證和認證加密工作模式.Kaplan等人[9]基于Grover量子算法提出了量子差分和線性分析.

Leander等人[4]利用Grover量子算法和Simon量子算法的結合，對分組密碼DESX(extension of DES)所采用的FX(extension of block cipher F)結構[10-11]進行了量子攻擊，FX結構的安全強度和其底層分組密碼的安全強度一致，前后白化密鑰沒有提高算法的安全強度.此后，結合Grover和Simon量子算法，基于不同的量子設置條件，更多的密碼結構(Feistel結構，Type-1型、Type-2型、Type-3型廣義Feistel結構)被分析研究，經典條件下已證明多個在多項式時間內不可區分的結構在量子條件下可以區分[12-19].

基于Grover量子算法和Simon量子算法的密碼結構安全性評估的文獻較為常見，但作為生日碰撞攻擊量子化的BHT(Brassard，H?yer，Tapp)量子算法[20]，還沒有公開文獻研究其針對對稱密碼的安全性評估，僅有對算法本身的研究[21-23].由于經典條件下，生日碰撞攻擊在對密碼算法安全性評估中的廣泛應用，研究量子條件下碰撞算法對密碼算法的安全性評估和BHT量子算法在密碼算法上的具體應用具有重要的意義.

本文通過對多輪EM結構進行分析，研究了經典條件和量子條件下的碰撞算法與差分密鑰恢復攻擊的結合，從BHT量子算法的角度對差分密鑰恢復攻擊進行量子化.本文的主要貢獻有2個方面：

1)研究了經典條件下多輪EM結構的差分碰撞密鑰恢復攻擊.針對多輪EM分組密碼結構，結合經典條件下的生日碰撞，我們對其進行了差分碰撞密鑰恢復攻擊，當差分傳遞概率2-p≥2-n /2時，r輪EM結構的密鑰恢復時間復雜度為O(2p+n /2)，比窮舉最后輪密鑰的時間復雜度O(2p+n)快了2n /2倍.

2)基于BHT量子算法對多輪EM結構的差分碰撞密鑰恢復攻擊進行量子化.通過研究BHT量子算法和差分密鑰恢復攻擊的結合，對多輪EM結構的差分碰撞密鑰恢復攻擊進行量子化，當差分傳遞概率2-p>2-n /3時，結合BHT量子算法的量子差分碰撞密鑰恢復時間復雜度要優于Grover搜索的直接二次加速，顯示了BHT量子算法在密碼分析中的有效性.

1 量子算法與量子分析模型

本文主要研究生日碰撞和BHT量子算法與差分密鑰恢復攻擊的結合，從而對經典密碼分析方法進行量子化，本文的關注重點是差分密碼分析的密鑰恢復階段，不從差分鏈的選取進行研究.

1.1 Grover量子算法

Grover量子算法[2]由Grover在1996年提出，對于1個擁有N個數據的無序數據庫，用Grover量子算法只需搜索O(N1/2)次，而經典算法需要O(N)次.Grover量子算法加快了對經典條件下密鑰的搜索，對經典安全通信構成了威脅.

Grover量子算法使用1個n量子比特寄存器Oracle，包括可能需要的附加工作量子比特，算法的目的是用最少的Oracle應用次數求出搜索問題的1個解.

算法從n量子比特初態|0?n開始，用Hadamard變換使計算機處于疊加態量子搜索算法由反復應用Grover迭代的量子子程序組成.通過進行次Grover迭代，就能以概率O(1)得到搜索問題的1個解(M為解的個數)，這是在量子條件下對經典算法要求的O(N/M)次Oracle調用的二次加速.

1.2 BHT量子算法

BHT量子算法[20]由Brassard，H?yer，Tapp在1998年提出，BHT量子算法被設計為針對2-to-1目標函數F求解碰撞，即對于函數：

F:X→Y，

其中,|X|=2|Y|，|Y|=2n.

BHT量子算法以Grover量子算法為基礎，以O(2n /3)的量子查詢復雜度、量子時間復雜度、量子存儲復雜度找到函數F的1個碰撞，算法過程為：

Step1.從集合X中隨機挑選2n /3個元素，放入集合X′.

Step2.詢問函數F，構造列表L={(x,F(x))}，其中x∈X′，|L|=2n /3，并將列表L存于量子存儲單元中.

Step3.檢查L中是否存在碰撞.

Step3.1.若L中存在碰撞，即有(x,F(x)),(y,F(y))∈L，滿足x≠y且F(x)=F(y)，則輸出碰撞.

Step3.2.若L中不存在碰撞，構造分類函數：

應用Grover量子算法對F1(x)求解.

BHT量子算法的量子查詢復雜度、量子時間復雜度、量子存儲復雜度均為O(2n /3).

1.3 量子分析模型

依據Zhandry[24]給出的量子設置中偽隨機函數(pseudo-random function, PRF)和偽隨機置換(pseudo-random permutation，PRP)安全性的概念，Kaplan等人[9]根據收集數據方式的不同，在對密碼進行量子分析時，提出標準安全和量子安全2種不同的量子分析模型.

如果沒有有效的量子算法能夠通過只進行經典查詢區分分組密碼與PRP(或PRF)，那么分組密碼就是針對量子分析的標準安全，簡稱Q1模型，該模型中，分析者用經典方式收集數據，用量子計算處理數據；如果即使能進行量子查詢，也沒有有效的量子算法能夠區分分組密碼與PRP(或PRF)，則分組密碼對量子分析是量子安全，簡稱Q2模型，該模型中，分析者可以直接用經典輸入的量子疊加來查詢密碼oracle，并接收相應輸出的疊加.

由于Q2模型的強大的量子查詢能力，現有公開的量子密碼分析文獻中大都采用Q2模型.Q2模型中，對手的攻擊能力非常強，但有可能設計安全的協議來抵抗這種攻擊.很多在經典模型中安全的消息鑒別碼(message authentication codes, MAC)和認證加密算法(authenticated encryption, AE)被Q2攻擊[8]破解.另一方面，在量子模型中，假設標準安全PRF或量子安全PRF，常見的加密模式已經被證明是安全的[25].

2 差分碰撞密鑰恢復攻擊

EM密碼結構是Even和Mansour[6]提出的分組密碼結構，可認為是高級加密標準(Advanced Encryption Standard, AES)的簡約形式.已經證明，任何經典算法都需要密鑰長度的子指數時間來破譯EM密碼，在這個意義上，EM密碼結構對任何經典對手都是安全的.

Fig.1 One round EM structure

單輪EM結構如圖1所示，P是{0,1}n上的公開隨機置換，密鑰k=k1‖k2長度為2n(單位為b)，其中k1,k2∈{0,1}n.加密算法為c=Ek(m)=P(k1⊕m)⊕k2，其中m,c∈{0,1}n分別是明文及其密文，解密以m=Dk(c)=P-1(k2⊕c)⊕k1進行.

通過迭代置換P并在其中插入密鑰k1,k2,…,kr+1的方式，可以獲得r輪EM結構：

EMk1,k2,…,kr+1(m)=

P(P(P(m⊕k1)⊕k2)⊕…)⊕kr+1，

其中，r+1個輪子密鑰可以相互獨立，也可以由主密鑰一并生成，本文假設r+1個輪子密鑰k1,k2,…,kr+1相互獨立.

根據差分密碼分析的概念，多輪EM密碼一般意義上的差分密碼分析如圖2所示：

Fig.2 Differential cryptanalysis of r-round EM structure

本文不考慮差分鏈的搜尋，關注的重點是恢復密鑰kr+1階段的復雜度.

P(y⊕β)⊕kr+1=c′，

DK(c)=m，

DK(c′)=m⊕α,

成立.

在經典條件中，一般利用

P-1(c⊕kr+1)⊕P-1(c′⊕kr+1)=β

對密鑰kr+1進行測試，直接窮舉或通過分析具體算法先求出部分值，再通過窮舉剩余密鑰的方式求解密鑰kr+1，計算復雜度為O(2p+n)，密鑰恢復過程如圖3所示:

Fig.3 Key recovery of differential cryptanalysis

將c′表示為以c和β為輸入的函數：

c′=EK(m⊕α)=P(P-1(c⊕kr+1)⊕β)⊕kr+1.

P和β的值已知，可以構造函數c″：

c″=P(P-1(c)⊕β).

如圖4所示，進而構造f函數：

f=c′⊕c″=

P(P-1(c⊕kr+1)⊕β)⊕P(P-1(c)⊕β)⊕kr+1=

EK(m⊕α)⊕P(P-1(c)⊕β)=

EK(DK(c)⊕α)⊕P(P-1(c)⊕β).

Fig.4 Construction of f=c′⊕ c″ function

也即，當差分傳遞鏈成立時，f函數可以寫為

f=P(P-1(c⊕kr+1)⊕β)⊕P(P-1(c)⊕β)⊕kr+1.

對于f函數，當差分傳遞概率不同時，有2種情況：

1)差分傳遞概率為1

即無論變量c如何變化，β總是以概率1出現，也即f函數以概率1成立.

當f函數輸入為c和c⊕kr+1時，有

f(c)=P(P-1(c⊕kr+1)⊕β)⊕P(P-1(c)⊕β)⊕kr+1，

f(c⊕kr+1)=P(P-1(c⊕kr+1⊕kr+1)⊕β)⊕

P(P-1(c⊕kr+1)⊕β)⊕kr+1=

P(P-1(c)⊕β)⊕P(P-1(c⊕kr+1)⊕β)⊕

kr+1=f(c)，

即函數值保持不變，函數f(c)存在周期s=kr+1.

在經典條件下，由生日碰撞攻擊可知，當任意選取2n /2個輸入c時，可以高概率求出1對碰撞(c,c⊕kr+1)，使得f(c)=f(c⊕kr+1)，從而輕易求出密鑰kr+1，時間復雜度和數據復雜度為O(2n /2).

2)差分傳遞概率2-p<1

當輸入2p個差為α的對時，存在1個輸入對的輸出差為β，出現2n /2個符合輸出差的輸入對時，根據生日攻擊，即可以高概率求出1對碰撞(c,c⊕kr+1)，使得f(c)=f(c⊕kr+1)，也即可高概率求出密鑰kr+1.那么在計算2n /2×2p個輸入c的函數值f(c)后，存在1對碰撞(c,c⊕kr+1)，時間復雜度和數據復雜度為

O(2n /2×2p)=O(2n /2+p).

由于對輸入c的形式不做限制，可以在選擇明文攻擊的條件下對多輪EM結構進行差分密鑰恢復攻擊.

算法1.基于生日碰撞的多輪EM結構差分密鑰恢復攻擊.

輸入：明文m集合M(|M|=2n /2+p)；

輸出：密鑰kr+1.

Step1. 任選1個包含2n /2+p個m元素的集合M.

Step2. 對于每一個m，分別計算：

c=EK(m)，

c′=EK(m⊕α)，

c″=P(P-1(c)⊕β)，

g(m)=c′⊕c″=

EK(m⊕α)⊕P(P-1(EK(m))⊕β).

Step3. 檢查是否存在不同的m值(m0,m1)，使得g(m0)=g(m1)成立.

Step4. 對于每1對碰撞，計算：

kr+1=EK(m0)⊕EK(m1).

Step5. 將m0或m1對應的c和c′，以及kr+1代入式：

P-1(c⊕kr+1)⊕P-1(c′⊕kr+1)=β，

驗證該式是否成立，如果成立則輸出密鑰kr+1.

復雜度分析：

EM結構分組和密鑰長度以及隨機置換P的輸入均為n位，生日碰撞攻擊下，對于g(m)函數，2n /2+p個輸入值約有2p個碰撞出現，共得到2p個候選密鑰.在隨機假設的條件下，錯誤密鑰通過公式P-1(c⊕kr+1)⊕P-1(c′⊕kr+1)=β測試的概率為2-n，則通過測試的錯誤密鑰數為2p-n.

1)p>n/2時，集合M中元素個數2n /2+p>2n，超過數據總長度，攻擊失敗.

2)p≤n/2時，集合M中元素個數2n /2+p≤2n，通過測試的錯誤密鑰數為2p-n≤2-n /2<1.2n /2+p個明文中共有2n /2個明文及其構成的差為α的明文對，r-1輪后輸出差為β.即在生日碰撞攻擊下，有2n /2個輸入值符合f函數，則可以高概率求出1對所需碰撞，進而求出正確密鑰，時間復雜度和數據復雜度均為

O(2n /2×2p)=O(2n /2+p).

當p≤n/2時，對比經典條件下的r輪EM結構的差分密鑰恢復的時間復雜度O(2p+n)，我們對r輪EM結構的差分碰撞密鑰恢復攻擊速度提高了2n /2倍，時間復雜度明顯降低.

3 量子差分碰撞密鑰恢復攻擊

本節基于BHT量子算法對多輪EM結構差分密鑰恢復攻擊進行量子化.由第2節分析可知，g(m)函數成立的概率為前r-1輪輸入輸出差(α,β)的差分傳遞概率2-p，當1對m值(m0,m1)同時滿足g(m)函數時，概率為2-p×2-p=2-2p，那么g(m)函數為2-to-1函數的概率也為2-2p，此時g(m)函數以概率2-2p符合BHT量子算法的適應條件.

可以在量子Q2模型下，以量子選擇明文的攻擊條件，通過BHT量子算法對多輪EM結構差分碰撞密鑰恢復攻擊進行量子化.

算法2.基于BHT量子算法的多輪EM結構差分密鑰恢復攻擊.

輸入：明文m集合M′(|M′|=l)；

輸出：密鑰kr+1.

Step1.從明文m集合中隨機挑選l個元素，放入集合M′.

Step2.詢問函數g(m)，構造列表L={(m,g(m))}，其中m∈M′，|L|=l，將列表L存于量子存儲單元中.

Step3.檢查L中是否存在不同的m值(m0,m1)，使得g(m0)=g(m1)成立.

Step3.1.對于每1對碰撞，計算：

kr+1=EK(m0)⊕EK(m1).

Step3.2.將m0或m1對應的c和c′，以及kr+1代入式：

P-1(c⊕kr+1)⊕P-1(c′⊕kr+1)=β.

驗證該式是否成立，如果成立則輸出密鑰kr+1.

Step4.若L中不存在碰撞或無法解出正確密鑰kr+1，構造分類函數：

Step5.應用Grover量子算法對g1(m)求解，計算并輸出kr+1=EK(m0)⊕EK(m).

復雜度分析：

Step3前需要計算g(m)函數的l個輸出值，并都存在量子存儲空間中，此步驟需要l的量子存儲復雜度、量子查詢復雜度與量子時間復雜度.

已知g(m)函數成立的概率為前r-1輪的差分傳遞概率2-p，出現(m0,m1)同時符合g(m)函數的概率為2-2p，由于列表L中的元素個數為l，因此在Step4中調用Grover量子算法對g1(m)求解時對應解的個數是l×2-2p.

L中所有數據都存在量子空間中，因此Grover量子算法每次查詢都能以量子疊加態訪問所有l個數據，依據Grover量子算法，有

則設量子時間復雜度:

其中，TO為以量子疊加態訪問Oracle的時間，T|ψ為Hadamard變換的時間.算法將L的元素都存在量子寄存器里，依據量子時間復雜度約定，若能以量子疊加態訪問Oracle，則只需要O(1)的時間，即TO=O(1).

由于Step3前需要計算函數g(m)的l個輸出值，總的量子時間復雜度為

max{l,2n /2+p×l-1/2}.

當l=2n /2+p×l-1/2，即l=2n /3+2p/3時，可得max{l,2n /2+p×l-1/2}最小值為O(2n /3+2p/3).

另外，當l×2-2p≥1，即l≥22p時Grover搜索才能有解，即上述復雜度成立的條件為

l=2n /3+2p/3≥22p，即p≤n/4.

當p≤n/4時，有最小復雜度O(2n /3+2p/3)，否則，量子時間復雜度為max{l,2n /2+p×l-1/2}，其中l≥22p，考慮2個可變參數l和p.

1)參數l

① 當l=2n /3+2p/3時，有最小值2n /3+2p/3；

② 當l<2n /3+2p/3時，max{l,2n /2+p×l-1/2}=2n /2+p×l-1/2；

③ 當l>2n /3+2p/3時，max{l,2n /2+p×l-1/2}=l.

2)參數p

①p≤n/4時，取l=2n /3+2p/3≥22p，max{l,2n /2+p×l-1/2}有最小值2n /3+2p/3；

②n/42n /3+2p/3，max{l,2n /2+p×l-1/2}=l，且需l≥22p，取l=22p，則有max{l,2n /2+p×l-1/2}=l=22p；

③p>n/2時，由于l×2-2p<2n×2-2p<1，Grover搜索無解，量子碰撞算法不能對該差分分析量子化，此時，和經典生日攻擊一致，p>n/2時，2n /2+p>2n，所需數據量超過所有明密文對個數，無法求出正確密鑰.

有關文獻中的量子差分攻擊只用Grover搜索進行量子化，當只用Grover量子搜索對本文所述差分分析進行量子化時，其分類函數為

該分類函數取1的概率為2-n-p，根據Grover量子算法，找到密鑰kr+1的時間復雜度為O(2n /2+p/2).

1)p≤n/4時，有

O(2n /3+2p/3)

2)n/4

max{l,2n /2+p×l-1/2}=l=22p<2n /2+p/2，

也即有:

O(22p)

上述2種情況下，基于BHT量子算法的差分密鑰恢復結果優于直接利用Grover搜索.

3)n/3≤p

max{l,2n /2+p×l-1/2}=l=22p≥2n /2+p/2，

也即有

O(22p)≥O(2n /2+p/2).

此種情況下，Grover搜索結果更優.

經典條件和量子條件下的對比結果匯總在表1中，結果顯示，當p2-n /3時，基于BHT碰撞搜索算法的量子差分碰撞密鑰恢復攻擊要優于基于Grover搜索的量子差分的直接二次加速.

Table 1 Time Complexity of Key Recovery Under Classical and Quantum Conditions

4 總 結

本文通過對多輪EM分組密碼結構進行分析，研究了經典條件生日碰撞、BHT量子算法和差分密鑰恢復攻擊的結合方法，對多輪EM結構進行了差分碰撞密鑰恢復攻擊，并從量子碰撞算法的角度對其進行量子化.

研究結果表明：經典條件下，當差分傳遞概率2-p≥2-n /2時，r輪EM結構的差分碰撞密鑰恢復攻擊快了2n /2倍；量子條件下，當2-p>2-n /3時，基于BHT碰撞搜索算法的量子差分碰撞密鑰恢復攻擊時間復雜度要優于基于Grover搜索的差分攻擊.結果同時表明，當2-p≤2-n /3時，基于Grover搜索的差分密鑰恢復攻擊的二次加速仍然是最優選擇.