Piccolo相關性功耗分析攻擊技術研究

王晨旭，趙占鋒，喻明艷，王進祥，姜佩賀

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

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

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

1 相關性功耗分析攻擊簡介

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

1.1 符號標記

a(b):二進制數據a的長度為b位.

a':向量或矩陣a的轉置.

{a}b:用b進制表示數據a.

{a，b，…}:將數值a，b，…進行拼接.

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

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

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

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

1.2CPA攻擊過程

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

1)利用HDL語言完成Piccolo算法的硬件設計.

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

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

4)對Pact和Phyp進行數學統計分析，完成對攻擊密鑰的攻擊，獲得攻擊密鑰的最可能值.

2 攻擊模型

2.1Piccolo算法的硬件實現

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

圖1 Piccolo密碼算法首輪運算硬件抽象

2.2 假設功耗矩陣建模

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

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

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

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

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)分別建立假設功耗矩陣，逐個進行攻擊.這樣，可以將攻擊密鑰的搜索空間降低到了(2×220+2×24+2×28)，給計算創造了可能.

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗配置及CPA攻擊結果

3.1 實驗配置

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

表1 基于模擬功耗數據的CPA攻擊實驗條件

圖2 功耗數據采集模擬平臺

假設每次加密過程的功耗信息由T個采樣點構成，通過換取N條不同明文，重復執行圖2中虛線框中的過程N次，則可以得到N×T個采樣點，構成N行T列的實際功耗矩陣Pact.

3.2 攻擊結果

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

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

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

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

圖3 針對SubKey1的CPA攻擊結果

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

圖4 針對SubKey2的CPA攻擊結果

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

圖5 針對SubKey5的CPA攻擊結果

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

4 討論

4.1 種子密鑰的獲得

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

4.2 相關度

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

4.3 密鑰搜索空間

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

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

5 結論

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

［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］唐明，汪波，楊欣，等.分組密碼的硬件實現［J］.哈爾濱工業大學學報，2006，38(9):1558-1562.

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

［9］劉鳴，陳弘毅，白國強.功耗分析研究平臺及其應用［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.