基于主成分分析的AES算法相關(guān)功耗分析攻擊*

基于主成分分析的AES算法相關(guān)功耗分析攻擊*

蔡 琛1，陳 運(yùn)1，2，萬武南1，陳 俊1，胡曉霞1
(1.成都信息工程大學(xué)應(yīng)用密碼學(xué)研究所，四川 成都 610225;2.電子科技大學(xué) 通信學(xué)院，四川 成都610054)

針對相關(guān)功耗分析攻擊中，當(dāng)功耗曲線的功耗采樣點(diǎn)較多時(shí)攻擊速度緩慢的問題，引入了基于主成分分析的預(yù)處理方法。利用主成分分析對功耗曲線進(jìn)行預(yù)處理，提取功耗信息中的主成分，拋棄次要成分，將功耗數(shù)據(jù)降維，達(dá)到減少數(shù)據(jù)分析量的目的，從而提高攻擊效率。以高級加密標(biāo)準(zhǔn)為研究對象，對基于主成分分析的相關(guān)功耗分析攻擊進(jìn)行了研究。引入主成分分析的相關(guān)功耗分析攻擊與經(jīng)典相關(guān)功耗分析攻擊的對比實(shí)驗(yàn)結(jié)果表明:基于主成分分析的預(yù)處理將功耗曲線中相關(guān)性高于0.2的信息集中到前67號的主成分中，有效地將實(shí)際分析功耗點(diǎn)的數(shù)量降低至經(jīng)典相關(guān)功耗分析的大約1/4。

密碼分析;邊信道攻擊;相關(guān)功耗分析攻擊;主成分分析;功耗預(yù)處理;高級加密標(biāo)準(zhǔn)

0 引言

密碼設(shè)備運(yùn)行算法時(shí)產(chǎn)生時(shí)間[1]、功耗[2]、電磁[3]等邊信息泄露，泄露的邊信息與加密運(yùn)算中的操作或數(shù)據(jù)存在相關(guān)性，利用這些邊信息攻擊密鑰的方法叫邊信道攻擊。功耗分析攻擊(Power Attacks，PA)[4-5]是其中一種邊信道攻擊(Side Channel Attack，SCA)[6-7]方法。攻擊者采集密碼設(shè)備運(yùn)行時(shí)的功耗，通過對功耗信息進(jìn)行分析來破解密鑰。在信息安全形勢日漸嚴(yán)峻的今天，邊信道安全越來越被學(xué)術(shù)和工業(yè)界重視。

功耗分析攻擊主要分為簡單功耗分析攻擊(Simple Power Analysis，SPA)[2]、差分功耗分析攻擊(Differential Power Analysis，DPA)[2]、模板攻擊(Template Attack，TA)[8]和相關(guān)功耗分析攻擊(Correlation Power Analysis，CPA)[9-10]。CPA是上述方法中對功耗信息利用較好的方法[11-12]。然而，相關(guān)功耗分析攻擊中計(jì)算相關(guān)系數(shù)相當(dāng)耗時(shí)，尤其在單條功耗曲線功耗采樣點(diǎn)過多時(shí)尤其明顯，所以采用預(yù)處理技術(shù)在CPA前對功耗曲線進(jìn)行壓縮十分必要。

黃永遠(yuǎn)等[13]提出頻域輔助分析的濾波方法來濾除相關(guān)性低的部分，該方法使用低通濾波后的功耗曲線所執(zhí)行的攻擊效率最高?！赌芰糠治龉簟穂14]提出了最大值提取、原始整合、絕對值整合、平方和整合的方法來整合一個時(shí)鐘周期內(nèi)的點(diǎn)，達(dá)到壓縮曲線的目的。

引入主成分分析[15](Principal Component Analysis，PCA)到功耗分析的預(yù)處理階段，提取功耗信息中的主要成分，拋棄次要成分，再進(jìn)行相關(guān)功耗分析攻擊，從而提高攻擊效率。主成分分析在簡單功耗分析以及模板攻擊中有良好的效果，尤其是在模板攻擊中。

與模板攻擊和簡單功耗分析的閾值判別法不同，相關(guān)功耗分析攻擊通過計(jì)算猜測值與實(shí)測值的相關(guān)性來攻擊密鑰。而相關(guān)性的計(jì)算對具體的數(shù)值、度量單位、密碼算法的種類并不敏感，因此其應(yīng)用范圍以及攻擊效果比模板攻擊和簡單功耗分析優(yōu)秀。將主成分分析引入相關(guān)功耗分析攻擊具有更廣泛的實(shí)用意義，并以AES算法為例進(jìn)行了驗(yàn)證。

1 經(jīng)典AES算法的相關(guān)功耗分析攻擊

高級加密標(biāo)準(zhǔn)(Advanced Encryption Standard，AES)是最有代表性的分組密碼加密算法，在全球廣泛應(yīng)用并被多方分析。因此本文以AES為研究對象。

相關(guān)功耗分析攻擊利用是實(shí)際測量功耗與其對應(yīng)的操作數(shù)的漢明重量之間的相關(guān)性來破解密鑰。

詳細(xì)步驟如下：

(1)采集加密時(shí)的功耗信息得到實(shí)測功耗矩陣X。用示波器采集加密設(shè)備加密時(shí)的n(n∈N+)條功耗曲線，每條曲線有 p(p∈N+)個功耗點(diǎn)。將原始數(shù)據(jù)寫成矩陣形式，矩陣X每一行為一條功耗曲線，每列為按時(shí)間對齊的p個功耗采樣點(diǎn)的值：

(2)選擇算法中間值。根據(jù)文獻(xiàn)[14]的描述，中間值應(yīng)為明文與密鑰或密文與密鑰的函數(shù)值。現(xiàn)選取AES算法第一輪輪密鑰加操作后S盒的輸出值為算法中間值。如圖1所示，8 bit明文和8 bit密鑰在執(zhí)行輪密鑰加異或操作之后，得到 8 bit的結(jié)果，作為 S盒的輸入，查詢S盒，得到S盒的輸出。

圖1 AES算法S盒的輸入和輸出

(3)計(jì)算假設(shè)中間值。

對可能的密鑰假設(shè) k=(k1，k2，…，k256)，輸入明文 P= (P1，P2，…，Pn)，n為明文數(shù)量，計(jì)算假設(shè)中間值矩陣 V，大小為n×256。計(jì)算公式：

其中，符號SBOX(Pi，kj)為AES算法S盒替代操作函數(shù)。

(4)將假設(shè)中間值映射為假設(shè)功耗。

漢明重量是字符串中非零的元素個數(shù)。以漢明重量模型為功耗模型，給出相關(guān)功耗分析攻擊法映射的步驟，其中V為假設(shè)中間值矩陣，符號HW()表示計(jì)算輸入字符串漢明重量的功能函數(shù)。計(jì)算假設(shè)功耗矩陣H公式如下：

(5)計(jì)算出假設(shè)功耗矩陣H之后，計(jì)算假設(shè)功耗矩陣H及實(shí)測功耗矩陣X之間的相關(guān)性。Hi及Xj分別為列向量 Hi及Xj的算術(shù)平均值，i為可能的密鑰的數(shù)量，p為每條功耗曲線的采樣點(diǎn)數(shù)。結(jié)果得到相關(guān)系數(shù)矩陣R，大小為256×p。計(jì)算方法如下式：

其每一行對應(yīng)一個假設(shè)密鑰。首先找出每一行最大的相關(guān)系數(shù)值，得到256個相關(guān)系數(shù)值。接著對這256個相關(guān)系數(shù)值從大到小排序，最大的相關(guān)系數(shù)值對應(yīng)的密鑰值(即矩陣行號)為最佳密鑰候選值，次大的相關(guān)系數(shù)值對應(yīng)的密鑰值(即矩陣行號)為次佳候選值，以此類推。最終得到了一個字節(jié)密鑰對應(yīng)的256個候選密鑰值。選取最佳候選密鑰值為該字節(jié)密鑰的猜測值。對其他算法密鑰字節(jié)值都采用類似的方法進(jìn)行猜測。

2 基于主成分分析的AES相關(guān)功耗分析攻擊

與經(jīng)典相關(guān)功耗分析攻擊不同的是：經(jīng)典相關(guān)功耗分析攻擊直接使用實(shí)測功耗X進(jìn)行攻擊，而本方法先對實(shí)測功耗X進(jìn)行主成分分析預(yù)處理得到矩陣Y，再用矩陣Y進(jìn)行攻擊。

2.1 主成分分析

信號處理中，主成分分析被用來提取一個混合信號中的主成分[16]，拋棄次要成分，將復(fù)雜數(shù)據(jù)降維。它的優(yōu)點(diǎn)是簡單，無參數(shù)限制，可以方便地應(yīng)用于各種場合，因此應(yīng)用極其廣泛。

將原來p個指標(biāo)記為X1，X2，…，Xp。尋求這p個變量的線性組合 Y1，Y2，…，Ym，(m≤p)：Ym即為主成分分析后的主成分，用這m個主成分來表示原始數(shù)據(jù)中的大部分信息，用累積貢獻(xiàn)率來衡量這m主成分對原始數(shù)據(jù)信息的表示程度。其滿足如下性質(zhì)：

(1)主成分的方差Var(Yi)(i=1，2，…，p)依次遞減，重要性依次遞減，即：

(2)主成分之間互不相關(guān)，即無重疊的信息。協(xié)方差Cov有如下性質(zhì)：

性質(zhì)(2)保證每個主成分都是不相關(guān)的，即保證每個主成分都不包含其他主成分的信息，從而保證最大化降維。性質(zhì)(1)則保證能表示更多信息的成分在主成分編號中較小。

2.1.1 主成分分析功耗曲線預(yù)處理計(jì)算步驟

將第1小節(jié)采集到n條功耗曲線，每條曲線有p個功耗點(diǎn)的功耗矩陣X進(jìn)行預(yù)處理。步驟如下：

(1)將 X數(shù)據(jù)標(biāo)準(zhǔn)化[17]得到矩陣 A，和 S分別是矩陣X所有元素的算術(shù)平均值和方差：

(2)建立矩陣A的協(xié)方差矩陣Cov。其中ai和aj分別為矩陣A的i列和j列的算術(shù)平均值，公式如下：

(3)求協(xié)方差矩陣Cov的特征根 λ1，λ2，…，λp及相應(yīng)的單位特征向量：

(4)計(jì)算主成分。矩陣 A=[A1，A2，…，Ap]，列矩陣 Ai為原始數(shù)據(jù)第i個列。Yi為第i號主成分，即矩陣Y的第i列：

T即為計(jì)算主成分的轉(zhuǎn)換矩陣。

一般取累計(jì)貢獻(xiàn)率達(dá) 85%～95%的特征值 λ1，λ2，…，λm所對應(yīng)的第 1、第 2、…、第m(m≤p)個主成分。

2.1.2 主成分的貢獻(xiàn)率

主成分分析的目的是減少變量的個數(shù)，所以一般不會使用所有p個主成分的，忽略一些帶有較小方差的主成分將不會給總方差帶來太大的影響。

2.2 實(shí)驗(yàn)

2.2.1 實(shí)驗(yàn)環(huán)境

加密設(shè)備用Atmel ATME0A16A為硬件仿真平臺，采用 Tektronix DPO4032示波器采集硬件仿真平臺加密隨機(jī)明文時(shí)的功耗。選取AES算法第一輪S盒輸出做中間值，用漢明重量做功耗模型進(jìn)行相關(guān)功耗分析攻擊。

2.2.2 基于主成分分析的功耗曲線預(yù)處理

使用示波器以 100 MHz采樣頻率采集 5組樣本數(shù)據(jù)，每組樣本有 10 000條功耗曲線，每條曲線 6 700個功耗采樣點(diǎn)。在上文硬件平臺下的相關(guān)功耗攻擊出全部16 B密鑰需要100條左右曲線，因此樣本量選擇 10 000能保證實(shí)驗(yàn)結(jié)果的穩(wěn)定可靠。對5組樣本分別進(jìn)行主成分分析預(yù)處理，為下一步三種方案對比實(shí)驗(yàn)方案做準(zhǔn)備。

按照2.1.1節(jié)主成分分析功耗曲線預(yù)處理計(jì)算步驟進(jìn)行預(yù)處理：

(1)n=10 000條功耗曲線，每條曲線有p=6 700個功耗采集點(diǎn)的值，原始數(shù)據(jù)寫成矩陣形式，得到矩陣X：

每一行是一條曲線樣本，每一列是對應(yīng)時(shí)刻采樣點(diǎn)的功耗值。對矩陣X進(jìn)行標(biāo)準(zhǔn)化。

(2)建立變量的協(xié)方差矩陣 Cov，求協(xié)方差矩陣 Cov的特征根 λ1，λ2， …，λ6700， 及相應(yīng)的單位特征向量：T1，T2，…，T6700。求得轉(zhuǎn)換矩陣 T=[T1，T2，…，T6700]。貢獻(xiàn)率向量 L=[λ1，λ2，…，λ6700]。

(3)矩陣Y=T'X，得到矩陣Y：

矩陣Y的每一行是主成分分析處理后的一條曲線樣本，每列都表示一個主成分，第一列為一號主成分，第二列為二號主成分，依次類推。

向量 L=[λ1，λ2，…，λ6700]，λp為第 p號主成分的貢獻(xiàn)率，用2.1.2節(jié)的方法計(jì)算累積貢獻(xiàn)率曲線，把 Y矩陣的每一行回寫為功耗曲線的形式，預(yù)處理完成。

預(yù)處理前的曲線示例如圖2所示，主成分分析后的曲線示例如圖3所示。

通過圖3發(fā)現(xiàn)幅值大的功耗點(diǎn)都是前若干主成分，越靠后的主成分值越小并有向零趨近的趨勢，結(jié)合圖4累積貢獻(xiàn)率可以發(fā)現(xiàn)前若干號主成分貢獻(xiàn)率明顯高于后面的主成分，該結(jié)果符合進(jìn)行PCA后的理論預(yù)期。

用2.1.2節(jié)的方法計(jì)算累積貢獻(xiàn)率如圖4所示。

圖2 原始功耗曲線示例

圖3 預(yù)處理后功耗曲線示例

圖4 累積貢獻(xiàn)率

實(shí)驗(yàn)結(jié)果表明，累積貢獻(xiàn)率迅速上升到0.8即80%以上，前35號主成分就能表示全部6 700個功耗點(diǎn)80.05%的信息，前141號主成分累積貢獻(xiàn)率為85.01%。多次實(shí)驗(yàn)顯示，相關(guān)性高的主成分集中在前若干主成分中，35～141號主成分只包含5%的信息。原始采樣點(diǎn)為6 700，為了實(shí)驗(yàn)對比的方便，選擇前67號主成分對比實(shí)驗(yàn)，此時(shí)單條曲線使用的點(diǎn)數(shù)量為原始點(diǎn)數(shù)的1%。

2.2.3 對比實(shí)驗(yàn)

為了驗(yàn)證主成分分析預(yù)處理的效果，設(shè)計(jì)3種實(shí)驗(yàn)方案進(jìn)行對比。

實(shí)驗(yàn)方案1：對原始功耗曲線進(jìn)行相關(guān)功耗分析攻擊，此時(shí)使用原始功耗矩陣X作為分析的功耗數(shù)據(jù)。

實(shí)驗(yàn)方案2：為了找出主成分分析預(yù)處理對攻擊成功率的影響，取預(yù)處理后的全部6 700號主成分進(jìn)行相關(guān)功耗分析攻擊，即此時(shí)使用矩陣Y作為分析的功耗數(shù)據(jù)。

實(shí)驗(yàn)方案3：為了驗(yàn)證單條曲線使用的點(diǎn)數(shù)量為原始點(diǎn)數(shù)的1%時(shí)的攻擊效果，預(yù)處理后曲線取前67號主成分進(jìn)行相關(guān)功耗分析攻擊，即此時(shí)使用矩陣Y的前67列作為分析的功耗數(shù)據(jù)。

實(shí)驗(yàn)結(jié)果如表1、表2和表3所示。

表1中的功耗點(diǎn)位置表示功耗曲線中與當(dāng)前字節(jié)密鑰相關(guān)系數(shù)最高的點(diǎn)，即猜測出正確密鑰的點(diǎn)。

實(shí)驗(yàn)方案1和實(shí)驗(yàn)方案2對比，區(qū)別是實(shí)驗(yàn)2比實(shí)驗(yàn)1多做了主成分分析預(yù)處理。結(jié)果說明主成分分析后若是依然采用全部 6 700個點(diǎn)進(jìn)行相關(guān)功耗分析攻擊，雖然都能攻擊出全部16 B密鑰，但是所需曲線上升至565，相關(guān)系數(shù)下降了 0.32，相關(guān)性降低了。但是，中間值相關(guān)性最高的點(diǎn)全部在前111號主成分中，說明主成分分析有效地將信息集中到了前111號主成分。

表1 AES16字節(jié)密鑰猜測正確對應(yīng)功耗點(diǎn)位置

表2 AES16字節(jié)密鑰猜測正確時(shí)的相關(guān)系數(shù)

表3 三種實(shí)驗(yàn)方案猜測正確密鑰平均所需曲線條數(shù)

實(shí)驗(yàn)方案3和實(shí)驗(yàn)方案2的區(qū)別是：實(shí)驗(yàn)方案2使用了全部的6 700號主成分，而實(shí)驗(yàn)方案3只使用了前67號主成分就能恢復(fù)出全部的16 B密鑰，且只用了445條曲線。再次說明主成分分析有效地把多數(shù)信息集中到了前若干主成分，主成分分析的降維效果顯著。

在2.1.1的第3步中得出第4步計(jì)算主成分時(shí)所用的轉(zhuǎn)換矩陣T，在保證采樣環(huán)境不變的情況下再次進(jìn)行主成分分析預(yù)處理時(shí)，轉(zhuǎn)換矩陣T可以作為先驗(yàn)知識來使用，即再次進(jìn)行同樣環(huán)境的功耗數(shù)據(jù)預(yù)處理時(shí)只需進(jìn)行第4步。而該步驟是一個簡單的線性運(yùn)算，其復(fù)雜度低于計(jì)算相關(guān)系數(shù)。為了比較實(shí)驗(yàn)方案3和實(shí)驗(yàn)方案1的計(jì)算量，假設(shè)該步驟和相關(guān)系數(shù)計(jì)算花費(fèi)一樣的時(shí)間，由于先驗(yàn)知識可以預(yù)處理 1 000條，取前 67個主成分即可穩(wěn)定破解密鑰，此時(shí)處理的點(diǎn)數(shù)為：

相關(guān)功耗分析攻擊會計(jì)算每個功耗點(diǎn)和中間值的相關(guān)性。設(shè)N為CPA成功時(shí)所用的功耗曲線條數(shù)，P為每條曲線的實(shí)際使用的點(diǎn)數(shù)，攻擊程序分析的功耗點(diǎn)數(shù)為：S=N×P。

實(shí)驗(yàn)方案1分析的功耗點(diǎn)數(shù)為：

實(shí)驗(yàn)方案3分析的功耗點(diǎn)數(shù)為：

對比實(shí)驗(yàn)方案3和實(shí)驗(yàn)方案1花費(fèi)的時(shí)間：

實(shí)驗(yàn)方案1比實(shí)驗(yàn)方案3多計(jì)算了4.15倍的功耗點(diǎn)。因此主成分分析預(yù)處理在AES的相關(guān)功耗分析攻擊中是能有效的減少攻擊時(shí)間的。

3 結(jié)論

針對相關(guān)功耗分析攻擊中，當(dāng)功耗曲線的功耗采樣點(diǎn)較多時(shí)攻擊速度緩慢的問題，引入了基于主成分分析的預(yù)處理方法，提取功耗信息中的主成分，減少相關(guān)功耗分析攻擊中分析量。引入主成分分析的相關(guān)功耗分析攻擊與經(jīng)典相關(guān)功耗分析攻擊的對比實(shí)驗(yàn)結(jié)果表明，該方法可以提高攻擊效率。

[1]KOCHER P C.Timing attacks on implementations of diffiehellman，RSA，DSS，and other systems[A].CRYPTO 1996[C]. Berlin：Springer，1996：104-113.

[2]KOCHER P C，JAFFE J，JUN B.Differential power analysis[A]. CRYPTO 1999[C].Berlin：Springer，1999：388-397.

[3]QUISQUATER J，SAMYDE D.Electromagnetic analysis(EMA)：measures and countermeasures for smart cards[A].E-Smart 2001[C].Berlin：Springer，2001：200-210.

[4]Mayer Sommer R.Smartly analyzing the simplicity and the power of simple power analysis on smartcards[C].Cryptographic Hardware and Embedded Systems-CHES 2000，Springer Berlin Heidelberg，2000：78-92.

[5]NOVAK R.SPA-based adaptive chosen-ciphertext attack on RSA implementation[C].Public Key Cryptography，Springer Berlin Heidelberg，2002：252-262.

[6]LEMKE K，PAAR C，WOLF M.Embedded security in cars[M]. New York：Springer，2006.

[7]MESSERGES T S.Securing the AES finalists against power analysis attacks[C].Fast Software Encryption.Springer Berlin Heidelberg，2001：150-164.

[8]CHARI S，RAO J R，ROHATGI P.Template attacks[A]. CHES 2002[C].Berlin：Springer，2002：13-28.

[9]PAN W，MARNANE W P.A correlation power analysis attack against tare pairing on FPGA[M].New York：Springer，2011：340-349.

[10]嚴(yán)迎建，樊海鋒，徐金甫，等.針對 DES密碼芯片的CPA攻擊仿真[J].電子技術(shù)應(yīng)用，2009(7).

[11]KOEUNE F，STANDAERT F X.A tutorial on physical security and side-channel attacks[M].New York：SpringerBerlin Heidelberg，2005：78-108.

[12]SEHIMMEL O，DUPLYS P，BOEH1 E，et a1.Correlation power analysis in frequency domain[J].COSADE，2010.

[13]黃永遠(yuǎn)，陳運(yùn)，陳俊，等.運(yùn)用頻域輔助分析的 AES算法相關(guān)功耗攻擊[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版)，2014，51(3).

[14]Stefan Mangard，Elisabeth Oswald，Thomas Popp.能量分析攻擊[M].北京：科學(xué)出版社，2010.

[15]魏艷華，王丙參，田玉柱.主成分分析與因子分析的比較研究[J].天水師范學(xué)院學(xué)報(bào)，2009(2).

[16]JOLLIFFE I T.Principal component analysis[A].ACM Computing Surveys[C].New York：Springer Verlag，1986.

[17]張立軍，袁能文.線性綜合評價(jià)模型中指標(biāo)標(biāo)準(zhǔn)化方法的比較與選擇[J].統(tǒng)計(jì)與信息論壇，2010(8).

Correlation power analysis for AES based-on principal component analysis

Cai Chen1，Chen Yun1，2，Wan Wunan1，Chen Jun1，Hu Xiaoxia1
(1.Applied Cryptography Institute，Chengdu University of Information Technology，Chengdu 610225，China; 2.School of Communication Engineering，University of Electronic Science and Technology of China，Chengdu 610054 China)

When power points in a power curve are too much，correlation power analysis is often slow.Power curve preprocessing based-on principal component analysis was proposed to remove low crosscorrelation points and reduce the power points of actual analysis.Taking the advanced encryption standard cryptographic algorithm as the target algorithm，correlation power analysis for AES based-on principal component analysis was studied.Experiment results demonstrate that the pretreatment of the principal component analysis focus on information to the previous 67th principal component.The proposed techniques can effectively reduce 3/4 power points of actual analysis.

cryptanalysis;side channel attack;correlation power analysis;principal component analysis;PCA;AES

TN918.91

A

10.16157/j.issn.0258-7998.2015.08.029

蔡琛，陳運(yùn)，萬武南，等.基于主成分分析的AES算法相關(guān)功耗分析攻擊[J].電子技術(shù)應(yīng)用，2015，41(8)：101-105.

英文引用格式:Cai Chen，Chen Yun，Wan Wunan，et al.Correlation power analysis for AES based-on principal component analysis[J].Application of Electronic Technique，2015，41(8)：101-105.

2015-04-27)(

2015-04-02)

蔡琛(1990-)，男，碩士研究生，主要研究方向：邊信道安全。

陳運(yùn)(1958-)，女，教授，主要研究方向：邊信道安全。

萬武南(1978-)，女，副教授，主要研究方向：邊信道安全。

四川省科技支撐計(jì)劃重點(diǎn)資助項(xiàng)目(2012GZ0017)