MICKEY和Trivium 同步流密码的能量攻击

杨昌盛，严迎建

（解放军信息工程大学，河南 郑州450004）

0 引 言

能量分析（power analysis，PA）攻击自Paul C.Kocher于1998年提出以来，被广泛地应用于分组密码和公钥密码的分析，但针对流密码的研究相对较少［1－3］。文献［4］基于LFSR（linear feedback shift register）相邻时刻能量消耗差异建立方程组，通过代数方法求解内部状态。文献 ［5］通过选择初始向量IV 来消除算法噪声，用较少的能量迹恢复密钥。文献［6］利用C 语言模拟能量消耗过程，对MICKEY流密码进行了仿真攻击。文献［7］对K2流密码进行了包括PA 攻击在内的多种侧信道攻击。

尽管国内外在流密码的能量分析攻击方面已有一定的研究，但大多停留在理论层面，或仅基于简单的仿真模型进行分析，且部分文献提出的方法没有考虑实际的可操作性。本文根据流密码算法的共性特征，提出了面向同步流密码PA 攻击点选取策略，并以eSTREAM［8］项目中获胜的MICKEY 和Trivium 算法为例进行了攻击演示，最后在ASIC（application specific integrated circuit）开发环境下进行了仿真实验，验证了上述策略的合理性。

1 同步流密码PA 攻击点选取策略

与分组密码中通过加／解密大量明／密文来获取密码算法能量迹进行PA 攻击的原理类似，同步流密码的PA 攻击利用了同步流密码需要反复初始化并更换IV 这一特性，使得获取大量已知IV 对应的能量迹成为可能［5］，其主要包括3个关键点：①攻击点的选取；②能量消耗模型；③假设能量消耗与实测能量迹的匹配。其中攻击点的选取最为关键，而能量消耗模型的研究已经很充分，采用汉明距离作为CMOS器件的能量消耗模型被证明是有效的［9］。

1.1 分组密码PA攻击点选取方法

在分组密码的PA 攻击中，攻击点必须是一个与局部密钥Kpartial和IV 有关的中间值f（IV，Kpartial）。在密码芯片中函数f 对应于局部电路，局部电路状态的变化将反映到局部功耗上。PA 攻击正是通过猜测局部密钥并根据能量消耗模型计算局部电路假设能量消耗，最后与采样到的密码算法总功耗进行匹配，匹配效果最好的猜测密钥被认为是正确的局部密钥。

1.2 同步流密码PA攻击点选取条件分析

同步流密码的PA 攻击点选取原则与分组密码中的类似，但仅满足上述条件并不足以保证攻击的可行性。记密码算法总功耗为Ptotal，攻击点对应的局部电路功耗为Pattack，与密码算法有关的其它功耗为Pnoise.algorithm，密码设备运行时引入的随机噪声为Pnoise.electronic，密码设备功耗中的常量成分为Pconstant，则密码算法总功耗可表示如下

其中，Pnoise.electronic与Pattack相互独立，而Pconstant对于功耗匹配没有影响，则PA 攻击最终转换为分析攻击点假设能量消耗与Pattack＋Pnoise.algorithm的匹配情况。在针对分组密码PA攻击的文献 ［10］中，作者假设Pnoise.algorithm与Pattack相互独立，并取得了理想的攻击结果。分析发现，由于分组密码中普遍使用了混乱和扩散部件，使得Kpartial在参与密码算法中的其它运算时，经过混乱和扩散的作用，其在Pnoise.algorithm中的功耗分量表现出很强的随机性。而流密码的构造相对简单，且存在大量线性部件，Pattack与Pnoise.algorithm相互独立的假设不再适用，而Pattack与Pnoise.algorithm的相关性可能导致PA 攻击无法实现。

据此，本文提出在选取同步流密码的PA 攻击点时，必须严格保证所攻击的Kpartial在Pnoise.algorithm中引起的分量与Pattack不相关或弱相关。

1.3 同步流密码PA攻击点选取的一般策略

根据以上分析，本文就同步流密码PA 攻击点的选取提出以下策略。

（1）适用于逐比特攻击的情形

对于密钥逐比特注入的密码算法（如MICKEY、A5／1），以与密钥注入端直接相关的中间状态为攻击点进行逐比特攻击是最为有效的方法；如果密钥与IV 并行注入，但密码算法中存在密钥与IV 单比特结合的部件（如Trivium），如图1所示，则该部件也可能成为有效的攻击点，由于这种攻击点仅以1比特寄存器的能量消耗差异值为区分函数，因此在选取IV时应特别考虑，以免Pattack被Pnoise.algorithm掩盖。

（2）适用于多比特攻击的情形

图1 密钥与IV 单比特结合

流密码算法的前馈模型中普遍采用滤波函数，一般是将FSR 的抽头代入布尔函数进行运算，如图2所示。如果布尔函数f2是非线性的（如Grain、DECIM），则其可能成为有效的攻击点。但若f2是线性的，则抽头位置所对应的局部密钥可能存在多种组合，例如f2为4输入异或逻辑，当通过PA 攻击猜测出某一时刻h 的值为0 时，则该时刻t1t2t3t4可能取值0000、1111、1100、0011等情况，对于抽头数量较多的部件，这种组合的数量是非常可观的，这种情况下的f2不适合作为攻击点。

图2 前馈模型中的滤波函数

2 MICKEY的能量攻击

2.1 MICKEY简介

密钥K ＝（k1，…，k80），长度为80比特，初始向量IV＝（iv1，…，ivL），长度L 可变，0≤L≤80，由寄存器R和S组成，每个寄存器100级，其中R 为线性，S为非线性。其密钥加载和初始化过程包括4 个阶段：①寄存器R和S置0；②IV 逐比特注入；③密钥逐比特注入；④空转（preclock）。图3给出了MICKEY 算法的硬件原理图，IV和密钥从input＿bit端口逐比特注入，经过组合逻辑后分别由input＿bit＿r和input＿bit＿s注入寄存器R 和寄存器S。其中，寄存器R 中有50个状态位与input＿bit＿r有关，寄存器S中所有状态位均与input＿bit＿s相关，具体参见文献［11］。

图3 MICKEY 算法硬件原理

2.2 攻击方案

（1）攻击点选取

根据1.3中的分析，MICKEY 算法与 “适用于逐比特攻击”中的前一种情形相符，故采取逐比特攻击方案。选取IV 加载完毕后，密钥加载阶段寄存器R 和寄存器S中所有与密钥注入端相关的状态位为攻击点，即ft（IV，K）＝（Rt‖St）IV，K，t＝0，…，80，其中，t表示已经加载的密钥比特数；“‖”表示拼接操作，ft表示第t个密钥比特注入后，寄存器R 和S所有状态位，共150比特。

（2）获取密码算法能量消耗

准备N 组随机初始向量IV1，IV2，…，IVN和待攻击密钥K’＝（k’1，…k’80），测量MICKEY 算法在加载上述IV和密钥时的能量消耗，记为P＝（P1，P2，…，PN）T，其中Pi＝（Pi，1，Pi，2，…，Pi，M）对应于IVi参与运算时的能量迹，M 为能量迹中采样点个数，即P的规模为N×M。

（3）计算攻击点假设能量消耗值

（4）假设能量消耗值与能量迹匹配

最后比较P 中各列P＊，i（1≤i≤M）与Hk（1≤K≤80，对应于第k比特密钥）中各列（1≤j≤2）的匹配程度。本文使用相关系数反映Hk中各列与P 中各列的匹配程度，计算公式如下

2.3 仿真实验

上述攻击方案与攻击平台无关，在实测环境和仿真环境中均适用，两者仅在IV 的样本数量和获取密码算法能量消耗的方式上有所区别。为了初步验证攻击方案的有效性，本文采用芯片设计流程中的EDA 工具获取密码算法能量消耗，其流程如图4所示。

图4 基于ASIC开发环境的功耗仿真流程

采用SMIC 0.18μm 工艺库，用Design Compiler 对Verilog HDL实现的MICKEY 算法进行综合，得到门级网表，并以 “攻击方案第2步”中准备的IV 和密钥为测试激励在VCS下进行仿真，得到包含网表中所有门的翻转信息的VCD 文件，最后利用PrimeTimePX 获取密码算法的能量消耗信息，具体可参考文献［12］。

实验采用随机初始向量2000 组，待攻击密钥K’ ＝0x5a5b5c5d5e5fa5a6a7a8（k1在最左端）。按照上述攻击方案，逐比特恢复出了完整的80比特密钥。图5给出了攻击第1、2和80比特时，假设能量消耗与算法总功耗（仿真功耗）的匹配情况，图中纵轴为相关系数，横轴为功耗采样点。

图5 仿真攻击第1、2和80比特时的相关系数

表1列出了攻击第1、2、3、79和80比特时，ρk两列中的最大值。

表1 击第1、2、3、79和80比特时ρk 峰值

3 Trivium 的能量攻击

3.1 Trivium 简介

密钥K＝（k1，…，k80），初始向量IV＝（iv1，…，iv80），长度均为80比特，由3 个NFSR（nonlinear feedback shift register）组成，级数分别为93，84和111，共288比特。其密钥安装与初始化过程包括2个阶段：

（1）密钥和IV 安装，过程如下：

（s1，s2，…，s93）←（k1，…，k80，0，…，0）

（s94，s95，…，s177）←（iv1，…，iv80，0，…，0）

（s178，s179，…，s288）←（0，…，0，1，1，1）

（2）空转4×288个时钟周期，过程如下：

for i＝1 to 4·288 do

t1←s66＋s91·s92＋s93＋s171

t2←s162＋s175·s176＋s177＋s264

t3←s243＋s286·s287＋s288＋s69

（s1，s2，…，s93）←（t3，s1，…，s92）

（s94，s95，…，s177）←（t1，s94，…，s176）

（s178，s179，…，s288）←（t2，s178，…，s287）

end

3.2 攻击方案

（1）攻击点选取

Trivium 算法符合 “适用于逐比特攻击”中的后一种情形。记Trivium 空转t 个时钟周期后第i 个状态比特为（1≤i≤288）＝，则中间值t1可记为＝＋·＋＋。由于，，…，全为0，因此当0≤t≤10时，，，为0，＝＋，而＝k66－t，＝iv78－t，根据前文分析，以t1为攻击点可以逐比特恢复k66，k65，…，k56。由于＝ki（1≤i≤80），故当完成前述11比特密钥的攻击后，，，…，即为已知，进而当27≤t≤35时，，，已知，以t1为攻击点可以逐比特恢复出k39，k38，…，k31。依此类推，反复地以前面攻击出的密钥比特为后续攻击的条件，最终可恢复出绝大部分密钥，其中当t≥66时用到式（1）

1）IV 选择方案1

表2 第1种IV 选择方案下的汉明距离情况

在具体攻击时，P＿HD 是基于猜测密钥比特计算出来的假设值，而T＿HD 是实际情况下的固有值。当密钥猜测正确时，P＿HD 与T＿HD 的相关系数为1。但当密钥猜测错误时，如猜测密钥比特为0，而实际密钥比特为1时，P＿HD＝ （0，3），T＿HD＝（1，2），两者的相关系数仍为1，故该IV 选择方案是不可行的。

2）IV 选择方案2

方案1的主要问题在于IV 空间过小，但是IV 空间过大又会造成寄存器s94的汉明距离被其它寄存器掩盖的问题。本文最初采用大量随机IV 进行攻击试验，其攻击结果与方案1类似。因此，方案2在方案1的基础上仅增加了iv77－t）1个可变IV 比特，即iv77－t‖iv78－t取00、01、10或11，IV 其它比特全为0。类似的，表3给出了不同密钥比特下，4个IV 参与运算时所有寄存器的汉明距离（T＿HD）和s94‖s170‖s171‖s172的汉明距离（P＿HD）。

表3 第2种IV 选择方案下的汉明距离情况

方案2中，当密钥猜测正确时，P＿HD 与T＿HD 的相关系数为1。当密钥猜测错误时，如猜测密钥比特为0，而实际密钥比特为1时，P＿HD＝（0，3，2，3），T＿HD＝（1，2，3，2），两者的相关系数为0.5，即密钥猜测正确与否是可区分的，故该IV 选择方案具备可行性。据此，攻击点确定为ft（IV，K）＝（‖‖‖）IV，K（0≤t≤10）。

（2）测量密码算法能量消耗

根据上述方案准备IV，攻击每1个密钥比特需要4个IV，测量Trivium 算法在加载上述IV 和待攻击密钥时的能量消耗，记为P ＝（P1，P2，…，P4）T，其中Pi＝（Pi，1，Pi，2，…，Pi，Y）对应于IVi参与运算时的能量迹，Y 为能量迹中采样点个数，即P 的规模为4×Y。

（3）计算攻击点假设能量消耗值

当攻击k66－t（0≤t≤10）时，对于每一种猜测值，分别计算t＋1时刻的攻击点状态ft＋1（IV，K），由于是逐比特攻击，根据前面攻击出的密钥比特可以确定＝0），故t时刻的攻击点状态ft（IV，K）已知，采用汉明距离模型计算攻击点处的假设能量消耗值，记为＝HW（ft⊕ft＋1），1≤i≤4，0≤t≤10，其中＝（，），分别对应猜测密钥比特为0和1，即Ht的规模为4×2。

（4）假设能量消耗值与能量迹匹配

与MICKEY 类似，针对Trivium 的能量攻击也采用相关系数来确定假设能量消耗值与算法总体功耗的匹配程度。所不同的是，MICKEY 的能量攻击中是根据整个相关系数矩阵中最大值确定猜测密钥比特。在Trivium 的能量攻击中，由于假设能量消耗矩阵H 每列仅含4个量，而密码算法能量迹采样点数（即P 列数）远大于24，故从整条能量迹来看，无论密钥猜测正确与否，Trivium 的相关系数矩阵ρ中都可能出现相关系数值很高的采样点，因此在分析不同猜测密钥比特与能量迹的匹配情况时，必须在该密钥比特参与攻击点运算的时刻进行。具体来说就是，在攻击k66－t（0≤t≤10）时，比较t＋1时刻能量迹采样点与假设能量消耗值的相关系数，下文将这一时刻称为攻击时刻。

3.3 仿真实验

与MICKEY 的仿真实验类似，在SMIC 0.18μm工艺库下利用PTPX 获取Trivium 算法运算时的功耗，待攻击密钥K’＝0x5a5b5c5d5e5fa5a6a7a8。图6给出了攻击k66，k65，k64和k63时，攻击点的假设能量消耗与算法总功耗的匹配情况，图中纵轴为相关系数，横轴为功耗采样点，虚线框对应于攻击时刻。

图6 仿真攻击k66，k65，k64和k63时的相关系数

表4列出了攻击k66，k65，k64，k63和k62时，不同猜测密钥比特在攻击时刻的假设能量消耗值与能量迹的相关系数。可以看到，当密钥猜测正确时，假设能量消耗值与能量迹的相关系数几乎为1，而当猜测错误时，相关系数近似为0.5，与前文的分析高度吻合，验证了攻击方案的有效性。

表4 攻击k66，k65，k64，k63和k62时在攻击时刻的相关系数

4 结束语

本文提出了同步流密码PA 攻击点选取策略，并以面向硬件的同步流密码算法MICKEY 和Trivium 为例进行了攻击演示，给出了具体的攻击方案及基于PrimeTimePX 等EDA 工具的仿真攻击结果，证明了攻击的有效性，进而验证了攻击点选取策略的合理性，为同步流密码PA 攻击的后续研究奠定了基础。

最后，结合攻击点选取策略，从抗能量攻击的角度，对流密码设计人员提出两点安全性建议：①密钥尽量并行加载，避免逐比特注入；②前馈函数中与密钥有关抽头数量尽可能多，避免一到一映射。

［1］ZANG Yuliang，HAN Wenbao.Differential power attack on linear feedback shift register［J］.Journal of Electronic ＆Information Technology，2009，31 （10）：2406－2410 （in Chinese）.［臧玉亮，韩文报.线性反馈移位寄存器的差分能量攻击 ［J］.电子与信息学报，2009，31 （10）：2406－2410.］

［2］JIA Yanyan，HU Yupu，ZHAO Yongbin，et al.Correlation power analysis of DECIM v2 ［J］.The Journal of China Universities of Posts and Telecommunications，2011，18 （5）：118－123.

［3］TANG Ming，CHENG Pingpan，QIU Zhenlong.Differential power analysis on ZUC algorithm［EB／OL］.http：／／eprint.iacr.org／，Report 2012／299，2012.

［4］Sanjay Burman，Debdeep Mukhopadhyay，Kamakoti Veezhinathan.LFSR based stream cipher are vulnerable to power attacks［G］.LNCS 4859：Berlin Heiderberg：Springer－Verlag，2007：384－392.

［5］Fischer W，Gammel BM，Kniffler O.Differential power analysis of stream ciphers ［G］.LNCS 4377：Berlin Heider－berg：Springer－Verlag，2007：257－270.

［6］ZANG Yuliang，ZENG Guang，HAN Wenbao，et al.Power attack on stream cipher MICKEY 2.0［J］.Journal of PLA University of Science and Technology （Natural Science Edition），2009，10 （4）：334－338 （in Chinese）. ［臧玉亮，曾光，韩文报，等.MICKEY 流密码算法的能量攻击 ［J］.解放军理工大学学报 （自然科学版），2009，10 （4）：334－338.］

［7］Matt Henricksen，Wun She Yap，Chee Hoo Yian，et al.Sidechannel analysis of the K2stream cipheR ［G］.LNCS 6168：Berlin Heiderberg：Springer－Verlag，2010：53－73.

［8］ECRYPT.ECRYPT stream cipher project［EB／OL］.http：／／www.ecrypt.eu.org／stream／，2008.

［9］Tim Guneysu，Amir Moradi.Generic side－channel countermeasures for reconfigurable devices ［G］.LNCS 6917：Berlin Heidelberg：Springer－Verlag，2011：33－48.

［10］Stefan Mangard，Elisabeth Oswald，Thomas Popp.Power analysis attack ［M］.FENG Dengguo，ZHOU Yongbin，LIU Jiye，et al transl.Beijing：Science Press，2010：56－58 （in Chinese）. ［Stefan Mangard，Elisabeth Oswald，Thomas Popp.能量分析攻击 ［M］.冯登国，周永斌，刘继业，等译.北京：科学出版社，2010：56－58.］

［11］Steve Babbage，Matthew Dodd.The stream cipher MICKEY 2.0［EB／OL］.http：／／www.ecrypt.eu.org／stream／p3ciphers／mikcey－p3.pdf，2008.

［12］FAN Haifeng，YAN Yingjian，XU Jinfu，et al.Simulation of correlation power analysis against AES cryptographic chip［J］.Computer Engineering and Design，2010，31 （2）：260－262 （in Chinese）. ［樊海锋，严迎建，徐金甫，等.AES密码芯片的相关性功耗分析仿真 ［J］.计算机工程与设计，2010，31 （2）：260－262.］