基于模板和KNN算法的能量分析攻擊對比研究

靳濟方，劉承遠，范曉紅，段曉毅，劉嘉瑜

（北京電子科技學院電子與通信工程系，北京 100070）

0 引言

隨著移動通信過程中對信息安全需求的提高，通信終端設備通常采用加密的安全芯片（如手機SIM卡等）保證用戶身份認證信息的硬件安全。但隨著技術的發展，密碼芯片的安全性面臨著威脅，其中最大的威脅來自功耗分析攻擊。它通過采集密碼芯片工作時的能量跡，利用統計分析等手段猜測密碼算法的密鑰，對終端密碼設備的安全構成了極大的威脅。

1999年，Paul和Joshua等[1]提出了差分能量分析（differential power analysis，DPA）恢復DES（data encryption standard）的密鑰。2003年，Chari等[2]通過采集大量能量跡樣本建立統計信息，利用模板攻擊（template attack，TA）獲取密鑰。2004年，Rechberger和Oswald對模板攻擊方法的實際問題進行討論，并分析了特征點數量對攻擊成功率的影響，提出使用差分能量分析攻擊尋找特征點的方法[4]。2006年，Archambeau等[5]提出從側信道信息中選取特征點構成樣本的主子空間（principal subspace），以減少模板攻擊的運算量。2011年，Gabrielet等[8]首次將機器學習技術應用到側信道攻擊中，利用具有明顯漢明重量泄露的數據集進行功率分析攻擊，利用最小二乘支持向量機（LS-SVM）成功攻擊了一些高級加密標準（advanced encryption standard，AES）的軟件實現。2013年，Lerman等[9]提出一種半監督的模板攻擊方法，這一方法放松了模板攻擊中必須完全掌握被攻擊設備的限制。可見，模板攻擊和基于機器學習的KNN算法的能量分析攻擊日益成為能量分析攻擊具有威脅的攻擊手段。2019年，Kim等[10]介紹了一種使用卷積神經網絡分析側通道的方法。馬向亮[11]使用基于能量分析技術分析芯片后門指令，Ryad等[12]使用CNN攻擊了有掩碼、擾亂防御的基于單片機上的算法實現，文獻[13]利用CNN對單片機上的算法實現進行了掩碼和抗干擾攻擊。2020年，Cai等[14]提出了差分功率分析攻擊的能量曲線壓縮方法，段曉毅等[15]使用數據增強技術解決了機器學習中SBOX（substitution box）輸出值的漢明重量不平衡問題。

本文對基于TA和KNN算法的能量分析攻擊進行了對比研究。在對皮爾遜相關系數（Pearson correlation coefficient，PCC）、互信息和最大信息系數（maximal information coefficient，MIC）、距離相關系數（distance correlation coefficient，dcorr）3種降維方法研究的基礎上，選出適合兩種能量分析攻擊的特征點，進一步研究特征點數量p對兩種能量分析方法的攻擊成功率以及3種降維方法對兩種能量分析方法的攻擊成功率的影響等。

1 能量分析攻擊

1.1 基于模板的能量分析攻擊

TA過程主要可以分為兩個階段：第一階段為建立模板階段，第二階段為模板匹配階段。最常用的模板攻擊模型是多元高斯模型。

其中，建立模板階段，構建的模板實際是一個二元組T=，由同一時刻該點的電壓均值t和計算不同點的協方差矩陣C組成。分為如下3步。

第一步：對L位密鑰的2L種可能密鑰進行建模。

第二步：每一種可能密鑰對同一個明文進行m次加密，得到m條能量/電磁曲線，然后在每條曲線上尋找n個與密鑰相關的特征點。計算這n個點的平均值，得到t，如式（1）所示。

第三步：計算不同點的協方差。協方差是構建不同點的相關性，如式（2）所示。

模板匹配階段是利用極大似然法則，計算能量跡t與模板匹配的概率，概率最大的是匹配最好的模板，對應的密鑰是最可能的正確密鑰。其概率計算式如式（3）所示。

1.2 基于KNN算法的能量分析攻擊

KNN作為監督學習中一種分類算法，該算法的中心思想為：若某樣本在特征空間中的k個最近鄰樣本多數屬于某一個類別，則該樣本屬于這個類別。KNN算法原理如圖1所示。

圖1 算法原理

KNN算法的完整步驟如下：

· 計算測試數據與各個訓練數據之間的距離；

· 按照距離的遞增關系進行排序；

· 選取距離最小的k個點；

· 確定前k個點所在類別的出現頻率；

· 返回前k個點中出現頻率最高的類別作為測試數據的預測分類。

其中，k值的選擇對訓練模型的擬合效果至關重要。k值過大或過小會造成訓練模型過擬合或欠擬合。因此，為了解決這個問題，一開始可以先選擇一個較小的k值，然后再使用交叉驗證的方法最終得到一個適合模型的終值。

KNN在各類開發庫中應用廣泛。Python3.8 Scikit-Learn機器學習庫中的KNN算法函數是此類庫函數中一個經典的例子。本文中，該函數輸入為測試集功耗曲線以及對應的類標簽（即AES-256算法的字節代替環節第一個SBOX輸出漢明重量值），輸出則為具有分類功能的模型（函數默認近鄰數量k=5，距離默認歐氏距離p=2）。再將測試集功耗曲線給到該模型進行分類預測。在測試過程中，最后需要將上述得到的漢明重量值與測試集數據實際對應的標簽值進行對比，以得到基于KNN算法進行能量分析攻擊時的攻擊成功率。

2 降維技術的原理及實現

進行能量分析攻擊的第一步是將龐雜的能量數據進行降維，去除噪聲，將攻擊對象（密鑰等敏感數據）有關的點保留，即進行特征點選擇。

2.1 特征點選擇

目前使用機器學習應用于能量分析攻擊是能量分析攻擊的一個研究熱點，而特征點選擇是影響機器學習模型的一個重要因素，當輸入數據的特征點數較大時，數據的冗余會造成訓練結果差；當輸入數據特征點數較小時，小的特征子集不能滿足訓練算法的需求，從而引起過擬合現象，導致模型誤差變大。因此，攻擊者在進行模板攻擊前，會對功耗曲線上的特征點進行篩選，選出與關鍵數據相關性高的點，把區分度不夠的點排除，以此提高輸入數據的優質程度。要評估相關性，需要引入統計學中的概念和統計量衡量。本文將分別使用3種常用的特征點選擇方法：PCC、MIC和Dcorr對輸入數據進行優化。

2.2 3種降維技術原理

2.2.1 皮爾遜相關系數

PCC是實現分析特征以及響應變量間關系的一種方法，其實現簡單且計算效率較高，能有效衡量各個變量間的線性相關性，結果的取值區間為[?1，1]，?1表示完全的負相關，1表示完全的正相關，0表示沒有線性相關。

PCC計算式如式（4）所示。

其中，X、Y是變量的值，N為樣本數。

2.2.2 互信息和最大信息系數

一般來說，互信息（MI）是指隨機變量X與Y在計算時產生的交互信息，其中用I(X;Y)表示各個事件間互信息，如式（5）所示。

可以通過分析互信息檢測定性因變量與自變量間的相關性。但互信息在應用于特征選擇時具有一定的缺陷。若計算一組連續的變量，就必須先將變量離散化，但將變量離散處理，互信息的結果就會受到一定影響，出現計算誤差。

MIC解決了互信息存在的以上缺陷。其在離散化變量之前挑選一個最優方案，再將互信息的取值方式變為統一化的標準度量方法，如式（6）所示。

將取值區間定在[0,1]，相較于互信息而言，MIC有更高的準確度。

2.2.3 距離相關系數

傳統的PCC存在一定的缺陷，在實際計算過程中，即使PCC的值為0，也不能證明計算變量是相互獨立的。但距離相關系數有效克服了這一缺點，當計算的距離相關系為0時，可以完全證明兩個計算變量是相互獨立的。距離相關系數是基于距離的變量u、v間相對獨立性的研究，其可以表示為?dcorr(u,v)，如式（7）所示。當?dcorr(u,v)為0時，則證明兩變量是相互獨立的；?dcorr(u,v)的值越大，則證明兩個變量間的相關性越強。

3 實驗結果與分析

本實驗將差分功耗分析（differential power analysis，DPA）國際學術大賽第四階段（DPA contest v4）[16]的數據集作為實驗對象，該數據集包含10 000條能量曲線，每條能量曲線包含435 000個特征值，本文實驗攻擊點為S盒輸出，模型為漢明重量模型。對TA和基于KNN算法的能量攻擊性能進行對比研究。

3.1 特征點選擇

本文實驗選用的數據集包含10 000條能量曲線，每條能量跡對應的時刻點是相同的，為了提高實驗運算速度，本文僅選擇前r條（r= 100、200、300、400）能量曲線分別采用3種降維技術實現特征點選擇。

3.1.1 PCC進行特征點選擇

使用PCC進行特征點選擇時，X為一組能量曲線，Y為這組能量曲線對應的S盒輸出的漢明重量值，把X和Y代入式（4），得到曲線中與Y相關性較大的特征點（絕對值越接近1的點），選擇這些特征點進行能量分析攻擊。不同r值計算出435 001個特征點對應的PCC如圖2所示。

圖2 不同r值計算435 001個特征點對應的PCC

3.1.2 MIC進行特征點選擇

使用MIC進行特征點選擇時，X為一組能量曲線，Y為這組能量曲線對應的第一個S盒輸出的漢明重量值，把X和Y代入式（6）中，即可以得到曲線中與Y相關性較大的特征點，選擇這些特征點進行能量分析攻擊。不同r值計算出435 001個特征點對應的MIC如圖3所示。

3.1.3 Dcorr特征點選擇

使用Dcorr進行特征點選擇時，u為一組能量曲線，v為這組能量曲線對應的第一個S盒輸出的漢明重量值，把u和v代入式（7），即可以得到曲線中與v相關性較大的特征點，選擇這些特征點進行能量分析攻擊。不同r值計算出435 001個特征點對應的Dcorr相關系數如圖4所示。

圖4 不同r值計算435 001個特征點對應的Dcorr相關系數

由圖2、圖3和圖4可知，3種特征點選擇方法均適用于能量分析攻擊，均可以很好地選擇特征點。且不同的能量曲線條數對相關系數的結果是有影響的，可以看出當能量曲線條數r=300、r=400時的圖像已經趨于相同，所以在統籌節約運算時間和效果的前提下，暫選定r=300。

3.2 特征點數量p對攻擊成功率的影響

3.2.1 特征點數量p對TA的影響

對于TA來說，每條功耗曲線選取特征點p不能過多。每個模板中的功耗曲線是對相同操作數的多次測量，所以具體功耗值都是十分接近的，當選取的特征點越多時，對應的協方差方陣C規模越大，矩陣的行列式越接近于0，即被看作一個奇異矩陣，沒有逆矩陣。在模板匹配時采用多元高斯分布概率密度公式中需要用到協方差矩陣的逆矩陣?1C，所以在TA的過程中每條曲線選取的特征點個數不能太多。經過實際測試，特征點個數p不能大于27。采用300條能量曲線（r=300），基于PCC技術進行特征點選擇后，對數據進行p值分析。p值的選擇對基于TA的能量分析攻擊成功率影響如圖5所示。

圖5 p值的選擇對基于TA的能量分析攻擊成功率的影響

由圖5可知，特征點個數p值對基于TA的能量分析攻擊的影響較為明顯。整體上看，當p值越大時，基于模板的能量分析攻擊成功率越高（少數情況有小幅波動）。當p≤23時，攻擊成功率在0.85以下，相對較低；當p≥24時，攻擊成功率提高到0.86~0.87；當p= 27時，攻擊成功率最高，達到0.868以上。

3.2.2 特征點數量V對KNN算法的影響

采用300條能量曲線（r=300），PCC進行特征點選擇后得到的數據進行p值分析。p值的選擇對于基于KNN算法的能量分析攻擊成功率影響如圖6所示。

圖6 p值的選擇對基于KNN算法的能量分析攻擊成功率的影響（k=7）

由圖6可知，當p值逐漸增大，攻擊成功率逐漸升高（少數情況有小幅波動），當p值超過某閾值后，攻擊成功率轉而逐漸降低。當p=50時，攻擊成功率最高，達到0.928。

3.3.3 特征點數量p對兩種能量分析攻擊的橫向比較

由圖5和圖6可以看出，當p∈[20,27]時，兩種能量分析攻擊方法的攻擊成功率均很高，將p與兩種能量分析攻擊方法進行橫向比較，分析p值的選擇對兩種能量分析算法的影響。p值的選擇對兩種能量分析攻擊方法的影響如圖7所示，整體上看，基于KNN算法的能量分析攻擊成功率明顯高于基于能量分析攻擊成功率，其平均成功率之差在0.066 7以上。

圖7 p值的選擇對兩種能量分析攻擊方法的影響

綜上可得，針對PCC降維技術得到的數據集，當兩個模型選取相同個數的特征點p時，明顯看出結果基于KNN算法的能量分析攻擊成功率更高，且p值的改變引起攻擊成功率的波動幅度更小，即基于KNN算法的能量分析攻擊的魯棒性更強。

3.3 不同特征點選擇方法對攻擊成功率的影響

本節將分析PCC、MIC和Dcorr 3種特征點選擇方法對模板攻擊和KNN算法攻擊成功率的影響。

3.3.1 能量曲線條數固定的影響

當能量曲線條數r為300時，經過3種特征點選擇方法得到數據集，對兩種能量分析攻擊方法的攻擊成功率見表1。TA表示基于模板的能量分析攻擊，KNN表示基于KNN算法的能量分析攻擊，特征點個數p為27。

表1 3種特征點選擇方法對兩種能量分析攻擊成功率的影響（r=300）

由表1可知，PCC、MIC和Dcorr 3種特征點選擇方法對兩種能量分析攻擊方法的影響程度不同，其中，對基于TA的能量分析攻擊的整體影響范圍在0.04內，對于基于KNN算法的能量分析攻擊的整體影響范圍在0.02以內。其中，MIC特征點選擇方法對兩種能量分析攻擊方法的成功率更高。

3.3.2 不同能量曲線條數的影響

控制變量保持不變：特征點個數p=27，KNN算法中近鄰數量k=7。分別對比經3種特征點選擇方法得到的數據對兩種能量分析攻擊成功率的影響。其中，r值的選擇對PCC降維技術效果的影響如圖8所示，r值的選擇對MIC降維技術效果的影響如圖9所示，r值的選擇對Dcorr降維技術效果的影響如圖10所示。

圖8 r值的選擇對于PCC降維技術效果的影響

圖9 r值的選擇對于MIC降維技術效果的影響

圖10 r值的選擇對于Dcorr降維技術效果的影響

由圖8可看出，對PCC降維技術來說并非在計算相關系數時選擇的功耗曲線的條數越多越好，在r=50時，兩種能量分析攻擊的成功率最高。具體地，對基于高斯模板的能量分析攻擊來說，在r=300時攻擊成功率優于除r=50的其他情況，基于KNN算法的能量分析攻擊來說，r值在大于50之后攻擊成功率沒有很大波動，基本趨于穩定。

由圖9可看出，對MIC降維技術來說計算相關系數時選擇的功耗曲線條數越多越好，另外由曲線的波動幅度可以看出基于高斯模板的能量分析攻擊對r值的改變反應更為敏感，而當r≥300后，攻擊成功率沒有很大的波動，基本趨于穩定。

由圖10可看出，對于Dcorr降維技術來說，當r≤300時，r值的增大會導致兩種能量分析攻擊成功率的降低；當r=200時，兩種能量分析攻擊成功率最低；當r≥250后，攻擊成功率在一個較小的范圍內變化（成功率不如r=50時高），沒有很大的波動，基本趨于穩定。

綜上可以得出，為達到較理想的能量分析攻擊效果，采用不同降維技術，應選擇不同功耗曲線條數計算相關系數，即選擇不同的r值。對于采用PCC降維技術，r=50時，兩種能量分析攻擊的成功率最高，效果最理想；對于采用MIC降維技術，r=300或r=400時，兩種能量分析攻擊的成功率最高，效果最理想；對于采用Dcorr降維技術，r=50時，兩種能量分析攻擊的成功率最高，效果最理想。

3.4 兩種能量分析攻擊方法比較

由第3.3節可以看出，攻擊成功率方面，KNN算法的攻擊成功率和魯棒性明顯優于模板攻擊，從運算速度和內存使用情況看，基于模板的能量分析攻擊訓練模型的速度較快，內存使用空間較小，而基于KNN算法的能量分析攻擊訓練模型的運算速度較慢，內存使用空間較大。原因是KNN算法屬于機器學習算法，模型訓練時需要耗費大量內存空間完成計算。兩種能量分析攻擊在攻擊成功率、魯棒性、運行速度和占用內存4個方面的對比見表2。

表2 兩種能量分析攻擊方法的對比

4 結束語

通過本文的對比研究，基于PCC、MIC和Dcorr的3種特征點選擇方法均適用于能量分析攻擊，均可以很好地選擇特征點；特征點p的數量對兩種攻擊方法的攻擊成功率都有一定的影響。不同的降維技術對模板攻擊和基于KNN算法的攻擊成功率有區別。MIC特征點選擇方法對兩種能量分析攻擊方法的成功率更高；為達到較理想的能量分析攻擊效果，建議采用不同的降維技術時，應選擇不同條功耗曲線計算相關系數。采用PCC降維技術時，r值選擇50，可使兩種能量分析攻擊的成功率最高；采用MIC降維技術時，r值選擇300或400，可使兩種能量分析攻擊的成功率最高；采用Dcorr降維技術時，r值選擇50，可使兩種能量分析攻擊的成功率最高。

本文主要針對傳統的模板分析攻擊和KNN算法的攻擊進行對比研究，實驗結果表明模板攻擊在運行速度、占用內存優于基于KNN算法的攻擊，而在攻擊成功率和魯棒性方面，基于KNN算法的攻擊具有更好的表現。當然，有很多方面仍可做進一步的研究和完善：進一步優化KNN算法，使其在運行速度、占用內存方面得到提升；采用多種特征點選擇方法來對兩種攻擊方法進行探索。