针对轻型分组密码LED 提出了一种基于碰撞模型的代数旁路攻击。首先利用代数攻击方法建立密码算法等效布尔代数方程组;然后采集算法运行中泄露的功耗信息并转换为碰撞信息;最后将碰撞信息转化成额外方程组并利用CryptoMiniSAT 解析器求解密钥。实验结果表明：旁路碰撞信息可有效降低方程组求解的复杂度;已知明文条件下，利用2轮最少50%的随机碰撞信息，即可在158.5 秒内恢复64-bit LED 完整密钥。此外，本文中分析方法也可用于其它分组密码功耗碰撞分析。
用rc5⊕rc4⊕1 更新。
(2)S 盒代换SB：算法采用了16 个4 进4 出的S 盒，S盒沿用PRESENT 密码S盒。
(3)行移位SR：状态矩阵的第i 行向左移i 位，i=0,1,2,3。
(4)列混淆MC：状态矩阵的每一列由混淆矩阵和该列向量相乘所得的新的向量替换更新。
2.2 代数方程组构建
为建立LED 算法加密代数方程组，本文结合算法结构，引入了9 种类型的64-bit 中间状态变量，对应标记及含义如表2 所示。
S 盒代换是LED 密码唯一的非线性变换，参考文献[11]中的S 盒构建方法，将LED 的每个S 盒用4 个方程表示出来，方程最高次数为3，共有22 个变量，如式(1)所示。每轮LED加密可引入512 个变量，816 个ANF 等式。最后加入轮密钥加操作后，全部32 轮LED 算法共引入17089 个变量，26689个ANF 等式。
基于SAT 问题的方程组求解包括线性化方程组、将线性化方程组转化为CNF 两个步骤。由于CryptoMinisat 可以自动将布尔方程组转化为CNF 求解，所以线性化方程组之后不需要再进行切割及转化为CNF 操作。方程组的线性化问题通过降幂来完成。以非线性多元布尔方程组(2)为例，对于其中的高次单项式x1x2x3，为了达到降幂的目的，需引进一个未知变量q，使得q=x1x2x3，降幂方法如式(3)所示。
3 基于功耗信息的碰撞分析
3.1 基于功耗的碰撞捕获
碰撞的捕获包括功耗采集、相关性匹配两步。实验中功耗信息采集环境如图4 所示：以8 位AVR 微控制器ATMEGA324P 为攻击对象，系统晶振为20MHz。为测量LED加密在某一时刻的能量功耗，在微控制器和稳压电源GND端之间串联了一个阻值为18.2Ω的电阻。加密过程中适时提供触发信号以便示波器采集电阻两端电压，并通过USB数据线将采集到的功耗轨迹传到PC 机。实验中，电压设置为5V，微控制器工作频率为8MHz，数字示波器采样频率为100MS/s。
采集到LED 加密的功耗信息后，从中选取功耗泄露较为明显的算法操作对保证碰撞捕获的准确率十分重要。实验中选取每轮S 盒代换输出的功耗泄露，用数组S[n][m](0
在相关性匹配阶段，将数组S 中的任意两个元素U=S[n1][m1]，V=S[n2][m2]基于Pearson 相关性系数公式(4)进行匹配，若相关系数ρ大于参考阈值则说明两个元素发生碰撞。若对n 轮的S 盒输出进行碰撞捕获，共需要进行216n C次匹配。
3.2 碰撞表示
捕获到碰撞之后需要将其用方程组表示出来。若S[n1][m1]和S[n2][m2]发生碰撞，根据2.2 节中LED 代数方程组的建立方法，有：
中国照明网论文频道现向广大业内朋友征集稿件。稿件内容要求具有技术性、可读性。欢迎研究机构、院校、企业进行投稿。
投稿信箱：edit@lightingchina.com.cn
联系电话：0086-020-85530605-5029
(投稿时请注明作者姓名、单位、邮编和地址及电话、E-mail；以便通知审核结果，如发稿七日内无通知请来电查询。)
广东中照网传媒有限公司 版权所有 增值电信业务经营许可证：粤B2-20050039 粤ICP备06007496号
传真：020-85548112 E-mail：Service@lightingchina.com.cn 中国照明网
