付超輝, 段 明,2, 魏 強, 吳茜瓊, 周 睿,2, 宿恒川,2

1. 信息工程大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院, 鄭州450001

2. 河南省網(wǎng)絡(luò)密碼技術(shù)重點實驗室, 鄭州450001

1 引言

自AlphaGo 誕生以來, 深度學(xué)習(xí)迅猛發(fā)展, 已廣泛應(yīng)用于社會生活的各個領(lǐng)域, 如智能機器人、智能醫(yī)療、智能安防、智能家居、智能交通、智慧城市以及計算機視覺、語音和圖像識別、機器翻譯、自動駕駛、信息推薦等.

2019 年美密會上, Gohr[1]提出深度學(xué)習(xí)用于密碼算法分析的技術(shù), 并對Speck 算法進行了差分攻擊, 對減少數(shù)據(jù)復(fù)雜度有很好的效果. 本文結(jié)合多面體差分的思想[2–4], 利用深度學(xué)習(xí)的方法創(chuàng)新提出了多面體差分神經(jīng)網(wǎng)絡(luò)區(qū)分器. 該區(qū)分器由一個殘差神經(jīng)網(wǎng)絡(luò)構(gòu)成, 可以對特定輸入差分對應(yīng)的輸出密文分布特征進行學(xué)習(xí). 殘差網(wǎng)絡(luò)訓(xùn)練完成后, 可對密文進行預(yù)測, 根據(jù)預(yù)測值即可判斷該密文是否是由特定輸入差分產(chǎn)生. 該多面體差分神經(jīng)網(wǎng)絡(luò)區(qū)分器相對于Gohr 提出的單差分區(qū)分器精度更高, 一定條件下, 利用其進行密鑰恢復(fù)的成功率也有一定提升, 為我們提供了一種在密鑰恢復(fù)成功率和數(shù)據(jù)復(fù)雜度時間復(fù)雜度之間折中的方法.

Simeck 算法是Yang[5]等在CHES 2015 上提出的一種輕量級的分組密碼, 結(jié)合了NSA 在2015 年設(shè)計的Speck 和Simon[6]算法的特征, 從輪函數(shù)上看更像Simon 算法, 從密鑰擴展上看更像Speck 算法. 該算法能夠滿足RFID 設(shè)備低功耗高性能的需求, 且適用于IOT 設(shè)備的安全[7], 可在16 位處理器上高效執(zhí)行[8]. 自提出以來, 出現(xiàn)了大量的針對該算法的攻擊分析, 如差分攻擊[9]、線性攻擊[10]、不可能差分攻擊[5]、積分攻擊[11]、相關(guān)序列攻擊[12]、零相關(guān)線性分析[13]等, 雖然針對該算法的攻擊方法很多,但大多都是理論攻擊, 針對13 輪的Simeck32/64 攻擊, Bagheri[10]給出了實際攻擊結(jié)果, 但數(shù)據(jù)復(fù)雜度和時間復(fù)雜度較高.

我們利用多面體神經(jīng)網(wǎng)絡(luò)區(qū)分器、單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器及兩種區(qū)分器的混合對13 輪Simeck32/64算法進行了密鑰恢復(fù)攻擊, 相對于現(xiàn)有針對該算法的攻擊它們都降低了所需數(shù)據(jù)復(fù)雜度和時間復(fù)雜度,表1 給出了利用兩種區(qū)分器的混合進行密鑰恢復(fù)的結(jié)果, 數(shù)據(jù)復(fù)雜度和時間復(fù)雜度分別為217.7和232.7,與已有的攻擊結(jié)果相比, 復(fù)雜度分別減少為原來的1/212和1/23, 同時我們也給出了利用單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器攻擊的結(jié)果, 結(jié)果顯示在略微降低密鑰恢復(fù)成功率的情況下, 所需數(shù)據(jù)復(fù)雜度和時間復(fù)雜度還可以再次降低. 其中文獻[10] 中給出的是恢復(fù)1 比特密鑰的時間復(fù)雜度, 此處對其進行了換算.

表1 Simeck32/64 算法Table 1 Simeck32/64 algrithm

2 基礎(chǔ)知識

2.1 Simeck 算法

Simeck 是一種輕量級分組密碼, 由Yang[5]等在CHES 2015 提出, 采用Feistel 結(jié)構(gòu), 記為Simeck2n/mn,其中分組大小為2n(n=16,24,32),mn表示密鑰大小. 本文主要研究Simeck32/64,即分組大小為32 比特、密鑰大小為64 比特. 輪函數(shù)可表示為L(i+1)=((Li?5)&Li)⊕(Li?1)⊕Ri⊕Ki,

其單輪函數(shù)迭代結(jié)構(gòu)如圖1 所示.

圖1 Simeck 算法輪函數(shù)迭代結(jié)構(gòu)Figure 1 Architecture of Simeck

2.2 差分分析

假設(shè)F是一個映射,F: (0,1)n →(0,1)m, 一個差分轉(zhuǎn)移是指一對(△in,△out)∈(0,1)n×(0,1)m,其映射F:(0,1)n →(0,1)m的概率稱為差分轉(zhuǎn)移概率, 記作

對于一個簡單的迭代結(jié)構(gòu)的分組密碼, 差分特征是指一個差分轉(zhuǎn)移序列△0,△1,···,△n. 差分區(qū)分器是一個高概率的差分特征. 當(dāng)給定具有某種差分的明文數(shù)據(jù)時, 密文輸出具有非隨機特性, 差分攻擊就是利用這種特性的一種密碼算法分析方法.

當(dāng)給定輸入差分△和加密輪數(shù)r, 綜合使用多個輸出差分特征時, 我們用

2.3 多面體差分分析

傳統(tǒng)的差分密碼分析利用兩個明文在加密時的統(tǒng)計相關(guān)性, 當(dāng)我們對兩個文本在狀態(tài)空間中的絕對位置不感興趣時, 兩個明文之間的差異完全決定了它們的相對位置. 當(dāng)有多個明文時, 選擇其中一個明文作為參照點, 就只需考慮它們相對于參考明文的差值, 據(jù)此Tiessen 在2016 年提出了多面體差分思想, 并在多個密碼分析中得到應(yīng)用[2–4].

例如有d+1 個明文, 可以用d差分的元組來描述它們的相對位置. 通常我們稱(m0,m1,···,md) 為(d+1) 面體, 相應(yīng)的差分(m0⊕m1,m0⊕m2,···,m0⊕md) 為d差分,m0稱為錨定值. 因此, 如果給定一個d差分和錨定值, 我們就可以唯一地確定其相應(yīng)的(d+1) 面體.

多面體密碼分析考慮了明文集在加密時的相互依賴性, 是標(biāo)準(zhǔn)差分密碼分析方法的一個擴展, 是一個通用的方法, 可以包含更高階的差分. 在實際密碼分析中具有一定的實用價值, 可以為我們在時間和數(shù)據(jù)復(fù)雜度之間提供一種折中.

2.4 神經(jīng)網(wǎng)絡(luò)差分區(qū)分器

神經(jīng)網(wǎng)絡(luò)差分區(qū)分器最早由Gohr[1]提出, 由一個殘差神經(jīng)網(wǎng)絡(luò)構(gòu)成. 殘差神經(jīng)網(wǎng)絡(luò)是深度學(xué)習(xí)的模型之一. 利用該網(wǎng)絡(luò), 對給定輸入差分的某算法的輸出差分分布特征進行學(xué)習(xí), 并利用訓(xùn)練的網(wǎng)絡(luò)對給定的密文進行預(yù)測, 看該密文是否符合其輸出差分分布. 區(qū)分器進行預(yù)測時, 利用了輸出差分的分布特征, 這其中很多特征對于傳統(tǒng)的純差分區(qū)分器來說是不可見的, 并且該區(qū)分器在用于密鑰恢復(fù)攻擊時, 大大降低了所需數(shù)據(jù)復(fù)雜度和時間復(fù)雜度. 下文我們將該區(qū)分器簡稱為單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器.

3 基于深度殘差神經(jīng)網(wǎng)絡(luò)的多面體差分區(qū)分器

下文將基于深度殘差神經(jīng)網(wǎng)絡(luò)的多面體差分區(qū)分器簡稱為多面體神經(jīng)網(wǎng)絡(luò)區(qū)分器. 我們從功能的角度對多面體神經(jīng)網(wǎng)絡(luò)區(qū)分器進行一個簡要描述. 多面體神經(jīng)網(wǎng)絡(luò)區(qū)分器的功能類似差分區(qū)分器. 首先, 訓(xùn)練一個多面體神經(jīng)網(wǎng)絡(luò)區(qū)分器. 給定輸入差分為△0,△1,···,△d用形如(P,P ⊕△0,P ⊕△1,···,P ⊕△d)的明文訓(xùn)練一個多面體神經(jīng)網(wǎng)絡(luò)區(qū)分器. 其次, 利用該區(qū)分器進行預(yù)測. 其輸入為由上述明文產(chǎn)生的密文,輸出為Z,Z ∈(0,1), 表示區(qū)分器對密文的預(yù)測值. 一般意義上當(dāng)Z> 0.5 且越接近1 時, 說明該密文是由輸入差分為△0,△1,···,△d的明文產(chǎn)生的. 假定多面體神經(jīng)網(wǎng)絡(luò)區(qū)分器的輸入為n個密文, 密鑰為k,第i個密文應(yīng)的輸出為Zki,Zki ∈(0,1) , 綜合多面體神經(jīng)網(wǎng)絡(luò)區(qū)分器的多個輸出, 可利用

來區(qū)分枚舉密鑰的好壞, 當(dāng)V2值大于一臨界值時, 說明該枚舉密鑰是一個好的密鑰. 數(shù)據(jù)復(fù)雜度與n值相關(guān).

當(dāng)d= 2 時神經(jīng)網(wǎng)絡(luò)區(qū)分器為3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器, 當(dāng)d= 3 時神經(jīng)網(wǎng)絡(luò)區(qū)分器為4 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器, 當(dāng)d=1 時神經(jīng)網(wǎng)絡(luò)區(qū)分器為2 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器, 也是Gohr 提出的單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器. 下文以3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器為例進行說明.

3.1 三面體神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

以3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器為例, 下面直接給出對應(yīng)Simeck32/64 算法我們的最好模型及參數(shù). 深度學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)一般由數(shù)據(jù)預(yù)處理、輸入層、隱藏層和輸出層構(gòu)成, 在數(shù)據(jù)預(yù)處理和輸入層, 將一組具有特定輸入差分的明文記作(P,P ⊕△0,P ⊕△1), 3 個元素共96 比特, 整體看作一個行向量作為網(wǎng)絡(luò)的輸入.隱藏層共十一層, 第一層的初始化使用一維卷積和正則化, 卷積使用32 個filter, 激活函數(shù)使用Sigmoid函數(shù), kernel_size 設(shè)置為1. 隱藏層的其它層全部由一維卷積和正則化構(gòu)成, kernel_size 設(shè)置為3, 其余參數(shù)與隱藏層第一層相同. 輸出層由三層構(gòu)成, 前兩層各有96 個神經(jīng)元, 每層后面都有正則化、矯正層,激活函數(shù)為ReLU 函數(shù), 最后一層有一個神經(jīng)元, 激活函數(shù)為Sigmoid.

3.2 三面體神經(jīng)網(wǎng)絡(luò)區(qū)分器的訓(xùn)練

訓(xùn)練數(shù)據(jù)和驗證數(shù)據(jù)均用隨機數(shù)生成. 三個明文分別記作P0,P1=P0⊕△0,P2=P0⊕△1,P3=(P0⊕Random1),P4=(P0⊕Random2). 此處△0=0x0000/0001,△1=0x0000/0004, Random1和Random2 均為32 比特隨機數(shù). 進行r輪Simeck32/64 算法訓(xùn)練時, 密鑰由隨機數(shù)生成, flag 也由隨機數(shù)生成且flag 屬于集合(0,1). flag=1 時, 神經(jīng)網(wǎng)絡(luò)的一組輸入數(shù)據(jù)為(P0,P1,P2), flag=0 時神經(jīng)網(wǎng)絡(luò)的一組輸入數(shù)據(jù)為(P0,P3,P4) . 訓(xùn)練的集合大小為107, 驗證集合大小為106. 每次訓(xùn)練我們運行50 個epoch, 每個batch 大小為5000, 使用Keras 中默認參數(shù)的Adam 算法對均方誤差損失和基于L2權(quán)重正則化(正則化參數(shù)c= 10?5) 懲罰進行優(yōu)化, 采用循環(huán)學(xué)習(xí)效率調(diào)度. 利用GTX1650 顯卡我們訓(xùn)練了一個8 輪和一個9 輪的3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器, 每個區(qū)分器訓(xùn)練50 個epoch, 一個epoch 大約需要5 分鐘, 結(jié)果如圖2 和圖3 所示.

圖2 N8 三面體神經(jīng)網(wǎng)絡(luò)區(qū)分器精度Figure 2 Accuracy of 8-round 3-polytopic differential neural network distinguisher

圖3 N9 三面體神經(jīng)網(wǎng)絡(luò)區(qū)分器精度Figure 3 Accuracy of a 9-round single differential neural network distinguisher

其中,x軸表示訓(xùn)練的epoch,y軸表示精度, 藍線表示訓(xùn)練精度, 橙線表示預(yù)測精度. 隨著訓(xùn)練周期的增加, 神經(jīng)網(wǎng)絡(luò)區(qū)分器的精度基本穩(wěn)定. 相似的, 我們利用輸入差分△0= 0x0000/0001[9],△0=0x0000/0002, 或△0= 0x0000/0004 等訓(xùn)練了多個8 輪和9 輪的單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器, 結(jié)果如表2 所示, N8 和N9 表示8 輪和9 輪神經(jīng)網(wǎng)絡(luò)區(qū)分器. 通過對比兩種類型的神經(jīng)網(wǎng)絡(luò)區(qū)分器可以發(fā)現(xiàn), 輪數(shù)相同的情況下多面體神經(jīng)網(wǎng)絡(luò)區(qū)分器的預(yù)測精度更高.

表2 單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器和多面體神經(jīng)網(wǎng)絡(luò)區(qū)分器精度對比Table 2 Accuracy comparison between single differential neural network distinguisher and polytopic neural network distinguisher

4 多面體差分神經(jīng)網(wǎng)絡(luò)區(qū)分器的應(yīng)用

在本節(jié)我們將利用 3 面體差分神經(jīng)網(wǎng)絡(luò)區(qū)分器 N9 和單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器 N8 對 13 輪Simeck32/64 進行密鑰恢復(fù)攻擊, 并通過該實例對密鑰恢復(fù)攻擊過程和原理進行說明.

4.1 區(qū)分器擴展

這里主要對13 輪的Simeck32/64 進行最后一輪子密鑰進行攻擊. 攻擊第13 輪時, 將9 輪的3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器擴展為11 輪的區(qū)分器, 添加一個兩輪區(qū)分器, 其差分轉(zhuǎn)移路徑為

(0x0002/0005,0x0008/0014) 為輸入3 面體的2 差分. 其中輸出以約1/16× 1/16 = 1/256 概率為(m0,m0⊕0x0000/0001,m0⊕0x0000/0004) , (0x0000/0001,0x0000/0004) 為輸出3 面體的2 差分. 該2 差分也是我們訓(xùn)練神經(jīng)網(wǎng)絡(luò)時輸入數(shù)據(jù)的差分. 此處, 我們將這樣的3 面體數(shù)據(jù)稱為可用差分結(jié)構(gòu). 一般來說, 可用差分結(jié)構(gòu)是一個d+1 多面體數(shù)據(jù), 它的d差分與訓(xùn)練多面體神經(jīng)網(wǎng)絡(luò)區(qū)分器的d+1 面體數(shù)據(jù)的d差分相同. 之后將添加的兩輪區(qū)分器的輸入解密一輪, 結(jié)果即為選擇明文, 以其作為13 輪加密的輸入, 這樣即可保證選擇明文加密1 輪后, 輸出3 面體的2 差分以概率1 為(0x0002/0005,0x0008/0014),加密3 輪后, 輸出3 面體的2 差分以概率1/256 為(0x0000/0001,0x0000/0004), 即9 輪3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器的輸入2 差分以概率1/256 為(0x0000/0001,0x0000/0004).

9 輪3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器經(jīng)過2 輪擴展后, 其輸入3 面體數(shù)據(jù)的2 差分以約1/256 的概率為(0x0000/0001,0x0000/0004), 為了擴大該概率, 減小數(shù)據(jù)復(fù)雜度, 我們利用了中性位[14]來構(gòu)造明文結(jié)構(gòu).實際上我們在構(gòu)造明文結(jié)構(gòu)時, 利用了中性位比特變化但不改變輸出差分的性質(zhì), 首先選定一個3 面體明文組, 然后對其6 個中性位比特進行變化, 從而擴展出64 個3 面體明文組, 稱其為一個明文結(jié)構(gòu). 13 輪攻擊采用的中性位比特為(0,1,2,3,4,6), 擴展后的64 個3 面體明文組經(jīng)加密后可得到64 個3 面體.

4.2 密鑰恢復(fù)過程

明文結(jié)構(gòu)經(jīng)過13 輪加密后得到相應(yīng)密文結(jié)構(gòu), 猜測最后一輪子密鑰, 并利用候選子密鑰搜索策略給出候選密鑰, 利用這些密鑰解密該密文對組, 得到的結(jié)果作為輸入進入3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器N9, 經(jīng)區(qū)分器和公式(2)計算后得到一組V2值, 將該值和臨界值Cut1比較, 如果大于Cut1, 就將解密最后一輪得到的密文結(jié)構(gòu)用于猜測倒數(shù)第二輪子密鑰. 其過程是, 利用猜測的倒數(shù)第二輪子密鑰解密倒數(shù)第二輪數(shù)據(jù), 得到的結(jié)果形如(m0,m1,m2), 取(m0,m1) 作為輸入進入單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器N8, 經(jīng)區(qū)分器和公式(2)計算出該輪的V2值, 如果該V2值大于臨界值Cut2, 那么用于解密的兩輪子密鑰即是所求.

簡要地說該過程主要分為兩個步驟: 第一步, 搜索最后一輪候選子密鑰; 第二步, 在最后一輪子密鑰確定后, 搜索倒數(shù)第二輪子密鑰. 兩個步驟都利用了輸出密文的差分分布特征. 當(dāng)然, 也可以只利用第一個步驟確定最后一輪子密鑰, 增加第二步是為了更好地確認第一步搜索出的最后一輪子密鑰的正確性. 第二步對于確定最后一輪子密鑰起到了輔助作用.

4.2.1 候選子密鑰搜索策略

最后兩輪候選子密鑰搜索均采用了貝葉斯優(yōu)化方法[15]對密鑰搜索策略進行了改進. 貝葉斯優(yōu)化是一種在不知道函數(shù)方程的情況下, 根據(jù)已有的采樣點求取函數(shù)最大值及其相應(yīng)參數(shù)的方法. 該方法可快速找到函數(shù)最大值, 其包含兩個核心過程: 一個是先驗函數(shù), 先驗函數(shù)主要利用高斯過程回歸, 其求解按貝葉斯推斷進行; 一個是采集函數(shù), 包括UCB (邊探索邊利用) 方法等, 目的是找到最佳樣本集. 在我們的攻擊模型中, 可把區(qū)分器看作一個黑盒函數(shù), 尋找該黑盒函數(shù)的最大值過程即搜索候選子密鑰過程, 首先猜測一個子密鑰, 由該子密鑰解密密文再經(jīng)黑盒函數(shù), 所得結(jié)果求均值方差, 再利用采樣點值經(jīng)貝葉斯推斷即可得出候選子密鑰. 采樣點值可以利用區(qū)分器和樣本集在錯誤密鑰情況下預(yù)計算獲得.

4.2.2 采樣點值計算

圖4 三面體神經(jīng)網(wǎng)絡(luò)區(qū)分器N9 錯誤密鑰均值分布Figure 4 Wrong key response profile of 9-round 3-polytopic differential neural network distinguisher

圖5 單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器N8 錯誤密鑰均值分布Figure 5 Wrong key response profile of 8-round single differential neural network distinguisher

其中, 橫軸表示密鑰差△, 縱軸表示神經(jīng)網(wǎng)絡(luò)區(qū)分器輸出均值. 該采樣點值主要用在貝葉斯推斷中.

4.2.3 候選子密鑰搜索算法

由上述知識為基礎(chǔ), 候選密鑰搜索算法可總結(jié)如算法1 所示. 其中,S為密鑰集合,N為神經(jīng)網(wǎng)絡(luò)區(qū)分器,n為候選密鑰個數(shù),m為密文組個數(shù), count 為貝葉斯優(yōu)化算法迭代次數(shù).

算法1 候選密鑰搜索算法Input: S := {k0,k1,···,kn?1},N,n,m,count Output: S 1 for iter < count do 2 解密1 輪m 個密文對組得到密文組Pi,k, k ∈S;3 用神經(jīng)網(wǎng)絡(luò)區(qū)分器N 預(yù)測Pi,k 得到中間變量Zki;4 Zk i 為輸入利用公式(2)得到中間變量wk;5 對每個密鑰構(gòu)建L = L‖[k,wk];6 對每個密鑰求均值mk = ∑m i=0 Zki/n;7 構(gòu)建中間變量λk = ∑n?1 i=0 (mk ?μ△⊕k)2/σ2△⊕k,k ∈{0,1,···,216 ?1};8 用S 記錄λk 最小的n 個值對應(yīng)的k 作為候選密鑰;9 end

用L保存枚舉的密鑰和計算得出的wk, 其中保存密鑰和wk的個數(shù)為n×count. 如果其中的某個wk超過了臨界值Cut1, 那么我們將該算法擴展倒倒數(shù)第二輪, 如果該輪的wk超過了臨界值Cut2, 那么我們的密鑰搜索就結(jié)束了, 此時便得到了最后兩輪的子密鑰.

在密鑰恢復(fù)攻擊的過程中, 首先對所有的密文結(jié)構(gòu)進行候選密鑰搜索, 如果沒有找到合適的密鑰, 就繼續(xù)主循環(huán)的迭代, 直到找出使得該輪wk> Cut1子密鑰. 算法擴展到倒數(shù)第二輪, 密鑰搜索過程相同,該輪利用的密文結(jié)構(gòu)是由猜測的最后一輪子密鑰解密原始密文數(shù)據(jù)得來. 在這些迭代過程中使用了UCB的方法.

在13 輪的攻擊實驗中我們分別使用了1024 個密文結(jié)構(gòu), 單個密文結(jié)構(gòu)包含64 個3 面體明文對組, UCB 方法的參數(shù)為10, 貝葉斯密鑰搜索迭代次數(shù)為2048, Cut1= 1.0, Cut2= 10.0, 候選密鑰個數(shù)n=32×5=160.

4.3 攻擊結(jié)果及復(fù)雜度估計

在13 輪密鑰恢復(fù)攻擊實驗中, 對100 個密鑰進行了恢復(fù), 統(tǒng)計發(fā)現(xiàn), 共用時17 984 秒, 恢復(fù)一個密鑰平均用時180 秒, 最后1 輪子密鑰完全正確的概率為98%, 倒數(shù)第二輪子密鑰誤差全部在2 比特以內(nèi).

數(shù)據(jù)復(fù)雜度為210×3×64=217.6, 以一次Simeck 運算為單位, 估計時間復(fù)雜度為(l1×1.5+l2)×22×22×217≈232.8, 其中217表示一次候選子密鑰搜索所需時間復(fù)雜度, 兩個22×22×217表示4次候選子密鑰搜索和神經(jīng)網(wǎng)絡(luò)預(yù)測所需時間復(fù)雜度,l1≈1024 表示需進行最后一輪解密的數(shù)據(jù)結(jié)構(gòu)個數(shù),l2≈2095 表示在wk>Cut1的情況下, 進行倒數(shù)第二輪解密的密文結(jié)構(gòu)個數(shù).

4.4 其它輪子密鑰的恢復(fù)

通過上述攻擊過程, 我們可以發(fā)現(xiàn)該攻擊方法的主要計算復(fù)雜度在于, 輸入明文經(jīng)3 輪加密后是以1/256 概率得到我們想要的輸出密文即可用差分結(jié)構(gòu), 該輸出密文再經(jīng)神經(jīng)網(wǎng)絡(luò)區(qū)分器、候選密鑰搜索等過程最終找到正確密鑰. 在未知哪一個明文輸入能得到可用差分結(jié)構(gòu)時, 我們只能將所有的輸入明文結(jié)構(gòu)枚舉. 但是, 在最后一輪子密鑰搜索完成后, 就可以得到一個輸入明文結(jié)構(gòu)其對應(yīng)的3 輪加密輸出為可用差分結(jié)構(gòu), 以及一個完全正確的最后一輪子密鑰. 利用此明文結(jié)構(gòu)即可以常數(shù)時間恢復(fù)其它各輪子密鑰,從而得到初始完整密鑰.

5 密鑰恢復(fù)效率對比分析

本節(jié)我們主要討論多面體差分相對于單差分帶來的精度提高, 在密鑰恢復(fù)效率上的具體體現(xiàn). 主要以3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器和單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器的應(yīng)用作對比. 同時也涉及到了3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器和單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器的混合使用, 即密鑰恢復(fù)攻擊的第一步使用3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器, 第二步使用單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器.

單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器的訓(xùn)練已由第3 節(jié)給出, 下文我們將直接給出單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器進行密鑰恢復(fù)的結(jié)果. 另使用單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器時, 該區(qū)分器由9 輪擴展為11 輪需添加的兩輪差分特征為(0x0002/0005,0x0000/0001), 得到一個可用差分結(jié)構(gòu)的概率約為1/16. 3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器由9 輪擴展為11 輪時, 得到一個可用差分結(jié)構(gòu)的概率約為1/256. 本節(jié)表格中涉及到的概率即為得到可用差分結(jié)構(gòu)的概率.

5.1 無概率攻擊實驗

在該實驗中, 我們將2 差分為(0x0000/0001,0x0000/0x0004) 的3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器與單差分為0x0000/0002 的神經(jīng)網(wǎng)絡(luò)區(qū)分器進行對比. 密鑰恢復(fù)攻擊的輪數(shù)為10 輪. 多面體差分攻擊的兩個步驟使用3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器N9 和N8, 單差分攻擊的兩個步驟使用單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器N9 和N8. 因輪數(shù)為10 輪, 故不需考慮由輸入明文到可用差分結(jié)構(gòu)的概率. 結(jié)果如表3 所示.

表3 無概率條件下單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器和三面體神經(jīng)網(wǎng)絡(luò)區(qū)分器密鑰恢復(fù)精度對比Table 3 Comparison of key recovery accuracy between single differential neural network distinguisher and polytopic differential neural network distinguisher without probability

通過該實驗我們確認了高精度的3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器在密鑰恢復(fù)攻擊中, 效果要好于精度低的單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器. 另外, 該結(jié)果也與采用UCB 方法時的主循環(huán)次數(shù)相關(guān), 一般意義上主循環(huán)次數(shù)越大越高密鑰恢復(fù)成功率越高, 但計算復(fù)雜度也越大, 此處主循環(huán)次數(shù)為50.

5.2 簡化密鑰攻擊過程實驗

在本實驗中, 我們僅使用密鑰攻擊過程的第一步進行密鑰恢復(fù), 也即僅利用Cut1值進行密鑰恢復(fù).首先猜測一個最后一輪密鑰, 解密一組密文數(shù)據(jù), 然后用3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器N9 和單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器N9 分別去預(yù)測, 給出該組密文數(shù)據(jù)的預(yù)測值分布, 最后利用貝葉斯優(yōu)化方法搜索候選子密鑰, 當(dāng)wk>Cut1時, 認為該密鑰為最終密鑰. 兩種區(qū)分器所得結(jié)果如表4.

表4 單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器和三面體神經(jīng)網(wǎng)絡(luò)區(qū)分器密鑰恢復(fù)精度對比Table 4 Comparison of key recovery accuracy between single differential neural network distinguisher and polytopic differential neural network distinguisher

數(shù)據(jù)結(jié)構(gòu)個數(shù)取512 和32 是為了保證可用差分結(jié)構(gòu)個數(shù)約為2. 主循環(huán)次數(shù)分別為128 和1024. 通過對比發(fā)現(xiàn), 在僅用Cut1值進行密鑰恢復(fù)時, 單差分區(qū)分器幾乎很難將正確密鑰篩選出來, 3 面體區(qū)分器在數(shù)據(jù)復(fù)雜度和計算復(fù)雜度一定增加的情況下, 可以以30% 的比例正確恢復(fù)密鑰. 其原因是3 面體對數(shù)據(jù)條件的要求更為嚴格, 區(qū)分器精度更高.

在無概率攻擊實驗和簡化密鑰攻擊過程實驗中, 我們都直接指定了進入兩種神經(jīng)網(wǎng)絡(luò)區(qū)分器的可用差分結(jié)構(gòu)個數(shù), 但是在實際攻擊中, 我們需要考慮得到可用差分結(jié)構(gòu)個數(shù)的概率, 此概率直接影響實際攻擊的數(shù)據(jù)復(fù)雜度.

5.3 多面體和單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器密鑰恢復(fù)效果對比

為了對比單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器和3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器精度對密鑰恢復(fù)的影響,我們利用兩種神經(jīng)網(wǎng)絡(luò)區(qū)分器進行了13 輪密鑰恢復(fù)攻擊. 三面體差分密鑰恢復(fù)攻擊采用3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器N9 和N8.單差分密鑰恢復(fù)攻擊采用單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器N9 和N8. 單差分攻擊取20 個明文結(jié)構(gòu), 3 面體攻擊取320 個明文結(jié)構(gòu), 即能夠基本保證有一個可用差分結(jié)構(gòu). 主循環(huán)次數(shù)采用數(shù)據(jù)結(jié)構(gòu)數(shù)的4 倍. 3 面體差分13 輪密鑰恢復(fù)攻擊時,數(shù)據(jù)復(fù)雜度為28.5×3×64 ≈215.9,估計時間復(fù)雜度為(l1+l2)×22×22×217≈227.3,其中,l1≈20,l2≈66. 3 面體差分13 輪密鑰恢復(fù)攻擊時, 數(shù)據(jù)復(fù)雜度為28.5×3×64 ≈215.9, 估計時間復(fù)雜度為(l1+l2)×1.5×22×22×217≈231.4, 其中,l1≈315,l2≈549.

在該實驗的基礎(chǔ)上將數(shù)據(jù)結(jié)構(gòu)個數(shù)增加, 結(jié)果如表5. 通過對比可見, 在數(shù)據(jù)復(fù)雜度和時間復(fù)雜度一定增加的情況下, 采用多面體神經(jīng)網(wǎng)絡(luò)區(qū)分器提高密鑰恢復(fù)成功率的效果有限.

表5 神經(jīng)網(wǎng)絡(luò)區(qū)分器不同使用方式密鑰恢復(fù)效果對比Table 5 Key recovery accuracy comparison of neural network distinguisher using different methods

5.4 混合使用多面體和單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器

上一個實驗中, 3 面體攻擊的兩個步驟均使用3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器, 本實驗中, 3 面體攻擊的第一步使用3 面體神經(jīng)網(wǎng)絡(luò)區(qū)分器N9, 第二步使用單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器N8. 主循環(huán)次數(shù)采用數(shù)據(jù)結(jié)構(gòu)次數(shù)的4 倍. 用“3 面體/單差分” 表示3 面體和單差分的混合, 在第4 節(jié)實驗基礎(chǔ)上, 增加其它數(shù)據(jù)結(jié)構(gòu)數(shù)目, 結(jié)果如表5.

由對比可知, 在可用差分結(jié)構(gòu)數(shù)目相近的情況下, 混合使用3 面體差分區(qū)分器和單差分區(qū)分器, 可以使密鑰恢復(fù)成功率相較于單差分區(qū)分器有一定提高, 但相應(yīng)數(shù)據(jù)復(fù)雜度和計算復(fù)雜度也有增加.

6 結(jié)束語

本文主要提出了基于深度學(xué)習(xí)的多面體差分攻擊方法, 并通過對Simeck32/64 算法的實際密鑰恢復(fù)攻擊, 說明了多面體差分攻擊方法的應(yīng)用及效果. 在實際密鑰恢復(fù)攻擊過程中, 我們使用了多面體神經(jīng)網(wǎng)絡(luò)區(qū)分器、單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器以及兩種區(qū)分器的混合. 與傳統(tǒng)差分攻擊方式相比, 三種攻擊方式均可降低數(shù)據(jù)復(fù)雜度和時間復(fù)雜度. 同時, 相對于單差分神經(jīng)網(wǎng)絡(luò)區(qū)分器, 多面體差分神經(jīng)網(wǎng)絡(luò)區(qū)分器進行密鑰恢復(fù)的成功率略好, 但所需數(shù)據(jù)復(fù)雜度和計算復(fù)雜度較高, 在兩種區(qū)分器混合使用的情況下密鑰恢復(fù)成功率和數(shù)據(jù)時間復(fù)雜度取得了較好平衡. 最后, 雖然這幾種神經(jīng)網(wǎng)絡(luò)區(qū)分器及其應(yīng)用方式都具有一定的局限性, 如攻擊多輪算法時區(qū)分器精度不高等, 但是作為一種新的密碼分析工具, 值得我們繼續(xù)探索.