Piccolo相關(guān)性功耗分析攻擊技術(shù)研究

王晨旭，趙占鋒，喻明艷，王進(jìn)祥，姜佩賀

(1.哈爾濱工業(yè)大學(xué)微電子中心，150001哈爾濱;2.哈爾濱工業(yè)大學(xué)信息與電氣工程學(xué)院，264209山東威海)

移動數(shù)字終端，無線傳感器網(wǎng)絡(luò)(WSN)，射頻識別(RFID)等技術(shù)的應(yīng)用日趨廣泛，這些技術(shù)對終端設(shè)備的硬件資源、能耗和終端數(shù)據(jù)安全等方面提出了更嚴(yán)格的要求.由于資源消耗和數(shù)據(jù)安全這對矛盾體的出現(xiàn)，給傳統(tǒng)加密算法帶來了新的挑戰(zhàn)，輕量級分組密碼算法應(yīng)運(yùn)而生.輕量級分組密碼算法是在確保加密數(shù)據(jù)安全的前提下，利用最少的硬件資源，最低的功耗實(shí)現(xiàn)的一類加密算法，例如，Sony公司提出的CLEFIA密碼算法以及在CHES2007上提出的PRESENT密碼算法已經(jīng)在2012年成為輕量級密碼算法的ISO標(biāo)準(zhǔn)［1-3］.作為CLEFIA的派生算法，Piccolo分組密碼算法于CHES2011上由Sony公司提出，它具有良好的硬件實(shí)現(xiàn)效率，在0.13 μm工藝下僅需683個等效門(Gate Equivalents，GE)即可實(shí)現(xiàn)加密操作，非常適合在資源受限的環(huán)境中使用［4］，展示出了非常好的使用前景.

在文獻(xiàn)［4］中，作者分別對Piccolo的差分分析安全性和線性分析安全性等方面進(jìn)行了評估，并聲稱該算法設(shè)計(jì)是安全的.然而，近年來，密碼算法的實(shí)現(xiàn)安全性受到了側(cè)信道攻擊(Side-Channel Attack，SCA)的嚴(yán)峻挑戰(zhàn)［5］，它是通過分析密碼設(shè)備在運(yùn)行過程中產(chǎn)生的功耗、電磁輻射等信息進(jìn)行密鑰攻擊的一種方法，該方法以其成本低、攻擊力強(qiáng)、防護(hù)困難等特點(diǎn)引起了國內(nèi)外研究人員的極大關(guān)注.相關(guān)功耗分析(Correlation Power Analysis，CPA)是SCA的一種，通過建立功耗模型，分析假設(shè)功耗與實(shí)際功耗曲線(Power Trace)之間的相關(guān)性，借助統(tǒng)計(jì)方法來完成密鑰攻擊［6］.本文首次對該算法功耗分析方面的安全性進(jìn)行了評估，提出了一個切實(shí)可行的功耗分析攻擊模型，成功地實(shí)施了對Piccolo的功耗分析攻擊.

1 相關(guān)性功耗分析攻擊簡介

Piccolo分組密碼算法的分組長度為64位，支持80位和128位兩種密鑰長度，分別用Piccolo-80和Piccolo-128表示，對應(yīng)的迭代輪數(shù)分別為25輪和31輪.Piccolo算法結(jié)構(gòu)是廣義Feistel結(jié)構(gòu)的變種，輪變換包括Feistel函數(shù)F和輪置換函數(shù)RP.本文的研究對象為Piccolo-80，并用Piccolo指代Piccolo-80.以下首先給出本文所用符號標(biāo)記的含義，而后對算法做簡要介紹.

1.1 符號標(biāo)記

a(b):二進(jìn)制數(shù)據(jù)a的長度為b位.

a':向量或矩陣a的轉(zhuǎn)置.

{a}b:用b進(jìn)制表示數(shù)據(jù)a.

{a，b，…}:將數(shù)值a，b，…進(jìn)行拼接.

X(a:b):選擇變量X的第a位到第b位.

HW(a):a的漢明重量.

HD(a，b):a和b的漢明距離.

HP(a:b):a位到b位的假設(shè)功耗值.

1.2CPA攻擊過程

在CPA攻擊中，針對首輪的明文攻擊和針對最后一輪的密文攻擊是兩種主要的攻擊方式，兩種攻擊方式的基本原理和攻擊方法相似，但相形之下，由于首輪運(yùn)算中包含了輪置換函數(shù)，所以明文攻擊要比密文攻擊復(fù)雜度高.本文選擇明文攻擊評測Piccolo密碼算法抗功耗分析的能力，攻擊目標(biāo)是獲取首輪輪密鑰RK0L、RK0R和白化密鑰WK0，WK1(為解釋方便，下文將WK0、WK1、RK0L和RK0R統(tǒng)稱為攻擊密鑰)，針對明文的CPA攻擊主要分為以下4個步驟:

1)利用HDL語言完成Piccolo算法的硬件設(shè)計(jì).

2)采集不同明文加密時的功耗信息，建立矩陣Pact，同時記錄對應(yīng)的明文.

3)基于漢明距離建立假設(shè)功耗模型，建立假設(shè)功耗矩陣Phyp.利用明文和密鑰猜測值推算出加密過程的某一中間值，將每一條明文的該過程映射為功耗信息，形成假設(shè)功耗矩陣Phyp.這一步是能否成功實(shí)施CPA攻擊的關(guān)鍵.

4)對Pact和Phyp進(jìn)行數(shù)學(xué)統(tǒng)計(jì)分析，完成對攻擊密鑰的攻擊，獲得攻擊密鑰的最可能值.

2 攻擊模型

2.1Piccolo算法的硬件實(shí)現(xiàn)

Piccolo算法的ASIC硬件實(shí)現(xiàn)方式主要有兩種，一是基于輪的并行實(shí)現(xiàn)方法，它可以得到較高的數(shù)據(jù)吞吐率，但消耗的硬件資源較多［7］.二是將輸入數(shù)據(jù)進(jìn)行分組，每組分別處理，再予以拼接，即串行實(shí)現(xiàn)方法，這種方法能夠顯著的減小硬件資源消耗，683GE即可實(shí)現(xiàn)［4］.在基于輪的并行實(shí)現(xiàn)方法中，Piccolo-80每輪計(jì)算的64位中間結(jié)果被記錄在觸發(fā)器DFF(0:63)中(本文用DFF(0)表示這些觸發(fā)器的最高有效位)，由于這里選擇了明文攻擊，因此只關(guān)心觸發(fā)器在首輪的數(shù)據(jù)變化.Piccolo-80的首輪的硬件抽象如圖1.

圖1 Piccolo密碼算法首輪運(yùn)算硬件抽象

2.2 假設(shè)功耗矩陣建模

根據(jù)CMOS電路的固有屬性，當(dāng)觸發(fā)器的值發(fā)生變化時將產(chǎn)生功耗，因此在t1時刻前后一段時間的功耗，可以用觸發(fā)器翻轉(zhuǎn)的個數(shù)予以表示，即可以對其使用觸發(fā)器翻轉(zhuǎn)前后(圖1中的深色部分)的漢明距離進(jìn)行功耗建模.

由于密鑰未知，在某一固定明文下，遍歷所有可能的密鑰值，根據(jù)該功耗模型獲取這一加密過程在某一時刻的假設(shè)功耗信息，之后，再通過換取不同的明文執(zhí)行上述過程構(gòu)成假設(shè)功耗矩陣.如果對N個明文進(jìn)行計(jì)算，所有密鑰遍歷位數(shù)為k，可以得到一個N×2k的假設(shè)功耗矩陣Phyp.

根據(jù)圖1，觸發(fā)器DFF(0:63)在t0時刻的值受到明文P和WK0、WK1的影響，而后RK0L、RK0R的不同造成了觸發(fā)器在t1時刻值的不同，因此只需對WK0、WK1、RK0L、RK0R進(jìn)行2(16+16+16+16)=264次遍歷，即可完成對假設(shè)功耗矩陣的建模.然而，這種方法工作量巨大，在有限的時間內(nèi)無法完成，對攻擊幾乎沒有意義.

由于部分觸發(fā)器的功耗與總功耗也會存在一定的相關(guān)性，為了方便計(jì)算，采用分而治之的思想，我們可以基于DFF(0:63)中部分觸發(fā)器進(jìn)行功耗建模，將WK0，WK1，RK0L，RK0R按下式進(jìn)行重新排列.

SubKey1(20)={WK0(0:15)，RK0L(0:3)}，

SubKey2(4)=RK0L(4:7)，

SubKey3(20)={WK1(0:15)，RK0L(0:3)}，

SubKey4(4)=RK0R(4:7)，

SubKey5(8)=RK0L(8:15)，

SubKey6(8)=RK0R(8:15).

之后對六段子密鑰SubKey1(20)、SubKey2(4)、SubKey3(20)、SubKey4(4)、SubKey5(8)、SubKey6(8)分別建立假設(shè)功耗矩陣，逐個進(jìn)行攻擊.這樣，可以將攻擊密鑰的搜索空間降低到了(2×220+2×24+2×28)，給計(jì)算創(chuàng)造了可能.

2.2.1 針對SubKey1(20)的假設(shè)功耗矩陣建模

由于首輪的RP置換，RK0L(0:3)的不同對DFF(0:3)在t1時刻的值構(gòu)成影響.為攻擊RK0L(0:3)，需要對DFF(0:3)在所有相關(guān)輪密鑰可能值下的漢明距離進(jìn)行計(jì)算.由于DFF(0:3)不僅受到RK0L(0:3)的影響，還要受到非線性函數(shù)F輸出的制約，因此WK0同樣影響DFF(0:3)的值.通過對RK0L(0:3)和WK0的值(即上文中的SubKey1(20))進(jìn)行遍歷，即可通過P(0:15)和P(16:19)恢復(fù)出觸發(fā)器DFF(0:3)在不同的子密鑰下t0和t1時刻的值，這樣就完成了DFF(0:3)漢明距離的計(jì)算.攻擊模型如下:

式中:Fout(0:3)表示F函數(shù)輸出的高4位;WK0g表示白化密鑰WK0的猜測值;RK0Lg(0:3)表示輪密鑰RK0L高4位的猜測值.WK0g與WK0同樣具有16位寬度，所以WK0g將會有216個可能的猜測值，根據(jù)上述模型，通過對SubKey1(20)的220次遍歷可以得到一個1×220的漢明距離矩陣，這個矩陣代表了在不同子密鑰猜測下，觸發(fā)器翻轉(zhuǎn)時刻的猜測的功耗信息，如果對N個明文進(jìn)行計(jì)算，則可以得到一個N×220的矩陣，這個矩陣即為我們攻擊SubKey1(20)所需的假設(shè)功耗矩陣Phyp1，利用該矩陣和后文的統(tǒng)計(jì)分析技術(shù)即可得到WK0和RK0L(0:3).

2.2.2 針對SubKey2(4)的假設(shè)功耗矩陣建模

在完成了WK0和RK0L(0:3)的攻擊后，WK0已經(jīng)成為了已知量，由于RP置換，RK0L(4:7)影響了DFF(4:7)在t1時刻的值.對RK0L(4:7)(即上文的SubKey2(4))進(jìn)行遍歷，計(jì)算DFF(4:7)在不同密鑰猜測的情況下時鐘沿前后的漢明距離，就得到了攻擊RK0L(4:7)所需的假設(shè)功耗矩陣Phyp2.建模過程如下:

由上述模型可知，基于N條明文并對SubKey2(4)進(jìn)行遍歷后得到N×24的假設(shè)功耗矩陣Phyp2.

2.2.3 針對SubKey3(20)和SubKey4(4)的假設(shè)功耗矩陣建模

對WK1和RK0R(0:3)的攻擊過程與對WK0和RK0L(0:3)的攻擊過程基本一致，唯一的區(qū)別就是這里需要對DFF(32:35)的漢明距離進(jìn)行建模以完成攻擊.

在完成了WK1和RK0R(0:3)的攻擊后，WK1已經(jīng)成為了已知量，對RK0R(4:7)的功耗建模與對RK0L(4:7)的功耗建模過程基本一致，所不同的是這里需要關(guān)注DFF(36:39)的漢明距離.

2.2.4 針對SubKey5(8)和SubKey6(8)的假設(shè)功耗矩陣建模

在得到WK0和WK1后，即可通過如下兩個等式針對RK0L(8:15)(即上文的SubKey5(8))完成功耗建模，該過程相對比較簡單.

為攻擊RK0R(8:15)(即上文的SubKey6(8))，需要關(guān)注DFF(8:15)的漢明距離，其建模過程與RK0L(8:15)的功耗建模過程相似.

3 實(shí)驗(yàn)配置及CPA攻擊結(jié)果

3.1 實(shí)驗(yàn)配置

功耗分析攻擊不同于普通的側(cè)重于平均功耗的功耗分析，它主要關(guān)注芯片工作過程中瞬態(tài)功耗與數(shù)據(jù)的相關(guān)性，密碼電路工作時的瞬態(tài)功耗數(shù)據(jù)獲取通常有兩種方式:第一種是采用示波器對實(shí)際芯片進(jìn)行功耗曲線測量［8］;第二種是采用功耗模擬工具，在設(shè)計(jì)階段獲取加密過程的功耗信息［9-10］.第一種方法雖然更有說服力，但是不能在芯片設(shè)計(jì)周期評估密碼芯片的功耗分析攻擊安全性，為了能夠準(zhǔn)確、快速的研究Piccolo的抗功耗分析攻擊特性，本文基于SMIC 0.18 μm 1P6M Logic18 CMOS工藝和PrimeTime PX功耗模擬工具，獲取加密過程的功耗信息，攻擊實(shí)驗(yàn)中所采用的實(shí)驗(yàn)條件與資源如表1所示.功耗曲線獲取流程如圖2所示.

表1 基于模擬功耗數(shù)據(jù)的CPA攻擊實(shí)驗(yàn)條件

圖2 功耗數(shù)據(jù)采集模擬平臺

假設(shè)每次加密過程的功耗信息由T個采樣點(diǎn)構(gòu)成，通過換取N條不同明文，重復(fù)執(zhí)行圖2中虛線框中的過程N(yùn)次，則可以得到N×T個采樣點(diǎn)，構(gòu)成N行T列的實(shí)際功耗矩陣Pact.

3.2 攻擊結(jié)果

在功耗分析攻擊中，功耗樣本數(shù)量越多，攻擊成功率就越高，因此常用MTD(Measurements To Disclosure)代表為了正確破解密鑰至少需要的功耗曲線數(shù)量，它經(jīng)常用來衡量密碼算法實(shí)現(xiàn)的抗功耗分析攻擊的能力［10-11］.依照第1部分中的CPA攻擊過程，分別完成了對6段子密鑰的攻擊，攻擊實(shí)驗(yàn)中，Piccolo加密時的種子密鑰PK(64)取{123456 789ABCDEF12345}16.攻擊結(jié)果顯示，500條功耗曲線足以恢復(fù)出白化密鑰WK0和WK1以及首輪的輪密鑰RK0L和RK0L.

由于對WK1和RK0R的攻擊與WK0和RK0L的攻擊過程基本一致，因此這里僅僅給出對WK0和RK0L，即SubKey1、SubKey2和SubKey5的攻擊結(jié)果.圖3是針對SubKey1的攻擊結(jié)果.其中，中橫坐標(biāo)表示密鑰猜測值，縱坐標(biāo)表示了相應(yīng)的相關(guān)系數(shù);圖3(b)則表示在攻擊成功時刻點(diǎn)附近，不同的SubKey1猜測值的相關(guān)系數(shù)隨功耗樣本數(shù)量的變化曲線，它更加形象的表明了SubKey1的抗功耗分析攻擊的能力，從50條功耗樣本開始，通過不斷增加樣本數(shù)量，逐次進(jìn)行上述CPA攻擊，直至能夠穩(wěn)定攻擊出SubKey1，并由此推出SubKey1的MTD值.

由圖3(a)可以發(fā)現(xiàn)，當(dāng)x={75657}10={12789}16時，相關(guān)系數(shù)達(dá)到最大值0.329，這說明在本次攻擊中{12789}16={0001-0010-0111-1000-1001}2最有可能是SubKey1的真實(shí)值，由此可推出WK0的攻擊密鑰值為{0001-0010-0111-1000}2，而RK0L(0:3)的攻擊密鑰值為{1001}2，事實(shí)上，WK0和RK0L(0:3)的真實(shí)密鑰值也的確如此.

隨著功耗曲線樣本數(shù)量的增加，正確密鑰與其它密鑰的相關(guān)系數(shù)在總體趨勢上都會有所降低，但是，與正確密鑰相比，錯誤密鑰的下降速度要來得快些，這一點(diǎn)可以由圖3(b)可以看出，隨著樣本量的增加，正確SubKey1猜測值與其它圖3(a)表示在500條功耗樣本下實(shí)施CPA攻擊時，不同SubKey猜測值所對應(yīng)的相關(guān)系數(shù)，圖SubKey1猜測值的相關(guān)系數(shù)的區(qū)別不斷加大，大約200條樣本就已經(jīng)可以成功破解SubKey1，即SubKey1的MTD值約為200.

圖3 針對SubKey1的CPA攻擊結(jié)果

針對SubKey2和SubKey5也可依次完成上述兩種實(shí)驗(yàn)，得到的CPA攻擊結(jié)果如圖4和5所示.由圖4(a)，在x={13}10={1101}2時獲得了最大的相關(guān)系數(shù)0.3401，即RK0L(4:7)的攻擊密鑰值為{1101}2={D}16.依據(jù)圖4(b)，可以得到SubKey2的MTD約為300.

圖4 針對SubKey2的CPA攻擊結(jié)果

對SubKey5的攻擊結(jié)果如圖5.從圖5可得出RK0L(8:15)的攻擊密鑰值為{1010-0000}2={A0}16;SubKey2的MTD值約為200.在圖5(a)中主峰與次峰相差較小(分別為0.475 4與0.459 6)，在基于本攻擊模型和實(shí)測功耗曲線進(jìn)行CPA攻擊時可能會被測量噪聲淹沒，此時可以通過增加樣本數(shù)量的方法提高攻擊成功率.

圖5 針對SubKey5的CPA攻擊結(jié)果

結(jié)合對SubKey3(20)、SubKey4(4)和SubKey6(8)的攻擊實(shí)驗(yàn)，500條功耗曲線足以成功攻擊上述6段子密鑰.綜上，對Piccolo進(jìn)行首輪的CPA攻擊后得到RK0L={9da0}16，WK0={1278}16，這些結(jié)果與預(yù)期值相同，表明攻擊成功.同時我們也換取了別的密鑰值，雖然所需功耗樣本數(shù)量(MTD)會稍有不同，但CPA攻擊同樣能夠成功，證明了所提出攻擊模型的行之有效性.

4 討論

4.1 種子密鑰的獲得

在完成對密鑰WK0、WK1、RK0L和RK0R的攻擊后，能夠容易地得到Piccolo的80位種子密鑰中的64位，只有PK(64:79)是未知的，此時可以基于一對明密文結(jié)合窮舉的方法獲得PK(64:79)，由此，采用本文上述攻擊模型，需要(2×220+2×24+2×28+216)次遍歷計(jì)算即可獲得Piccolo的80位種子密鑰.

4.2 相關(guān)度

根據(jù)上述討論，在t1時刻，實(shí)際Piccolo硬件的功耗可近似用DFF(0:63)全部64個觸發(fā)器的動態(tài)功耗表征;但是，在攻擊模型建立時，SubKey1和SubKey2分別依賴于DFF(0:3)和DFF(4:7)，而SubKey5則有賴于DFF(40:47)這8個觸發(fā)器，因此攻擊SubKey5時用到的功耗模型更加接近于真實(shí)情況.這造成了在成功攻擊SubKey5時的相關(guān)系數(shù)(0.4754)比攻擊SubKey1和SubKey2時的相關(guān)系數(shù)(分別是0.329和0.3401)要高.

4.3 密鑰搜索空間

在上述攻擊模型中，將WK0，WK1，RK0L，RK0R重排為6段子密鑰，由此得到的攻擊密鑰搜索空間為(2×220+2×24+2×28);需要指出，這種重排方式并不唯一，也能按照如下方式重排為4段子密鑰建立模型實(shí)施攻擊:

這種組合方式造成攻擊密鑰的搜索空間為(2×220+2×212)，比本文采用的方式要大.為了獲得更小的密鑰搜索空間，并降低內(nèi)存空間復(fù)雜度，也可以將WK0，WK1，RK0L，RK0R重排為如下8段子密鑰，并基于相應(yīng)的觸發(fā)器段進(jìn)行建模，此時，可以將攻擊密鑰的搜索空間降低為(8×28)，該攻擊模型也已經(jīng)通過實(shí)驗(yàn)證實(shí)了其可行性.

5 結(jié)論

輕量級密碼算法在硬件資源消耗與數(shù)學(xué)安全方面得到了有機(jī)的統(tǒng)一，但是輕量級密碼算法同樣也受到了功耗分析攻擊的威脅，Piccolo算法在首輪和最后輪中加入了白化密鑰，這在一定程度上給功耗分析攻擊增加了困難.由于Piccolo屬于GFN結(jié)構(gòu)型密碼算法，與傳統(tǒng)密碼算法AES和DES的功耗建模方式有所不同.本文評估了Piccolo面向功耗分析攻擊的安全性，提出了一種針對首輪的相關(guān)性功耗分析攻擊模型，成功地完成了Piccolo算法的80位種子密鑰的攻擊.攻擊結(jié)果表明，在模擬功耗數(shù)據(jù)的情況下，只需500條功耗曲線即可完全恢復(fù)出Piccolo-80的種子密鑰，而密鑰搜索空間也從面向數(shù)學(xué)分析的280降低為面向?qū)崿F(xiàn)的功耗分析攻擊時的(2×220+2×24+2×28+216)，由此可見，輕量級密碼算法在面向功耗分析攻擊時是脆弱的，在Piccolo的硬件實(shí)現(xiàn)中引入相應(yīng)的抗功耗分析攻擊措施是不可忽略的.研究適用于輕量級分組密碼算法的抗功耗分析攻擊措施將是下一步的研究重點(diǎn).

［1］CLEFIA:a lightweight block cipher with a block size of 128 bits and a key size of 128，192 or 256 bits［S］.ISO/IEC 29192-2:2012，2012.

［2］PRESENT:a lightweight block cipher with a block size of 64 bits and a key size of 80 or 128 bits［S］.ISO/IEC 29192-2:2012，2012.

［3］BOGDANOV A，KNUDSEN L R，LEANDER G，et al.PRESENT:An Ultra-Lightweight Block Cipher［C］.//Proceedings of the 9th International Workshop on Cryptographic Hardwareand Embedded Systems.Berlin:Springer-Verlag，2007:450-466.

［4］SHIBUTANIK.Piccolo:Anultra-lightweight blockcipher［C］//Proceedings of the 13th International Workshop on Cryptographic Hardware and Embedded Systems.Berlin:Springer-Verlag，2011:342-357.

［5］KOCHER P，JAFFE J，JUN B.Differential power analysis［C］//Proceedings of Advances in Cryptology—CRYPTO’99.Berlin:Springer-Verlag.1999:388-397.

［6］BRIER E，CLAVIER C，OLIVIER F.Correlation Power Analysis with a leakage model［C］//Proceedings of the 6th International Workshop on Cryptographic Hardware andEmbeddedSystems.Berlin:Springer-Verlag，2004:135-152.

［7］唐明，汪波，楊欣，等.分組密碼的硬件實(shí)現(xiàn)［J］.哈爾濱工業(yè)大學(xué)學(xué)報，2006，38(9):1558-1562.

［8］烏力吉，李賀鑫，任燕婷，等.智能卡功耗分析平臺設(shè)計(jì)與實(shí)現(xiàn)［J］.清華大學(xué)學(xué)報(自然科學(xué)版)，2012，52(10):1409-1414.

［9］劉鳴，陳弘毅，白國強(qiáng).功耗分析研究平臺及其應(yīng)用［J］.微電子學(xué)與計(jì)算機(jī)，2005，22(7):134-238.

［10］ZHANG J，GU D W，GUO Z，et al.Differential power cryptanalysis attacks against PRESENT implementation［C］//Proceedings of the 3rd International Conference on Advanced Computer Theory and Engineering.New York:IEEE，2010:V6-61-65.

［11］LIU P C，CHANG H C，LEE C Y.A Low Overhead DPA Countermeasure Circuit Based On Ring Oscillators［J］.IEEE Transactions on Circuits and systems-II，2010，57(7):547-550.