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

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

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

0 引言

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

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

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

1 能量分析攻擊

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

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

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

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

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

第三步：計算不同點的協(xié)方差。協(xié)方差是構(gòu)建不同點的相關(guān)性，如式（2）所示。

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

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

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

圖1 算法原理

KNN算法的完整步驟如下：

· 計算測試數(shù)據(jù)與各個訓(xùn)練數(shù)據(jù)之間的距離；

· 按照距離的遞增關(guān)系進行排序；

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

· 確定前k個點所在類別的出現(xiàn)頻率；

· 返回前k個點中出現(xiàn)頻率最高的類別作為測試數(shù)據(jù)的預(yù)測分類。

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

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

2 降維技術(shù)的原理及實現(xiàn)

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

2.1 特征點選擇

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

2.2 3種降維技術(shù)原理

2.2.1 皮爾遜相關(guān)系數(shù)

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

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

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

2.2.2 互信息和最大信息系數(shù)

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

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

MIC解決了互信息存在的以上缺陷。其在離散化變量之前挑選一個最優(yōu)方案，再將互信息的取值方式變?yōu)榻y(tǒng)一化的標準度量方法，如式（6）所示。

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

2.2.3 距離相關(guān)系數(shù)

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

3 實驗結(jié)果與分析

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

3.1 特征點選擇

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

3.1.1 PCC進行特征點選擇

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

圖2 不同r值計算435 001個特征點對應(yīng)的PCC

3.1.2 MIC進行特征點選擇

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

3.1.3 Dcorr特征點選擇

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

圖4 不同r值計算435 001個特征點對應(yīng)的Dcorr相關(guān)系數(shù)

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

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

3.2.1 特征點數(shù)量p對TA的影響

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

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

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

3.2.2 特征點數(shù)量V對KNN算法的影響

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

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

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

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

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

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

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

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

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

3.3.1 能量曲線條數(shù)固定的影響

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

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

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

3.3.2 不同能量曲線條數(shù)的影響

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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