基于深度學習的SIMON32/64安全性分析

王慧嬌 叢 鵬 蔣 華 韋永壯

(廣西可信軟件重點實驗室(桂林電子科技大學) 廣西桂林 541004)

近年來，伴隨無線傳感器網絡以及射頻識別技術的發展和廣泛應用，對資源受限的設備進行數據加密需要使用輕量級的密碼算法.然而輕量級的密碼算法追求低消耗與高效率，必然會導致安全性的降低，針對這一問題目前還沒有公認的設計準則與安全標準，因此有必要對這些輕量級算法的安全性進行分析.

一個輕量級分組密碼的分析關鍵在于構造一個有效的區分器，即根據密碼算法的結構或其組件的特征將原密碼算法和隨機置換進行區分.差分區分器是迄今已知的攻擊分組密碼最有利的工具之一，由Biham等人[1]首次提出，該工具利用了分組密碼算法在迭代過程中存在不平衡的差分統計量分布.輕量級分組密碼在設計之初會充分考慮抵御差分密碼分析和線性密碼分析.如何發現未知的算法缺陷，設計新型區分器是一個新的研究方向.人工智能的飛速發展與深度學習技術的進步息息相關，在計算機視覺[2]、自然語言處理[3]、生物信息[4]等領域深度學習具有廣泛的應用.深度學習是一種從數據當中發現復雜規律，并且利用規律對未來時刻、未知狀況進行預測和判定的方法，因此深度學習在解決密碼學問題上具有潛在的優勢.

就密碼學而言，深度學習主要應用于側信道分析[5]，對深度學習技術在經典密碼分析的適用性上沒有進行過多探討.Abadi等人[6]認為神經網絡通常意味著并不擅長密碼學，簡單的感知機甚至無法對異或運算進行區分，而這恰恰是許多密碼算法的基礎.Rivest[7]則評價了深度學習與密碼學之間的多種聯系，提出了使用深度學習應用于密碼分析中的一些可能的研究方向.Hu等人[8]開發了一種前饋神經網絡(feedforward neural network, FNN)，該網絡可以從AES密碼的密文中發現明文，而無需使用密鑰信息.Gohr[9]在2019年美密會上提出了基于深度學習的減輪SPECK32/64改進差分攻擊，通過訓練卷積殘差神經網絡用以區分固定明文差分加密的密文對和隨機數據并以此構造區分器，證明了深度學習在對稱密碼上攻擊的有效性和研究方向.Baksi等人[10]延續Gohr的工作并借鑒文獻[11]的思想利用神經網絡構造多合一差分區分器應用于非馬爾可夫密碼GIMLI. Yadav等人[12]將差分區分器和深度學習技術結合，對經典差分區分器設計了基于深度學習的通用擴展，使區分器具有更多的輪數且需要更少的數據復雜度.Bellini等人[13]采用多層感知機和卷積神經網絡(convolutional neural network, CNN)來構造減輪TEA和RAIDEN算法的神經網絡區分器，并提出了傳統區分器無法應用的場合以及該方法的局限性.Jain等人[14]對輕量級密碼算法PRESENT構造3～6的神經網絡區分器，該區分器能夠將密碼數據和隨機數據以極高的概率區分開，進一步拓展了深度學習在分組密碼的工作.So[15]嘗試利用深度學習對簡化版本的DES，SPECK和SIMON在基于密鑰空間受限下的全輪攻擊，成功發現了明/密文對和密鑰之間的線性近似，但在密鑰空間不受限制的條件下，該方法并不適用.

2013年輕量級分組密碼SIMON[16]一經發布，便受到了廣泛的關注.最初由Abed等人[17]采用傳統差分分析獲得了SIMON算法在各種分組長度下的高概率差分特征.Biryukov等人[18]在FSE’14對自動化搜索算法尋找差分路徑進行改進，提出了基于ARX(addition rotation exclusive-or)密碼的閾值搜索技術.該方法能夠更有效地利用密碼算法的強差分效應，進一步改善了SIMON類算法的最佳差分.K?lbl等人[19]在2015年美密會上提出關于SIMON系列密碼的差分和線性分布特征，采用自動化搜索技術SAT/STM尋找最佳的差分和線性特征，并研究了在不同輪數下SIMON算法抵抗攻擊的能力.但是這類方法在構造區分器的過程中數據復雜度和時間復雜度相對較高.如何針對SIMON算法構建更加智能化、便捷化的深度學習區分器有待進一步去解決.

本文借鑒差分密碼分析的攻擊思想，通過深度學習發現輕量級分組密碼在迭代過程中存在的差分不均勻性，提出了基于深度學習的減輪SIMON32/64的區分器模型，該區分器可以將密碼算法和隨機數據以極高的概率區分開.這是對SIMON算法安全性分析的全新思路，相較于傳統的區分器具有更強的通用性和可實現性.該方案采用FNN和CNN深度學習算法來構造區分器，討論了在相同環境下2種模型各自具有的優勢.進一步通過對FNN和CNN區分器進行結合構造混合區分器，在保持模型的相對精度下，增加個體間的差異，提高區分器的泛化能力.通過實驗結果證明，混合區分器在進行侯選密鑰的篩選任務時能夠以相對較高的概率將真實子密鑰的范圍確定在一個三者最小的集合中.與文獻[18-19]相比，本文提出的深度學習區分器具有較好的性能，詳細的9輪攻擊復雜度對比如表1所示：

Table 1 Comparison of 9 Rounds of Attack Complexity for SIMON32/64

1 預備知識

1.1 SIMON算法

輕量級分組密碼SIMON[16]基于平衡Feistel結構，其設計上只使用了簡單的與運算、異或運算、移位運算，特別適用于物聯網設備當中.其可選擇的分組長度為2n，其中，n取值為16,24,32,48,64，主密鑰長度為n×m，其中，m取值為2,3,4，設計者基于不同n和m以及迭代輪數給出了SIMON算法的多個版本.其非線性變換為

F(x)=(x<<1) & (x<<8)⊕(x<<2).

(1)

假設其輸入為(Li,Ri)，子密鑰為ki，經過1輪加密后其輸出為

(2)

圖1為SIMON的1輪迭代變換結構，其中<<為左移運算符、&為與運算符、⊕為異或運算符.

Fig. 1 Process of SIMON single round encryption圖1 SIMON單輪加密過程

1.2 前饋神經網絡與卷積神經網絡

FNN和CNN在設計上具有相似性同時也存在差異，因此對數據集進行處理的過程中會有不同的敏感偏好.

Fig. 2 Model of feedforward neural network distinguisher圖2 前饋神經網絡區分器模型

Fig. 3 Model of convolutional neural network distinguisher圖3 卷積神經網絡區分器模型

CNN是一種特殊結構的FNN，能夠接受矩陣作為輸入，具有跨空間(圖像等)或跨時間(音頻信號等)的重復神經元塊(卷積核)，這種特殊的設計結構使得CNN具有部分平移不變性.圖3給出了CNN區分器的模型，其中輸入層可由密文對(C0,C1)靈活設置其矩陣的尺寸.

以截斷差分區分器為例：算法只考慮差分的一部分性質，比如，差分落在某個集合中以及差分的某個比特位為0.對于不同的數據集這些差分集合以及其中的某比特可以落在空間中的任意位置，假如要像FNN一樣在每個空間位置學習獨立的權重，訓練數據需要多出幾個數量級.簡單地說，對于沒有跨空間重復權重的FNN，連接到輸入矩陣左上方的輸入神經元組不得不獨立于連接到輸入矩陣右下方的輸入神經元組來學習表示某個差分集合或某個比特位.因此需要足夠多的訓練樣本，才能夠讓FNN學習到某些差分集合在各個可能位置.

2 基于深度學習的區分器設計

本節采用1.2節中的2種深度學習模型來構建深度學習區分器，給出了深度學習區分器的構建方法和實現過程，以及如何利用該區分器進行候選密鑰篩選.

2.1 區分器的設計

輕量級分組密碼在迭代輪數低的情況下，明文中的統計規律和結構特征沒有完全隱藏在密文當中，本文期望通過深度學習發現這種隱含的特征，從而將密文對和隨機數據區分開，進而篩選出具有高概率差分特點并且隱含了密鑰信息的密文對.對此本文選取了2種網絡結構模型：FNN和CNN，通過靈活調節超參數，使其達到最優的性能.一方面是為了驗證2種神經網絡結構對于加密數據的敏感度；另一方面通過結合2種神經網絡區分器進行候選密鑰篩選，得到更好的結果.

深度學習技術能夠揭示數據中的隱藏結構而無需顯式標注其特征，借鑒差分密碼分析中尋找多條差分特征的思想將其轉化為深度學習的分類問題，采用2階段策略構造深度學習區分器：

1) 離線階段

離線階段是對神經網絡進行2分類學習，訓練集與驗證集由密文對和隨機數據組成.密文對來自于固定明文差分通過不同密鑰加密r輪生成.

2) 在線階段

在線階段是通過神經網絡進行預測.測試集來自于固定明文差分采用統一密鑰進行加密r輪生成的密文對.確定區分器閾值δ，當測試樣本預測值大于δ時將其歸類為正例，否則歸類為負例.

算法1.離線階段.

輸入：樣本數量n、明文差分Δx；

輸出：訓練成功的網絡模型model.

①TD←?; /*初始訓練集為空*/

②P0,K←Random;P1←P0⊕Δx;

③C0←encrypt(P0,k);C1←encrypt(P1,k);

④ fori∈{1,n} do /*設置樣本集標簽*/

⑥Ci←Random;

⑦Yi←0;

⑧ else

⑨Yi←1;

⑩ end if

算法2.在線階段.

輸入：樣本數量n、明文差分Δx、閾值δ、模型model；

輸出：隱藏密鑰信息且具有高概率差分密文對.

①TD′←?; /*初始測試集為空*/

②P0←Random;P1←P0⊕Δx;

③C0←encrypt(P0,k); /*唯一密鑰加密*/

④C1←encrypt(P1,k);

⑤TD′←X(C0,C1);

⑥ fori∈{1,n} do

⑨ else

2.2 神經網絡的設置

為了保留密文對的統計信息以及神經網絡模型能夠順利收斂到一個局部最優解，分別對輸入輸出格式、激活函數、部分超參數進行設置.

2) 基于不同的數據集和應用場景神經網絡在訓練過程中采取不同的非線性激活函數：sigmoid函數是1個logistic函數,表示為不管輸入是什么得到的輸出被約束在0～1之間.本文中的神經網絡模型只有1個輸出神經元，因此將其應用于輸出層,其函數表達式為

(3)

ReLU函數應用于輪數比較低的區分器訓練當中，減少了梯度消失的可能性，其函數表達式為

ReLU(x)=max(0,x).

(4)

當對輪數比較高的區分器進行訓練時，由于數據集當中的密文對和隨機數據沒有出現明顯的差異性，因此往往在訓練過程中產生梯度爆炸的情況，訓練模型存在向2個方向傾斜的可能，基于此本文選擇了tanh函數，其函數表達式為

(5)

3) 超參數設置.損失函數設置為其均方誤差

(6)

同時為了防止出現過擬合現象，對均方誤差采用L2范數最小化結構風險.每批次(batch)訓練數據為213，優化器采用Adam算法，學習率隨訓練輪數不斷下降，經過20個回合(epoch)后不再降低，所以，算法中訓練周期設置為20個epoch.其間通過回調函數觸發ModelCheckPoint方法保存最佳的學習模型.

2.3 候選密鑰篩選方案

采用上述算法獲得了一個r-1輪深度學習區分器，對一個r輪加密算法，其攻擊步驟為：

1) 均勻隨機的選取明文P0，令P1=P0⊕Δx，在同一密鑰k(k∈k1,k2…,kr)下加密，獲得相應密文對(C0,C1).

2) 對(C0,C1)利用其r輪中所有存在的候選密鑰進行1輪“解密”，得到其r-1輪密文對(σ0,σ1).

(7)

其中,α,β由FNN和CNN區分器的準確率分配.

4) 進一步統計每一個候選密鑰來自于解密后的得分

vk

(8)

通過vk對所有候選密鑰進行排名.算法3對步驟1)～4)進行了闡述.

算法3.候選密鑰篩選.

輸入：選擇明文差分加密r輪的密文對(C0,C1)、r-1輪深度學習區分器modelFNN,modelCNN；

輸出：候選密鑰排名.

① fori∈{1,n} do /*n為候選子密鑰數量*/

②σ0←decryptOneRound(C0,ki);

③σ1←decryptOneRound(C1,ki);

⑦vk←finalGrade(δk);

⑧ end for

⑨descendingSort(vk). /*降序排列*/

3 實驗結果與分析

本節主要給出了深度學習區分器在訓練階段和測試階段的實驗結果，并展示了通過深度學習區分器在對SIMON32/64的9輪攻擊中呈現的效果.所有實驗平臺其硬件環境為處理器：Intel?CoreTMi7-7700，內存：8.00 GB.深度學習庫：后端Tensorflow，前端Keras，采用CPU進行計算實現.

3.1 離線階段實驗

選擇明文差分Δx=0x0040/0000，通過第2節的算法1生成220個訓練集樣本，217個驗證集樣本，正負樣本的數量各占其中的1/2.圖4給出了基于6輪FNN在20個回合的訓練情況：

Fig. 4 Performance measurement of SIMON 6-round neural network differentiator圖4 SIMON的6輪神經網絡區分器的性能度量

損失曲線能夠反映模型的學習率變化和函數的收斂情況，在圖4(a)中，由于初始時學習率設置較大，損失值下降很快.隨著迭代學習率不斷得到調整，模型的訓練精度增加，損失曲線也逐漸趨于穩定.其后面epoch驗證集的曲線變化有向低性能過渡的趨勢，反映出模型存在輕微的過擬合現象.查全率表示被預測正確的正例樣本占總正例樣本的比例，衡量了區分器對正例的識別能力.其20個epoch的查全率變化如圖4(b)所示，反映該模型能夠比較全面地選擇出更多的密文對，從而能夠尋找出更多的高概率差分.AUC(area under curve)反映了模型對樣本的排序能力，它能夠直觀地展示一個模型的好壞.圖4(c)展示了在第6個epoch后AUC的值開始接近于1，說明采用Δx=0x0040/0000為初始差分經過6輪迭代后生成的密文對與隨機數據之間存在較大的差別，神經網絡能夠輕易地提取到這種數據間差異.綜上說明這是一個近乎完美的6輪區分器.

表2列出了FNN和CNN在6～9輪區分器的學習參數、訓練時間和準確率.可以看出CNN能夠更好的收斂到一個局部最小值，更容易被優化.但相應的由于FNN結構簡單，訓練時間將大大降低，準確率上略遜于CNN.

Table 2 Comparison of SIMON32/64 6～9 Rounds FNN and CNN

圖5展示了6～9輪區分器訓練過程中驗證集準確率的變化，表明深度學習區分器對低輪的SIMON算法輕松的學習到了加密數據和隨機數據的區分，但隨著其迭代輪數的增加，準確率會不斷降低.其本質原因在于根據密碼算法的混淆和擴散原則，其迭代輪數越高，明密文之間的統計信息越弱，相應的正負樣本相似性很高，使深度學習難以進行有效的特征選擇.為了使8，9輪的區分器有更強的泛化能力，通過增加訓練集和驗證集的數據量、延長訓練epoch，2種神經網絡模型都獲得了不同程度的提升，CNN相比于FNN提升效果更加明顯.

Fig. 5 Comparison of the accuracy in verification set of SIMON 6～9 rounds FNN and CNN圖5 SIMON的6～9輪FNN與CNN驗證集準確率對比

3.2 在線階段實驗

對2種神經網絡模型6～9輪進行測試，采用選擇明文差分為Δx=0x0040/0000，定義閾值δ>0.5.為了防止可能存在的密鑰依賴，每一輪采用1 000個密文對作為數據集，循環1 000次，總計100萬個數據集.表3給出了2種神經網絡模型6～9輪的預測結果，可以看出2種模型在6，7輪都具有可信的準確率，同時證明該模型具有良好的泛化能力.在8，9輪中，CNN在預測上具有一定的參考意義，基于9輪的FNN幾乎沒有學到任何東西.圖6給出了6輪CNN區分器對300個隨機正樣本的預測分布.可以看出我們的6輪CNN區分器在預測值的分布上具有較高的可信度，能夠容易地找到具有高概率差分的密文對.

Fig. 6 Prediction results of SIMON 6 rounds of convolutional neural network圖6 SIMON的6輪卷積神經網絡預測結果

Table 3 Test Set Accuracy of Deep Learning Distinguisher表3 深度學習區分器測試集準度

3.3 候選密鑰篩選結果

訓練集包含220個樣本，驗證集包含217個樣本，每批次采用213樣本，訓練epoch為20輪.模型初始學習率為0.02，每輪遞減5E-4，經過20個epoch后學習率為0.01.最終得到了基于FNN和CNN的最佳學習模型.故其每個區分器的離線復雜度為220+217=220.170(加密次數).

利用算法1構造了一個7輪的深度學習區分器.采用128個輸入差分為Δx=0x0040/0000的已知明文對，基于SIMON32/64的自身性質，對其無損失的向上擴展1輪，最后通過真實密鑰加密至9輪.

利用算法3對9輪SIMON32/64的65,535個候選密鑰進行篩選.采用27個選擇明密文對，該攻擊的時間復雜度為220.170+27×216=223.000(加密次數)，混合區分器的攻擊時間復雜度為220.170×2+27×216=223.358(加密次數).

通過對FNN和CNN以及兩者結合的混合區分器進行實驗，表4給出了以真實密鑰為分界線，高于真實密鑰成績的候選密鑰數量.篩選出的候選密鑰數量越少，表明所設計的區分器越有效.候選密鑰成績的平均取值范圍在-537.107～-500.221之間.

Table 4 The Number of Candidate Keys and the Actual Key Scores

3.4 深度學習區分器與傳統區分器的比較

采用STA/STM方法K?lbl等人[19]給出了減輪SIMON32/64的16輪差分軌跡，其中6～9輪的差分軌跡的轉移概率分別為2-12,2-14,2-18,2-20，相應所需的數據復雜度和存儲復雜度至少分別需要212，214，218，220.采用深度學習構造的區分器在9輪攻擊中數據復雜度僅為27+1，FNN和CNN以及兩者結合的混合區分器存儲復雜度分別為210.115，29.760和29.399.表1對文獻[18-19]和深度學習區分器所需的數據復雜度、時間復雜度和存儲復雜度進行了總結，可以反映出深度學習區分器在這些度量標準上都具有明顯的優勢，采用FNN和CNN結合的候選密鑰篩選方案能夠將存儲復雜度有效降低.

4 總結與展望

本文分別基于FNN和CNN 2種深度學習模型對減輪SIMON32/64的安全性進行了分析.實驗結果發現：CNN構造的區分器在準確率上要優于FNN；對于6，7輪的SIMON32/64該區分器都能夠以很高的概率將密文對和隨機數據區分開；在利用FNN和CNN區分器共同參與的候選密鑰篩選策略中，不但成功縮減了候選密鑰可能的范圍，而且有效降低了攻擊復雜度、數據復雜度及時間復雜度.這也進一步說明了通過結合神經網絡和差分對一些輕量級分組密碼進行安全性分析是一個可行的手段.另一方面，能否利用機器學習中的其他算法來構建分組密碼的新型區分器，有待進一步研究.