密碼芯片基于聚類的模板攻擊

吳震，杜之波，王敏，向春玲

?

密碼芯片基于聚類的模板攻擊

吳震，杜之波，王敏，向春玲

（成都信息工程大學網絡空間安全學院，四川 成都 610225）

傳統的模板攻擊需要已知密鑰建模等對實驗設備完全控制的前置條件來實施攻擊，該前置條件限制了模板攻擊的應用場景，使模板攻擊只能應用于可以控制密鑰輸入的設備。為了解決該問題，提出了基于聚類的模板攻擊方法。該方法根據信息泄露模型的特征對聚類期望最大值（EM）算法進行改造，使改造后的聚類方法能夠較為準確地擬合出泄露信息的概率模型，在未知密鑰的情況下，即可確定信息泄露的位置。該方法通過建模進行模板匹配，消除了傳統模板攻擊對已知密鑰建模等前置條件的依賴，從而擴大了模板攻擊的應用范圍。

側信道攻擊；模板攻擊；聚類；EM算法

1 引言

側信道攻擊是一種利用加密設備的能量泄露來攻擊設備密鑰的方法。Kocher等最早提出SPA （simple power analysis）[1]和DPA（differential power analysis）[2]的能量攻擊方法。這些攻擊方法的原理是：假設加密的某個中間狀態與泄露的能量具有相關關系，攻擊者可以使用泄露的能量來檢查、猜測密鑰的正確性，從而達到攻擊的目的。CPA（correlation power analysis）[3]是利用這種相關性進行攻擊的最有效方法。SPA、DPA、CPA以及基于這些方法提出的其他方法都是直接對加密設備進行攻擊的，并不需要一個訓練階段。

模板攻擊[4]是側信道攻擊技術的另一個分支。模板攻擊分為2個階段：建模和攻擊。在建模階段，模板攻擊利用與被攻擊設備相同的、攻擊者可完全控制的實驗設備，通過設置密鑰和明文實施多次加密操作，收集操作的大量能耗數據，并據此建立、刻畫被泄露信息的能耗概率模型。精確的能耗概率模型可以使攻擊者僅使用少量的攻擊能跡就能夠恢復設備的密鑰。但相對于SAP、DPA和CPA，模板攻擊需要攻擊者具有對實驗設備的完全控制能力，這限制了其應用范圍。為了克服這一現狀，文獻[5]提出一種僅需3個密鑰的半監督建模方法；文獻[6-7]則更近一層地提出EIS（equal image under different sub-key）的概念，即不論使用固定密鑰隨機明文，還是使用固定明文隨機密鑰，加密中間值的分布都是相同的。這樣，攻擊者只需要知道實驗設備的密鑰，而不需要改變其密鑰，采用固定密鑰隨機明文的方法收集能跡，同樣可以建立泄露信息的模板，進而成功地獲取被攻擊設備的密鑰。

本文對高斯混合分布的EM算法在模板攻擊中的應用方法進行了詳細的討論。根據理論上和實際中的經驗，提出了對EM算法的幾種針對性的約束，以便真正提高聚類的質量。這些方法運用在9個簇的漢明重量模型的聚類中，可以相當準確地還原出真實成員分布。針對EM算法得到局部最優的問題，本文給出了切實可行的算法初始參數設置方法。此外，上述文獻并未討論如何在密鑰或掩碼未知的情況下，找到確切的泄露位置，針對泄露位置的問題，要么采用類似暴力攻擊的方法，要么直接假設已知泄露位置。對此，本文提出了一種在未知密鑰的情況下，準確找到信息泄露位置的方法。

2 基于聚類的模板攻擊模型

2.1 基本攻擊模型

假設攻擊者沒有標準模板攻擊所需要的實驗設備，即不能設置加密設備的密鑰，只能設置任意隨機明文使用加密設備進行加密操作，并收集設備能耗。在這種場景下，由于密鑰未知，無法計算目標操作的中間值，不能使用有監督的學習方法獲得模板。

在這種無法預知中間值、無法明確分類的情況下，則可以采用無監督的學習發現數據外在的劃分或內在的模型。無監督的學習算法可以分為2個類別：簇合算法和基于潛變量模型的學習。簇合算法根據數據本身的特征（相似性、距離等），將特征相似或距離相近的數據聚集在一起形成簇。常見的簇合算法包括-means、DBSCAN、高斯混合模型等。簇合算法的質量取決于數據特征的顯著程度。基于潛變量模型的學習算法認為數據中可觀察的變量（顯變量）是由內在的、不可觀察的隱變量決定的。

在側信道攻擊中，廣為接受的能耗模型是漢明重量或漢明距離模型。該模型認為，加密操作中間值的漢明重量或漢明距離與相應的能耗呈線性關系，且疊加高斯噪聲。這樣，各漢明重量或漢明距離的能耗是一個高斯分布，所有漢明重量或漢明距離的能耗則是一個混合高斯分布。這種成員分布就是模板攻擊中所需要的模板。針對混合高斯分布的無監督學習算法是EM算法。如果攻擊者可以使用EM算法還原出真實的內在分布，就可以以此為模板進行模板攻擊。這里的關鍵問題是，對于高噪聲、低信噪比的能耗數據，EM算法能夠在多大程度上還原數據的真實分布。

2.2 混合高斯模型及其EM聚類算法

2.2.1 漢明重量能耗模型與混合高斯分布

以8位SBOX輸出為例，其漢明重量為0~8。圖1給出了實際能耗數據的混合一元高斯分布。

圖1 實際能耗數據的混合一元高斯分布

從圖1可以看出，實際分布與漢明能耗模型的預測是非常相符的。

2.2.2 使用EM算法估算能耗的混合高斯分布

若式(9)對各參數的偏導等于0，就可以得到EM算法迭代中參數的更新方法，為

EM算法通過反復迭代來優化對數似然率的數學期望，直到對數似然率的變化小于一個閾值為止。每次迭代分為E-Step和M-Step。

E-Step：根據當前的模型參數，使用式(9)計算成員率矩陣。

M-Step：根據當前的成員率，使用式(10)~式(12)更新模型參數。

然而，對于低信噪比的能耗數據，標準EM算法的聚類并不能恢復真實的成員分布。圖2是在混合二元高斯模型下，EM算法得到的成員分布與真實成員分布的對比情況。其中，橢圓是各成員分布的95%最大概率密度的等高線。黑色為真實數據的成員分布，灰色是EM算法得到的混合高斯分布的聚類成員分布（下同）。可以看出，由于各漢明重量的能耗數據高度混淆在一起，標準EM算法并不能準確恢復真實成員分布的中心位置和方差。

圖2 真實成員分布（黑色）與EM聚類成員分布（灰色）比較

2.3 漢明能耗模型及其EM聚類算法

漢明能耗模型是一種特殊的高斯混合分布模型，有以下特征。

1) 成員分布的先驗概率固定

對于本文設定的攻擊場景：密鑰固定和采用隨機明文，目標操作的中間值是均勻分布的。這樣，中間值的漢明重量呈二項分布。假設中間值為位，漢明重量為時對應的成員分布的先驗概率為

2) 相鄰成員分布中心的距離相等

在漢明能耗模型中，由于均值能耗與漢明重量呈線性關系，即

則任意2個相鄰的漢明重量的均值能耗之差為

其中，協方差矩陣的更新方式并未發生變化。

漢明能耗模型還有一個弱特征，即各成員分布的協方差矩陣相同或接近。這是因為，與同一個操作相關的噪聲主要是由操作指令的硬件實現決定的，而與操作數的關系不大。假設該特征成立，則各成員的協方差矩陣應該是相同的。共享協方差矩陣的更新式為

圖3和圖4為采用上述特征改造EM算法后，數據的聚類成員分布與真實成員分布的對比情況。從圖3可以看出，聚類得到的成員分布與真實成員分布仍然有一定差異。不僅是各成員分布中心與真實中心仍有較大的差異，成員分布的方差與真實方差相比也有較大差異。但總體來看，其比采用標準EM算法得到的結果要好得多。而圖4是采用共享協方差矩陣得到的結果。其特點是：共享協方差矩陣的EM算法趨于將成員分布重疊在整體能耗均值中心，這一點可以從理論上得到證明（略）。因此，共享協方差矩陣在這里無法得到應用。

圖4 共享協方差矩陣時，聚類成員分布與真實成員分布

3 EM算法改造

由于能耗數據的低信噪比的特點，標準的EM算法的聚類結果與真實數據分布相差巨大。而模板攻擊所依賴的是對數據噪聲的準確了解和表達。如果不對算法進行適應性改造，使用聚類算法進行模板攻擊是不可行的。漢明重量模型提供了一些特征，可供對混合高斯模型以及相應的EM算法進行改造。

3.1 對聚類的優化

上述根據漢明能耗模型特征對EM算法的改造仍然無法得到所需的聚類質量。本節根據其他一些隱藏的特征，為EM算法附加一些額外約束，以期提高聚類質量。

3.1.1 成員分布的相關系數約束（pdc）

成員分布的協方差矩陣的非對角元素為

相應地修改EM算法的M-Step：首先按對角協方差矩陣更新對角元素為

然后根據式(23)計算協方差矩陣的非對角元素。

圖5顯示了采用相同相關系數后，聚類得到的成員分布與真實成員分布的對比情況。與第2節的聚類結果相比，采用相同的相關系數后，成員分布的中心和方差與真實分布更加接近。

圖5 pdc條件下聚類成員分布與真實成員分布對比

從圖5可以看出，采用pdc相關系數約束后，成員分布中心和方差與真實分布較為接近。

3.1.2 成員分布的形狀約束（pds）

根據真實分布的特點可以看出，所有成員分布等高線的“形狀”大致相似。這并不是偶然的。“形狀相似”實際上反映了不同漢明重量下，能耗的概率密度分布是相似的。不同的漢明重量可能影響方差的大小，但不會影響各維數據方差的比例關系和相關性。因此，成員分布形狀相似的假設比共享協方差矩陣的假設稍弱。

從幾何上看，等高線形狀相似包括2個因素：等高線橢圓的方向一致，且橢圓的長短軸比例相等。首先推導二元高斯分布等高線的方向，然后擴展到多元高斯分布。

將式(28)代入式(27)，且設式(27)右端等于1，則有

式(30)旋轉后得

(32)

比較式(30)和式(28)，有以下方程組成立。

解式(32)可得

對于多元高斯分布，對其中任意二維使用式(34)，可計算等高線在該二維子平面上的旋轉角度。然后利用式(35)，根據成員分布在該二維上的方差，計算子平面上的協方差。

根據這種方法，聚類的結果如圖6所示。除漢明重量為0和8的成員分布與真實分布有偏差外，其余成員分布的中心和方差幾乎完全與真實分布相同，非常好地還原了真實成員分布。漢明重量為0和8的擬合成員分布與真實分布的偏差主要來源于真實分布自身的偏差：在固定密鑰、隨機明文的訓練能跡中，漢明重量為0和8的能跡數與總訓練能跡數的比例近似等于其理想先驗概率，即0.39%。實驗中使用8 000條能跡，而漢明重量為0和8的能跡數僅為31條左右。由于能跡不足，造成了其真實分布的統計偏差。

圖6 psd條件下成員分布與真實成員分布對比

從圖6可以看出，使用成員分布等高線形狀相似約束后，EM算法可以很好地恢復真實分布。

3.2 聚類的初始參數設置

3.2.1 未知密鑰時發現信息泄露的位置

由于能跡上的樣本數非常多，大多數樣本與目標操作的信息泄露無關。直接使用能跡的全部樣本作為能跡向量的元素，在效率上不可行，聚類的結果也不可能作為有效的模板。在本文設置的攻擊場景下，設備密鑰位置，無法計算真實的目標中間值，因此無法使用這些方法得到POI。

3.2.2 根據設備信噪比設置聚類初始參數

由于EM算法得到的是局部最優解，算法初始參數的設置非常關鍵。根據混合分布的整體方差與成員方差的關系以及理想分布中關于成員分布中心均勻線性分布和方差相等的假設，可以根據POI上的信噪比估算初始參數。

混合分布與其成員分布的方差關系為

根據理想分布的假設，有

代入式(38)可得

根據能耗上信息泄露的特點，將信噪比定義為

代入式（40）后得到

4 實驗分析

4.1 實驗設置

針對某密碼芯片的SM4算法軟實現進行多種方式的攻擊，共收集能跡10 000條，其中，8 000條用于訓練，2 000條用于攻擊測試。芯片主頻為2.8 MHz，示波器采樣頻率為100 MHz。采樣能跡進行了低通濾波和對齊處理。

4.2 確定信息泄露位置

根據上文所述方法，確定被攻擊SM4芯片的POI，圖7是根據SOST確定的第一個SBOX輸入和輸出的POI，圖中2個高尖峰對應的位置即是SBOX輸入和輸出的POI，SBOX輸入的位置為509，SBOX輸出的位置為554，根據分組內SBOX輸入和輸出值以及輸入和輸出漢明重量確定的POI如表1所示。

圖7 能耗跡的SOST峰值

表1 POI點

4.3 與標準模板攻擊的對比實驗

實驗中分別采用以下方法獲得模板，以便進行對比。

1) 標準的模板攻擊。即使用已知的固定密鑰對訓練能跡集進行分組，從而得到模板，該方法用STD表示。

2) 采用EM算法對訓練能跡進行聚類得到的模板，該方法用EM表示。

3)采用根據漢明能耗模型改造的EM算法聚類得到的模板，該方法用EMPD表示。

4) 在漢明能耗模型的基礎上，采用增加相關性約束改造EM算法后聚類得到的模板，該方法用EMPDC表示。

5) 在漢明能耗模型基礎上，采用增加“形狀相似”約束改造EM算法后聚類得到的模板，該方法用EMPDS表示。

攻擊方法2)~5)選擇POI的方法見3.2節。實驗中統一選擇2個興趣點。攻擊質量的指標用1階成功率到4階成功率表示。階成功率表示正確密鑰在攻擊后得到的、按概率降序排序的候選密鑰集的前個的比例。猜測熵[16]表示在多次實驗攻擊中，正確密鑰的平均位置。根據文獻[16]給出的猜測熵計算方法，計算每個攻擊方法的猜測熵。

從圖8可以更明確地觀察5種模板生成方法之間的比較關系。從表2可以看出，EMPDS方法的攻擊成功率基本與模板攻擊相當，而EM方法最差，EMPD與EMPDC沒有本質的區別。

圖8 5種模板生成方法的1階成功率比較

4.4 對一個能跡集的攻擊實驗

在本文設定的攻擊場景下，由于訓練時密鑰未知，因此在實際攻擊時，不存在訓練能跡集與攻擊能跡集的區別。本節實驗采用一個能跡集，同時用于訓練和攻擊。本實驗的目的是，測試能跡集的大小與攻擊成功率的關系。

攻擊時并不采用全部能跡，而僅選擇在能耗均值向量附近的30條能跡作為攻擊能跡。由于計算成功率需要多次實驗，且每次實驗需要采用不同的能跡進行攻擊，因此首先選擇與能耗均值向量最接近的600條能跡作為攻擊能跡集，每次實驗隨機從其中選擇30條進行攻擊，共進行20次攻擊。此外，根據4.2節實驗的結果，這里僅對標準模板攻擊和采用EMPDS的攻擊進行比較，如表3所示。

從表3可以看出，訓練能跡集達到3 000條后，4階成功率可達到100%；訓練能跡集達到5 000條后，1階成功率可達到100%，該成功率已優于標準模板攻擊。當能跡數在4 000條以下時，由于數據稀缺問題，聚類質量出現下降，該問題在標準模板攻擊中同樣存在。從猜測熵的對比來看，EMPDS在所有訓練能跡數下均小于標準模板攻擊。

5 結束語

從實驗結果可以看出，改造后的EM算法可以相當好地還原出不同漢明重量能耗的成員分布，從而成功實現模板攻擊。這種攻擊方式并不需要攻擊者掌握對被攻擊設備的控制權，甚至也不需要了解任何密鑰信息，就能以相當高的成功率攻擊出密鑰。從效率來看，由于本文方法可以準確地找到POI，同時合理地設置了EM算法的初始參數，聚類效率也比較高（一般10次迭代就可以達到閾值）。實驗中為了證明本文方法的有效性，與標準模板攻擊進行對比，驗證了兩者的應用場景不同。標準模板攻擊通過實驗設備得到模板后，只需要少量能跡即可實施攻擊。而本文方法雖然不需要實驗設備，但事實上需要更多的能跡來以聚類方式建模和實施攻擊。本文的主要貢獻在于：突破了已有對實驗設備完全可控的局限性，詳細討論了EM聚類算法在能耗混合高斯分布中的適應性改造，并在實踐中證明了這種改造的有效性。

表2 5種模板訓練方法的攻擊成功率和猜測熵對比

表3 STD與EMPDS訓練能跡數與攻擊成功率的關系

[1] KOCHER P C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[C]//Annual International Cryptology Conference. 1996: 104-113.

[2] KOCHER P, JAFFE J, JUN B. Differential power analysis[C]//Annual International Cryptology Conference. 1999: 388-397.

[3] BRIER E, CLAVIER C, OLIVIER F. Correlation power analysis with a leakage model[C]//International Workshop on Cryptographic Hardware and Embedded Systems. 2004: 16-29.

[4] CHARI S, RAO J R, ROHATGI P. Template attacks[C]//International Workshop on Cryptographic Hardware and Embedded Systems. 2002: 13-28.

[5] LERMAN L, MEDEIROS S F, VESHCHIKOV N, et al. Semi- supervised template attack[C]//International Workshop on Constructive Side-Channel Analysis and Secure Design. 2013: 184-199.

[6] SCHINDLER W, LEMKE K, PAAR C. A stochastic model for differential side channel cryptanalysis[C]//International Workshop on Cryptographic Hardware and Embedded Systems. 2005: 30-46.

[7] GIERLICHS B, LEMKE-RUST K, PAAR C. Templates vs. stochastic methods[C]//International Workshop on Cryptographic Hardware and Embedded Systems. 2006: 15-29.

[8] KARSMAKERS P, GIERLICHS B, PELCKMANS K, et al. Side channel attacks on cryptographic devices as a classification problem[J]. Esat Kuleuven Be, 2009, 7: 36.

[9] LERMAN L, POUSSIER R, BONTEMPI G, et al. Template attacks vs. machine learning revisited (and the curse of dimensionality in side-channel analysis)[C]//International Workshop on Constructive Side-Channel Analysis and Secure Design. 2015: 20-33.

[10] LERMAN L, BONTEMPI G, MARKOWITCH O. Side channel attack: an approach based on machine learning[J]. Center for Advanced Security Research Darmstadt, 2011: 29-41.

[11] BATINA L, GIERLICHS B, LEMKE-RUST K. Differential cluster analysis[M]//Cryptographic Hardware and Embedded Systems-CHES. 2009: 112-127.

[12] CHOU J W, CHU M H, TSAI Y L, et al. An unsupervised learning model to perform side channel attack[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining. 2013: 414-425.

[13] HEYSZL J, IBING A, MANGARD S, et al. Clustering algorithms for non-profiled single-Execution attacks on exponentiations[C]// International Conference on Smart Card Research and Advanced Applications. 2013: 79-93.

[14] LEMKE-RUST K, PAAR C. Gaussian mixture models for higher-order side channel analysis[C]//International Workshop on Cryptographic Hardware and Embedded Systems. 2007: 14-27.

[15] MANGARD S, OSWALD E, POPP T. Power analysis attacks: revealing the secrets of smart card[M]. New York: Springer. 2007.

[16] STANDAERT F X, MALKIN T G, YUNG M. A unified framework for the analysis of side-channel key recovery attacks[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2009: 443-461.

Template attack of Crypto chip based on clustering

WU Zhen, DU Zhibo, WANG Min, XIANG Chunling

College of Information Security Engineering, Chengdu University of Information Technology, Chengdu 610225, China

The known-key establishment template and others full control of experimental equipment preconditions are required to implement the traditional template attack. The preconditions restrict the application scenario of template attack. The template attack is only applied to the device that the key input can be controlled. In order to resolve the restrictive preconditions, a novel method of template attack based on clustering was proposed. The clustering EM algorithm was modified according to the characteristics of information leakage model in the method. The modified clustering methods accurately fitted the leaked information probability model in the case of unknown key, the location of information leakage could be determined. Then the attack established the templates in the location, and implemented template matching. The proposed method eliminates the dependence of traditional template attacks on per-conditions and expand the application scenario of template attack.

side channel attack, template attack, clustering, EM algorithm

TP309.1

A

10.11959/j.issn.1000?436x.2018130

吳震（1975?），男，江蘇蘇州人，成都信息工程大學副教授，主要研究方向為信息安全、密碼學、側信道攻擊與防御、信息安全設備設計與檢測。

杜之波（1982?），男，山東冠縣人，成都信息工程大學副教授，主要研究方向為信息安全、側信道攻擊與防御、天線應用和物聯網安全。

王敏（1977?），女，四川資陽人，成都信息工程大學副教授，主要研究方向為網絡攻防、側信道攻擊與防御。

向春玲（1990?），女，湖北宜昌人，成都信息工程大學助教，主要研究方向為信息安全、嵌入式系統安全、側信道攻擊與防御。

2018?04?02；

2018?07?16

杜之波，du139123456789@163.com

國家科技重大專項基金資助項目（No.2014ZX01032401）；國家高技術研究發展計劃（“863”計劃）基金資助項目（No.2012AA01A403）；“十三五”國家密碼發展基金資助項目（No.MMJJ20180244）；四川省科技支撐計劃項目基金資助（No.2017GZ0313）；四川省教育廳重點科研基金資助項目（No.17ZB0082）

The National Science and Technology Major Project of China (No.2014ZX01032401), The National High Technology Research and Development Program of China (863 Program) (No.2012AA01A403), The “13th Five-Years” National Cryptogram Development Fund (No.MMJJ20180244), Sichuan Science and Technology Support Programmer (No. 2017GZ0313), Sichuan Provincial Education Department Key Scientific Research Projects (No.17ZB0082)