基于聚類的密碼芯片頻域側信道分析

蔡爵嵩，嚴迎建，朱春生，郭朋飛

(戰略支援部隊信息工程大學，河南 鄭州450002)

0 引言

側信道分析(Side-channel Analysis，SCA)是一種不僅利用算法本身，更依賴于密碼算法物理實現中的側信道泄漏的分析方法，嚴重威脅到密碼芯片的安全性。 能量分析是一種最流行的側信道分析方式，包括簡單能量分析(Simple Power Analysis，SPA)[1]、差分能量分析(Differential Power Analysis，DPA)[2]、模板攻擊(Template Attacks，TA)[3]、相關能量分析(Correlation Power Analysis，CPA)[4]等。現有文獻主要是針對密碼芯片的能量消耗在時域上進行分析。 但時域分析有一定的局限性，如能量跡的對齊問題。通常采集設備的不穩定或者芯片加入時鐘隨機化防護措施，都會導致能量跡需要進行對齊處理。因此，能量跡的對齊成為影響側信道分析成功率的關鍵因素之一。

密碼芯片有效信號的頻率由時鐘頻率決定，不會受到采集設備和手段的影響，所以使用有效信號的頻率能量大小代替能量跡采樣點的功耗大小作為密鑰的特征是可行的。 2000 年，AIGNER M 等人表示在對密碼芯片側信道分析中，時域內的能量消耗差異在頻域內同樣會體 現 出 來[5]。 2005 年，GEBOTYS C H 等 人 在CHES 會 議上通過對電磁信號的頻域進行分析首次驗證了頻域側信道分析的可行性[6]。 近年來，將能量跡轉換到頻域進行側信道分析已經被證明是一種解決能量跡對齊問題的有效途徑[7-9]。 雖然頻域側信道分析能夠解決時域側信道分析的對齊問題，但由于噪聲頻率可能與有效信號頻率相同或相近，因此頻域側信道分析通常需要更多的能量跡，如文獻[7]采集了70 000 條能量跡，文獻[8]采集了10 000 條能量跡。

文獻[10]～[14]表明將機器學習引入側信道分析，能夠有效找到能量跡上的特征點，提高側信道分析的成功率。2017 年，ZHANG R N 等人[14]直接使用機器學習中的無監督學習算法k-means 對時域內的能量跡進行了分析，并成功獲得其密鑰。 本文將機器學習中的聚類算法引入頻域側信道分析中，尋找信號頻率內在的分布，對有效信號頻率進行分離，從而減少頻域側信道分析所用能量跡條數。

1 基礎知識

1.1 相關能量分析(CPA)

2004 年，BRIER E 等人提出了相關能量分析(Correlation Power Analysis，CPA)[4]，工作原理是基于芯片能量消耗W 與中間值模型H 之間具有線性相關性。 通過計算W 與H 之間的皮爾遜相關系數ρ(W，H)來評估中間值模型與實際能量消耗的匹配程度。

一般地，分析者采用的中間值模型為漢明重量模型(Hamming Weight，HW)或漢明距離模型(Hamming Distance，HD)。 分析者通過計算猜測密鑰對應的中間值與芯片實際能量消耗之間的相關系數來進行分析，相關系數最大的對應密鑰值即被認為是正確密鑰。

1.2 頻域側信道分析

密碼芯片的頻域側信道分析就是對傅里葉變換后的能量跡進行分析。由于能量跡是由采集設備采樣得到的數字信號，在時域內是離散的有限時間序列，因此本文采用的是離散傅里葉變換(Discrete Fourier Transform，DFT)。

一般地，信號的時域波形表示信號隨時間的變化，而其頻域圖則顯示了在一個頻率范圍內每個給定頻帶內的信號量，所以頻域內的信息更集中。 這也是頻域側信道分析一般需要比時域側信道分析更多的能量跡條數的原因。

1.3 k-means 算法

機器學習中的無監督聚類算法可以利用樣本數據內在的相似性對樣本數據進行自動分類。將每一類稱為一個簇，則有簇內相似性高、簇間相似性低的特點。本文選取應用最廣、算法實現最簡單的k-means 算法進行聚類分析。

給定樣本集D={x1，x2，…，xm}，k-means 算法從中選擇k 個樣本作為初始聚類中心{μ1，μ2，…，μk}，計算樣本xj(1≤j≤m)與各初始聚類中心μi(1≤i≤k)之間的距離：根據距離最近的聚類中心確定樣本xj的簇標記λj(1≤j≤m)：

1.4 輪廓系數(Silhouette Coefficient)

1986 年，ROUSSEEUW J 等人提出了輪廓系數(Silhouette Coefficient)[15]，用來衡量一個點與它所屬聚類類別的相似程度，可以用來在相同數據的基礎上來評價不同算法或者算法不同參數對聚類結果產生的影響。

(1)計算樣本xj(1≤j≤m)到同一簇Cλj內其他樣本的平均距離aj。 aj越小，表明樣本xj越應該被聚類到該簇。aj被稱為樣本xj的簇內不相似度。

(2)計算樣本xj到其他簇Ci(i=1，2，…，k；i≠j)內所有樣本的平均距離bij，稱之為樣本xj與簇Ci(i=1，2，…，k；i≠j)的不相似度，即樣本xj的簇間不相似度。

bj為 樣 本xj到 其 他 簇Ci(i=1，2，…，k；i ≠j)內 所 有樣本的最小平均距離。可以知道，bj越大，說明樣本xj越不屬于其他簇Ci(i=1，2，…，k；i≠j)。

(3)根據樣本xj的簇內不相似度aj和簇間不相似度bj，就可以定義樣本xj的輪廓系數Sj：

容易知道，-1≤Sj≤1，當Sj越接近于1 時，簇內越緊湊，簇間越稀疏，聚類效果越優。所有樣本的輪廓系數Sj的均值為聚類結果的輪廓系數，是評價該聚類是否合理、有效的指標之一。

2 基于聚類的頻域側信道分析

2.1 使用聚類算法分離有效信號的可行性分析

現在來分析能量跡中的有效信號與噪聲信號相似度是否較低，即能否在能量跡中有效分離出有效信號。 設能量跡中某一點的信噪比(Signal to Noise Ratio，SNR)為：

其中，Pexp為側信道分析所利用的有效信號能量，Psw.noise為轉換噪聲，Pel.noise為電子噪聲。 顯而易見，SNR 越高，從全部信號分離出Pexp越容易。一般地，在采集密碼芯片能量消耗時通過低通濾波技術來提高能量跡的SNR，確保側信道分析能夠成功。 因此，對于一個能夠成功進行頻域側信道分析的能量跡來說，Pexp是能夠從全部信號中分離出來的。

本文的研究是在能夠成功實施頻域側信道分析的前提下進行的，所以有效信號Pexp是能夠從全部信號中分離出來的。 由于噪聲頻率和有效信號頻率均為基頻的倍數，因此，將能量跡進行傅里葉變換后，有效信號的頻率與大部分噪聲信號的頻率的相似度低，只有很小一部分噪聲與有效信號同頻或頻率接近，但這并不妨礙進行側信道分析。 因此，使用聚類算法能夠有效分離出有效信號的頻率。

2.2 基于聚類的頻域側信道分析方法

結合頻域側信道分析方法和聚類算法，本文提出基于聚類的頻域側信道分析方法，流程圖如圖1 所示。 現給出該方法的具體實施步驟：

(1)使用采集設備對密碼芯片能量消耗進行采集，得到n 條能量跡ti(i=1，2，…，n)，組成能量跡集T={t1，t2，t3，…，tn}。

(2)對能量跡集T={t1，t2，t3，…，tn}中的每一條能量跡ti(i=1，2，…，n)進行離散傅里葉變換(DFT)，得到：

(3)對T′使用k-means 算法進行聚類。 k-means 算法非常簡單且使用廣泛，運行速度快，可用于處理大型的數據集。 但該算法存在對初始參數比較敏感，需要找到相似程度低的類別才能進行較好的聚類。

由于只存在有效信號頻率和噪聲頻率，因此聚類類別數設置為2。

(4)由于能量跡中噪聲頻率分布更廣，有效信號頻率占比較少，因此選擇其中簇內數量較少的一類進行側信道分析， 一般采用1.1 節所描述的相關能量分析(CPA)方法進行側信道分析。

(5)如果失敗，則回到步驟(3)。 因為聚類算法是根據數據內在特征進行自動分類，所以有可能會出現無法得到預期結果的情況。因此，在失敗時，應該重新進行聚類分析，或者在對聚類算法進行優化改進[16]。

圖1 基于聚類的頻域側信道分析方法流程圖

3 實驗驗證及分析

本文使用ChipWhisperer 系列側信道分析開發板[17]進行實驗，驗證基于聚類的密碼芯片頻域側信道分析方法的可行性。

3.1 實驗數據采集

本節使用CW1173 ChipWhisperer-Lite 開發板[18]進行能量跡采集，目標設備為ATMEGA XMEGA128，密碼算法為128 位AES 算法, 共采集60 000 條能量跡用作分析。 實驗平臺為MATLAB R2018b，傅里葉變換使用的是MATLAB 自帶的fft 和fftshift 函數。

圖2 為AES 算法第一輪的能量跡曲線，圖3 為經過傅里葉變換后的頻域幅值譜。

圖2 AES 算法第1 輪能量跡曲線

圖3 AES 第1 輪能量跡經過傅里葉變換后的頻域幅值譜

3.2 實驗過程及結果

對AES 算法前4 輪分別進行傅里葉變換后，利用1.1節描述的相關能量分析(CPA)方法進行分析，中間值模型選擇為S 盒輸出的漢明重量(HW)值，然后計算中間值模型與傅里葉變換后的能量跡之間的相關系數。當連續使用多條能量跡進行分析得到的最大相關系數對應的猜測密鑰值key_guess 不變時，即認為是正確密鑰。

采取對比實驗，設定3 組實驗，第1 組為全部能量跡，第2 組為聚類后數量較多的能量跡，第3 組為聚類后數量較少的能量跡，分別記為I、II、III。 在實驗中，將第I 組作為基準，第II 組和第III 組都與第I 組進行比較，看本文方法是否會減少能量跡條數，同時第II 組與第III 組進行比較，看本文方法是否能夠準確分離出有效信號頻率，結果如表1 所示。 其中，表內失敗是指使用60 000 條能量跡無法分析得到正確密鑰；表1 結果為最少所需能量跡條數；由于聚類算法是根據數據內在特征進行自動分類，因此會出現結果與表1 結果不一致的情況。

表1 3 組實驗分析成功所需能量跡條數

3.3 實驗結果分析

本文引入1.4 節介紹的輪廓系數(Silhouette Coefficient)對聚類算法參數設置和聚類后的結果進行評價。圖4～圖7 分別對應AES 算法第一輪的第1 個S 盒、第2個S 盒、第3 個S 盒、第4 個S 盒聚類后的輪廓系數圖。

圖4 AES 算法第一輪第1 個S 盒聚類后輪廓系數示意圖

圖5 AES 算法第一輪第2 個S 盒聚類后輪廓系數示意圖

從圖4～圖7 可以看出，4 次聚類后的輪廓系數均接近1，說明文中聚類參數設置合理、有效，聚類效果較好，進一步說明本文所提方法的步驟(3)將聚類類別設為2 是正確的，同時表明通過聚類算法能夠從全部信號中分離出有效信號。

圖6 AES 算法第一輪第3 個S 盒聚類后輪廓系數示意圖

圖7 AES 算法第一輪第4 個S 盒聚類后輪廓系數示意圖

通過對表1 的分析可知，第III 組分析成功所需能量跡條數明顯少于第I 組和第II 組，并且第II 組還存在不能成功分析的情況，說明能量跡中的有效信號頻率確實在第III 組當中，即能準確分離出有效信號頻率，從而進行有效側信道分析，減少頻域側信道分析所需能量跡條數。

4 結論

將密碼芯片的能量消耗轉換到頻域進行側信道分析，能夠有效解決能量跡對齊問題，但由于頻域內的一個點對應時域內的多個點，因此頻域側信道分析往往需要更多的能量跡條數。 本文針對這個問題，提出使用機器學習中的聚類算法找出有效信號的頻率后進行分析。實驗結果表明，本文方法能夠減少密碼芯片頻域側信道分析所需的能量跡條數。將本文方法應用于密碼芯片頻域側信道分析中，能夠提高分析性能，使頻域側信道分析更加實用。