基于FPGA實(shí)現(xiàn)AES的側(cè)信道碰撞攻擊

郭建飛，王 忠，嚴(yán)迎建，郭朋飛

（解放軍信息工程大學(xué)，河南 鄭州 450004）

0 引言

2003年Schramm等在FSE上提出碰撞攻擊[1]，參考文獻(xiàn)[2]首次將側(cè)信道碰撞應(yīng)用到AES上。隨后，Bogdanov[3]對AES的側(cè)信道碰撞攻擊進(jìn)行了改進(jìn)，Moradi等人[4]提出對使用掩碼S盒的AES進(jìn)行碰撞攻擊。側(cè)信道碰撞攻擊不需要依賴任何泄露模型，只需擁有識別攻擊點(diǎn)在能量跡中位置的能力。

本文在對側(cè)信道碰撞攻擊技術(shù)研究的基礎(chǔ)上，提出了方差檢查技術(shù)，并利用基于相關(guān)系數(shù)的碰撞檢測方法，對AES實(shí)施了攻擊。

1 碰撞攻擊流程及AES碰撞分析

1.1 碰撞攻擊流程

碰撞攻擊可按圖1所示的步驟實(shí)施。側(cè)信道碰撞攻擊技術(shù)可分為4個階段：碰撞分析、側(cè)信息測量、碰撞檢測和密鑰恢復(fù)。其中，碰撞分析和碰撞檢測為側(cè)信道碰撞攻擊的關(guān)鍵，本文主要對這兩個階段進(jìn)行研究。

1.2 AES碰撞分析及密鑰恢復(fù)

圖1 側(cè)信道碰撞攻擊流程圖

本文選擇AES進(jìn)行側(cè)信道碰撞攻擊的研究。記K={kj}1j=61，kj∈F28，(j=1，2，…，16)為初始密鑰，Pi={pij}1j=61，pij∈F28，(j=1，2，…，16)為明文，其中 pij為明文的第 j個字節(jié)，i表示AES執(zhí)行的序號。

如圖2所示，假設(shè)在AES第一輪S盒中的第4個字節(jié)和第11個字節(jié)位置處發(fā)生一次碰撞，則：

圖2 AES執(zhí)行過程中發(fā)生的線性碰撞

由于S盒是雙射函數(shù)，可獲得一個關(guān)于密鑰的線性方程：

針對第一輪第一個S盒與其他S盒的碰撞，理想情況下可得到如下方程組：

即第一輪子密鑰字節(jié) k2，…，k16均可由k1表示，然后在給定明密文對的條件下遍歷 k1，就可確定 k1，根據(jù)k1和方程組(3)就可求出其他比特密鑰。

2 算法實(shí)現(xiàn)及能量采集

2.1 算法實(shí)現(xiàn)

對面積和功耗有較高要求的分組密碼算法在硬件實(shí)現(xiàn)時，會對S盒采取復(fù)用[4-6]，這為側(cè)信道碰撞攻擊的實(shí)施提供了契機(jī)。本文以如圖3所示AES為攻擊對象。

圖中，控制模塊控制寄存器組1每一個時鐘周期輸出輸入選擇模塊結(jié)果的8位，最后一圈時，寄存器組1中的128比特數(shù)值為密文；寄存器組2用于寄存16個時鐘周期中S盒運(yùn)算的輸出。

2.2 能量采集平臺

采用如圖4所示的能量采集平臺[7]對本文的研究進(jìn)行驗(yàn)證。其中，PC對控制模塊和密碼芯片進(jìn)行信息配置，并對示波器采集到的波形數(shù)據(jù)進(jìn)行分析；控制模塊控制密碼芯片的加解密運(yùn)算；信號發(fā)生器提供系統(tǒng)時鐘；密碼芯片中下載待攻擊密碼算法；示波器采集密碼芯片的電磁輻射信息。

圖4 能量采集平臺

3 基于相關(guān)系數(shù)的碰撞檢測方法

本文提出通過計算能量跡中每一采樣點(diǎn)的方差來識別攻擊點(diǎn)的方差檢查技術(shù)，并利用基于相關(guān)系數(shù)的碰撞檢測方法對其進(jìn)行了驗(yàn)證。

3.1 方差檢查

概率論上，方差用于度量隨機(jī)變量和其數(shù)學(xué)期望之間的偏離程度，隨機(jī)變量X的方差如式(4)所示：

當(dāng)不同算法操作處理不同輸入時，對應(yīng)的側(cè)信息有差別，基于此，可利用方差來檢查電磁曲線中碰撞攻擊點(diǎn)的位置信息，具體步驟如下：

(1)針對某一攻擊點(diǎn)，遍歷所有對應(yīng)明文位作為能量采集平臺中算法的明文輸入；

(2)利用能量采集平臺采集對應(yīng)明文的電磁曲線波形；

(3)對電磁曲線中每一個采樣點(diǎn)進(jìn)行方差計算。

具體地，針對AES算法，將第一輪第一個S盒視為碰撞攻擊點(diǎn)，對其進(jìn)行方差檢查。

首先，遍歷對應(yīng)第一個S盒輸入的8位明文；然后，利用能量采集平臺重復(fù)采集y次對應(yīng)遍歷明文的電磁曲線，對每個明文對應(yīng)的電磁曲線做平均，得到28條平均電磁曲線，記第i條平均電磁曲線為：

其中，Ti，j為第 j(1≤j≤m)個采樣點(diǎn)值，m 為采樣點(diǎn)個數(shù)；則第j個采樣點(diǎn)的方差可用下式計算：

利用式(6)對28條平均電磁曲線計算每一個采樣點(diǎn)的方差，就可得到對應(yīng)第一個S盒的方差圖。

3.2 碰撞檢測方法

每條跡Ti都包含第一輪中每個S盒計算時泄露的電磁信息，當(dāng)S盒計算在兩個字節(jié)位置j1=a和j2=b碰撞時，可得 sia1=sib2，則pia1⊕ka=pib2⊕kb。將輸入差分定義為Δa，b=pia1⊕pib2=ka⊕kb。對 于 固 定 的 密 鑰 ， 差 分 Δa，b=ka⊕kb是固定的。 因此當(dāng) pa=α，pb=α⊕Δa，b時，碰撞就會發(fā)生。圖 5給出了猜測 Δa，b=Δg的相關(guān)系數(shù)計算方法。 其中，T1，T2，…，Tn表示輸入明文為 P1，P2，…，Pn時對應(yīng)的平 均 能 量 跡 ；T1′，T2′， … ，Tn′表 示 輸 入 明 文 為 P1⊕Δg，P⊕Δ ， …，P⊕Δ 時對應(yīng)的平均能量跡；Ma和 Ma⊕Δg分2gngab別表示平均跡矩陣；ρ(Ma，Ma⊕Δg)表 示 對 Ma和 Ma⊕Δg在abab每一個采樣點(diǎn)得到的相關(guān)系數(shù)。

圖5 基于相關(guān)系數(shù)的碰撞檢測方法示意圖

對應(yīng)第j個采樣點(diǎn)的相關(guān)系數(shù)可利用下式進(jìn)行計算：

遍歷 Δa，b，根據(jù)式(7)對每個采樣點(diǎn)進(jìn)行相關(guān)系數(shù)計算可以得到n條相關(guān)系數(shù)曲線，對應(yīng)相關(guān)系數(shù)最大的Δa，b即為正確差。

4 攻擊驗(yàn)證

本節(jié)從實(shí)測驗(yàn)證、方差計算、相關(guān)系數(shù)計算三個方面對AES的實(shí)現(xiàn)進(jìn)行攻擊驗(yàn)證。

4.1 實(shí)測驗(yàn)證

按照側(cè)信道信息采集平臺的工作流程，采集AES密碼芯片運(yùn)行時16個S盒運(yùn)算的泄露信息如圖6所示。

圖6 AES S盒運(yùn)算時的電磁曲線

從圖6可以看出示波器上的能量跡與AES的16個時鐘周期的S盒運(yùn)算十分吻合。因此，能量采集平臺下觀測到的能量跡曲線可以作為攻擊的信息源。

4.2 方差計算

如3.1節(jié)的描述對個別S盒發(fā)生泄露的位置進(jìn)行檢測。 選擇兩個 S 盒為碰撞點(diǎn)時，固定 α∈GF(28)，遍歷 Δa，b，對每個明文重復(fù)50次測量，對應(yīng)每個S盒可各得50×28條跡，對兩組28條平均跡分別求方差，得到圖7所示兩個方差圖。

圖7 第一輪前兩個S盒的方差圖

從圖中可以看出，在第110個采樣點(diǎn)附近和第160個采樣點(diǎn)附近兩圖有明顯差異，說明算法執(zhí)行時對這兩部分操作處理的數(shù)據(jù)有明顯不同，這與遍歷輸入明文字節(jié)的位置不同相對應(yīng)，印證了第一個S盒和第二個S盒作為碰撞攻擊點(diǎn)的事實(shí)。

4.3 相關(guān)系數(shù)計算

將第一個S盒和第二個S盒作為碰撞攻擊的目標(biāo)。設(shè)初始密鑰 K=128’h0123 4567 89AB CDEF FEDC BA98 7654 3210，固定明文 P=128’h0000 0000 0000 0000 0000 0000 0000 0000，遍歷 Δa，b=Δg，對對應(yīng) P 的能量跡和對應(yīng)P⊕Δg的能量跡進(jìn)行相關(guān)系數(shù)計算。由于兩個S盒對應(yīng)電磁曲線中位置不同，在計算相關(guān)系數(shù)前，將第二個S盒的電磁曲線左移50個采樣點(diǎn)，使得兩個S盒對應(yīng)位置信息對齊。固定α∈GF(28)，對每一個時間點(diǎn)計算相關(guān)系數(shù)ρ(Ma，Ma⊕Δa，b)。對以上采集到的電a b磁曲線進(jìn)行相關(guān)系數(shù)計算，得到相關(guān)系數(shù)結(jié)果如圖8所示。

從圖8中可以看出， 當(dāng) Δa，b=128’h0000 0000 0000 0000 0000 0000 0000 2200 時，對應(yīng) P 和 P⊕Δa，b的 相 關(guān)系數(shù)曲線有明顯的尖峰，則碰撞檢測成功。

圖8 相關(guān)系數(shù)結(jié)果圖

5 結(jié)論

為了識別攻擊點(diǎn)，本文提出方差檢查技術(shù)，在對AES進(jìn)行攻擊的過程中，利用基于相關(guān)系數(shù)的碰撞檢測方法對其進(jìn)行了驗(yàn)證，結(jié)果表明方差檢查技術(shù)可以有效地識別攻擊點(diǎn)在能量跡中的位置信息。

[1]SCHRAMM K，WOLLINGER T，PAAR C.A new class of collision attacks and its application to DES[C].Johansson，T.(ed.)FSE 2003，LNCS，Springer，Heidelberg，2003：206-222.

[2]SCHRAMM K，LEANDER G，F(xiàn)ELKE P，et al.A collisionattack on AES：combining side channel and differentialattack[C].Joye，M.，Quisquater，J.-J.(eds.)CHES 2004，LNCS，Springer，Heidelberg，2004：163-175.

[3]BOGDANOV A.Improved side-channel collision attacks on AES[C].Selected Areas in Cryptography-SAC 2007，2007：84-95.

[4]MORADI A，MISCHKE O，EISENBARTH T.Correlationenhanced power analysis collision attack[C].CHES，2010：125-139.

[5]CANRIGHT D.A very compact S-Box for AES[C].CHES 2005，volume 3659 of LNCS，Springer，2005：441-455.

[6]SATOH A，MORIOKA S，TAKANO K，et al.A compact rijndael hardware architecture with S-Box optimization[C].Advances in Cryptology-ASIACRYPT 2001，volume 2248 of LNCS，Springer，2001：239-254.

[7]段二朋，嚴(yán)迎建，李佩之.針對 AES密碼算法FPGA實(shí)現(xiàn)的 CEMA攻擊[J].計算機(jī)工程與設(shè)計，2012，33(8)：2926-2930.