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.