文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.2015.08.029
中文引用格式: 蔡琛,陳運,,萬武南,,等. 基于主成分分析的AES算法相關功耗分析攻擊[J].電子技術應用,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.
0 引言
密碼設備運行算法時產生時間[1]、功耗[2],、電磁[3]等邊信息泄露,,泄露的邊信息與加密運算中的操作或數(shù)據(jù)存在相關性,利用這些邊信息攻擊密鑰的方法叫邊信道攻擊,。功耗分析攻擊(Power Attacks,,PA)[4-5]是其中一種邊信道攻擊(Side Channel Attack,,SCA)[6-7]方法。攻擊者采集密碼設備運行時的功耗,,通過對功耗信息進行分析來破解密鑰,。在信息安全形勢日漸嚴峻的今天,邊信道安全越來越被學術和工業(yè)界重視,。
功耗分析攻擊主要分為簡單功耗分析攻擊(Simple Power Analysis,,SPA)[2]、差分功耗分析攻擊(Differential Power Analysis,,DPA)[2],、模板攻擊(Template Attack,TA)[8]和相關功耗分析攻擊(Correlation Power Analysis,,CPA)[9-10],。CPA是上述方法中對功耗信息利用較好的方法[11-12]。然而,,相關功耗分析攻擊中計算相關系數(shù)相當耗時,,尤其在單條功耗曲線功耗采樣點過多時尤其明顯,所以采用預處理技術在CPA前對功耗曲線進行壓縮十分必要,。
黃永遠等[13]提出頻域輔助分析的濾波方法來濾除相關性低的部分,,該方法使用低通濾波后的功耗曲線所執(zhí)行的攻擊效率最高?!赌芰糠治龉簟?sup>[14]提出了最大值提取,、原始整合、絕對值整合,、平方和整合的方法來整合一個時鐘周期內的點,,達到壓縮曲線的目的。
引入主成分分析[15](Principal Component Analysis,,PCA)到功耗分析的預處理階段,,提取功耗信息中的主要成分,拋棄次要成分,,再進行相關功耗分析攻擊,,從而提高攻擊效率。主成分分析在簡單功耗分析以及模板攻擊中有良好的效果,,尤其是在模板攻擊中,。
與模板攻擊和簡單功耗分析的閾值判別法不同,相關功耗分析攻擊通過計算猜測值與實測值的相關性來攻擊密鑰,。而相關性的計算對具體的數(shù)值,、度量單位、密碼算法的種類并不敏感,因此其應用范圍以及攻擊效果比模板攻擊和簡單功耗分析優(yōu)秀,。將主成分分析引入相關功耗分析攻擊具有更廣泛的實用意義,并以AES算法為例進行了驗證,。
1 經典AES算法的相關功耗分析攻擊
高級加密標準(Advanced Encryption Standard,,AES)是最有代表性的分組密碼加密算法,在全球廣泛應用并被多方分析,。因此本文以AES為研究對象,。
相關功耗分析攻擊利用是實際測量功耗與其對應的操作數(shù)的漢明重量之間的相關性來破解密鑰。
詳細步驟如下:
(1)采集加密時的功耗信息得到實測功耗矩陣X,。用示波器采集加密設備加密時的n(n∈N+)條功耗曲線,,每條曲線有p(p∈N+)個功耗點。將原始數(shù)據(jù)寫成矩陣形式,,矩陣X每一行為一條功耗曲線,,每列為按時間對齊的p個功耗采樣點的值:
(2)選擇算法中間值。根據(jù)文獻[14]的描述,,中間值應為明文與密鑰或密文與密鑰的函數(shù)值?,F(xiàn)選取AES算法第一輪輪密鑰加操作后S盒的輸出值為算法中間值。如圖1所示,,8 bit明文和8 bit密鑰在執(zhí)行輪密鑰加異或操作之后,,得到8 bit的結果,作為S盒的輸入,,查詢S盒,,得到S盒的輸出。
(3)計算假設中間值,。
對可能的密鑰假設k=(k1,,k2,…,,k256),,輸入明文P=(P1,P2,,…,,Pn),n為明文數(shù)量,,計算假設中間值矩陣V,,大小為n×256。計算公式:
其中,,符號SBOX(Pi,,kj)為AES算法S盒替代操作函數(shù)。
(4)將假設中間值映射為假設功耗。
漢明重量是字符串中非零的元素個數(shù),。以漢明重量模型為功耗模型,,給出相關功耗分析攻擊法映射的步驟,其中V為假設中間值矩陣,,符號HW()表示計算輸入字符串漢明重量的功能函數(shù),。計算假設功耗矩陣H公式如下:
其每一行對應一個假設密鑰。首先找出每一行最大的相關系數(shù)值,,得到256個相關系數(shù)值,。接著對這256個相關系數(shù)值從大到小排序,最大的相關系數(shù)值對應的密鑰值(即矩陣行號)為最佳密鑰候選值,,次大的相關系數(shù)值對應的密鑰值(即矩陣行號)為次佳候選值,,以此類推。最終得到了一個字節(jié)密鑰對應的256個候選密鑰值,。選取最佳候選密鑰值為該字節(jié)密鑰的猜測值,。對其他算法密鑰字節(jié)值都采用類似的方法進行猜測。
2 基于主成分分析的AES相關功耗分析攻擊
與經典相關功耗分析攻擊不同的是:經典相關功耗分析攻擊直接使用實測功耗X進行攻擊,,而本方法先對實測功耗X進行主成分分析預處理得到矩陣Y,,再用矩陣Y進行攻擊。
2.1 主成分分析
信號處理中,,主成分分析被用來提取一個混合信號中的主成分[16],,拋棄次要成分,將復雜數(shù)據(jù)降維,。它的優(yōu)點是簡單,,無參數(shù)限制,可以方便地應用于各種場合,,因此應用極其廣泛,。
將原來p個指標記為X1,X2,,…,,Xp。尋求這p個變量的線性組合Y1,,Y2,,…,Ym,,(m≤p):Ym即為主成分分析后的主成分,,用這m個主成分來表示原始數(shù)據(jù)中的大部分信息,用累積貢獻率來衡量這m主成分對原始數(shù)據(jù)信息的表示程度,。其滿足如下性質:
(1)主成分的方差Var(Yi)(i=1,,2,,…,p)依次遞減,,重要性依次遞減,,即:
(2)主成分之間互不相關,即無重疊的信息,。協(xié)方差Cov有如下性質:
性質(2)保證每個主成分都是不相關的,,即保證每個主成分都不包含其他主成分的信息,從而保證最大化降維,。性質(1)則保證能表示更多信息的成分在主成分編號中較小。
2.1.1 主成分分析功耗曲線預處理計算步驟
將第1小節(jié)采集到n條功耗曲線,,每條曲線有p個功耗點的功耗矩陣X進行預處理,。步驟如下:
T即為計算主成分的轉換矩陣。
一般取累計貢獻率達85%~95%的特征值λ1,,λ2,,…,λm所對應的第1,、第2,、…、第m(m≤p)個主成分,。
2.1.2 主成分的貢獻率
主成分分析的目的是減少變量的個數(shù),,所以一般不會使用所有p個主成分的,忽略一些帶有較小方差的主成分將不會給總方差帶來太大的影響,。
這里稱為第k(k>0)個主成分Yk的貢獻率,。第一主成分的貢獻率最大,這表明Y1綜合原始變量X1,,X2,,…,Xp的能力最強,,而Y2,,Y3,…,,Yp的綜合能力依次遞減,。若只取m個主成分,則稱為主成分Y1,,…,,Ym的累計貢獻率,累計貢獻率表明Y1,,…,,Ym綜合X1,X2,…,,Xp的能力,。通常取m,使得累計貢獻率達到一個較高的百分數(shù),,如85%以上,。
2.2 實驗
2.2.1 實驗環(huán)境
加密設備用Atmel ATME0A16A為硬件仿真平臺,采用Tektronix DPO4032示波器采集硬件仿真平臺加密隨機明文時的功耗,。選取AES算法第一輪S盒輸出做中間值,,用漢明重量做功耗模型進行相關功耗分析攻擊。
2.2.2 基于主成分分析的功耗曲線預處理
使用示波器以100 MHz采樣頻率采集5組樣本數(shù)據(jù),,每組樣本有10 000條功耗曲線,,每條曲線6 700個功耗采樣點。在上文硬件平臺下的相關功耗攻擊出全部16 B密鑰需要100條左右曲線,,因此樣本量選擇10 000能保證實驗結果的穩(wěn)定可靠,。對5組樣本分別進行主成分分析預處理,為下一步三種方案對比實驗方案做準備,。
按照2.1.1節(jié)主成分分析功耗曲線預處理計算步驟進行預處理:
(1)n=10 000條功耗曲線,,每條曲線有p=6 700個功耗采集點的值,原始數(shù)據(jù)寫成矩陣形式,,得到矩陣X:
每一行是一條曲線樣本,,每一列是對應時刻采樣點的功耗值。對矩陣X進行標準化,。
(2)建立變量的協(xié)方差矩陣Cov,,求協(xié)方差矩陣Cov的特征根λ1,λ2,,…,,λ6 700,及相應的單位特征向量:T1,,T2,,…,T6 700,。求得轉換矩陣T=[T1,,T2,…,,T6 700],。貢獻率向量L=[λ1,λ2,,…,,λ6 700],。
(3)矩陣Y=T′X,得到矩陣Y:
矩陣Y的每一行是主成分分析處理后的一條曲線樣本,,每列都表示一個主成分,,第一列為一號主成分,第二列為二號主成分,,依次類推,。
向量L=[λ1,λ2,,…,,λ6 700],λp為第p號主成分的貢獻率,,用2.1.2節(jié)的方法計算累積貢獻率曲線,,把Y矩陣的每一行回寫為功耗曲線的形式,預處理完成,。
預處理前的曲線示例如圖2所示, 主成分分析后的曲線示例如圖3所示,。
通過圖3發(fā)現(xiàn)幅值大的功耗點都是前若干主成分,,越靠后的主成分值越小并有向零趨近的趨勢,結合圖4累積貢獻率可以發(fā)現(xiàn)前若干號主成分貢獻率明顯高于后面的主成分,,該結果符合進行PCA后的理論預期,。
用2.1.2節(jié)的方法計算累積貢獻率如圖4所示。
實驗結果表明,,累積貢獻率迅速上升到0.8即80%以上,,前35號主成分就能表示全部6 700個功耗點80.05%的信息,前141號主成分累積貢獻率為85.01%,。多次實驗顯示,,相關性高的主成分集中在前若干主成分中,35~141號主成分只包含5%的信息,。原始采樣點為6 700,,為了實驗對比的方便,選擇前67號主成分對比實驗,,此時單條曲線使用的點數(shù)量為原始點數(shù)的1%,。
2.2.3 對比實驗
為了驗證主成分分析預處理的效果,設計3種實驗方案進行對比,。
實驗方案1:對原始功耗曲線進行相關功耗分析攻擊,,此時使用原始功耗矩陣X作為分析的功耗數(shù)據(jù)。
實驗方案2:為了找出主成分分析預處理對攻擊成功率的影響,,取預處理后的全部6 700號主成分進行相關功耗分析攻擊,,即此時使用矩陣Y作為分析的功耗數(shù)據(jù),。
實驗方案3:為了驗證單條曲線使用的點數(shù)量為原始點數(shù)的1%時的攻擊效果,預處理后曲線取前67號主成分進行相關功耗分析攻擊,,即此時使用矩陣Y的前67列作為分析的功耗數(shù)據(jù),。
實驗結果如表1、表2和表3所示,。
表1中的功耗點位置表示功耗曲線中與當前字節(jié)密鑰相關系數(shù)最高的點,,即猜測出正確密鑰的點。
實驗方案1和實驗方案2對比,,區(qū)別是實驗2比實驗1多做了主成分分析預處理,。結果說明主成分分析后若是依然采用全部6 700個點進行相關功耗分析攻擊,雖然都能攻擊出全部16 B密鑰,,但是所需曲線上升至565,,相關系數(shù)下降了0.32,相關性降低了,。但是,,中間值相關性最高的點全部在前111號主成分中,說明主成分分析有效地將信息集中到了前111號主成分,。
實驗方案3和實驗方案2的區(qū)別是:實驗方案2使用了全部的6 700號主成分,,而實驗方案3只使用了前67號主成分就能恢復出全部的16 B密鑰,且只用了445條曲線,。再次說明主成分分析有效地把多數(shù)信息集中到了前若干主成分,,主成分分析的降維效果顯著。
在2.1.1的第3步中得出第4步計算主成分時所用的轉換矩陣T,,在保證采樣環(huán)境不變的情況下再次進行主成分分析預處理時,,轉換矩陣T可以作為先驗知識來使用,即再次進行同樣環(huán)境的功耗數(shù)據(jù)預處理時只需進行第4步,。而該步驟是一個簡單的線性運算,,其復雜度低于計算相關系數(shù)。為了比較實驗方案3和實驗方案1的計算量,,假設該步驟和相關系數(shù)計算花費一樣的時間,,由于先驗知識可以預處理1 000條,取前67個主成分即可穩(wěn)定破解密鑰,,此時處理的點數(shù)為:
S0=1 000×67=67 000
相關功耗分析攻擊會計算每個功耗點和中間值的相關性,。設N為CPA成功時所用的功耗曲線條數(shù),P為每條曲線的實際使用的點數(shù),,攻擊程序分析的功耗點數(shù)為:S=N×P,。
實驗方案1分析的功耗點數(shù)為:
S1=60×6 700=402 000
實驗方案3分析的功耗點數(shù)為:
S3=445×67=29 815
對比實驗方案3和實驗方案1花費的時間:
S1/(S3+S0)=4.15
實驗方案1比實驗方案3多計算了4.15倍的功耗點。因此主成分分析預處理在AES的相關功耗分析攻擊中是能有效的減少攻擊時間的,。
3 結論
針對相關功耗分析攻擊中,,當功耗曲線的功耗采樣點較多時攻擊速度緩慢的問題,,引入了基于主成分分析的預處理方法,提取功耗信息中的主成分,,減少相關功耗分析攻擊中分析量,。引入主成分分析的相關功耗分析攻擊與經典相關功耗分析攻擊的對比實驗結果表明,該方法可以提高攻擊效率,。
參考文獻
[1] KOCHER P C.Timing attacks on implementations of diffie-hellman,,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] 嚴迎建,,樊海鋒,,徐金甫,等.針對DES密碼芯片的CPA攻擊仿真[J].電子技術應用,,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] 黃永遠,,陳運,,陳俊,等.運用頻域輔助分析的AES算法相關功耗攻擊[J].四川大學學報(自然科學版),,2014,,51(3).
[14] Stefan Mangard,Elisabeth Oswald,,Thomas Popp.能量分析攻擊[M].北京:科學出版社,,2010.
[15] 魏艷華,王丙參,,田玉柱.主成分分析與因子分析的比較研究[J].天水師范學院學報,,2009(2).
[16] JOLLIFFE I T.Principal component analysis[A].ACM Computing Surveys[C].New York:Springer Verlag,1986.
[17] 張立軍,,袁能文.線性綜合評價模型中指標標準化方法的比較與選擇[J].統(tǒng)計與信息論壇,,2010(8).