轻量级分组密码SLIM 的差分故障攻击*

高 杨, 王永娟, 高光普, 袁庆军, 王 灿

1. 战略支援部队信息工程大学, 郑州 450001

2. 河南省网络密码技术重点实验室, 郑州 450001

1 引言

随着物联网技术的快速发展, 当前各行业对硬件相关产业的需求愈发旺盛. 在以智能芯片为首的硬件平台中, 传统密码算法暴露出硬件实现成本代价高和电路耗费开支大的现实问题. 为应对该问题, 近年来学界提出了一些适用于这类资源受限设备的分组密码算法, 即轻量级分组密码算法. 相较传统分组密码算法, 轻量级密码使用更简单的组件以减少实现所需的硬件成本, 同时采取更多的迭代轮数以保证其实现安全. 在低功耗情况下, 轻量级分组密码算法仅需要少量硬件和软件资源, 便可为设备提供安全性加密保障.常见的轻量级算法包括LBlock[1]、Piccolo[2]、TWINE[3]、MIBS[4]、PRESENT[5]等, 这些算法在设计时往往考虑到已有的传统攻击方法, 同时保证硬件高效实现, 以达到安全和效率的平衡.

故障攻击由Boneh 等人[6]于1996 年提出用于攻击RSA 签名算法. 1997 年, Biham 等人[7]改进形成差分故障分析方法, 并凭借这种新方法成功攻击了分组密码DES 算法. 差分故障攻击将侧信道攻击和传统密码分析思想结合, 对基于硬件实现的轻量级密码算法攻击效果显著, 近年来, 人们不断提出新的差分故障攻击方法, 成功分析了LED[8]、SIMON[9]、FeW[10]、SM4[11]、KLEIN[12]等密码算法.

轻量级分组密码的基本数据单元均为半字节, 因此往往采用半字节故障注入模型对其进行差分故障分析. 2010 年, Wang 等[13]首次提出将单个随机半字节故障注入PRESENT 算法的密钥扩展方案, 结合其他密码分析方法恢复全轮密钥. 另一方面, 学者对实际攻击中半字节故障注入的实现展开分析研究. 2013年, Moro 等[14]提出了强电磁场故障注入技术. 针对一些实际的现场可编程门阵列和专用集成电路芯片上的实验表明, 该方法可以产生若干半字节故障. 2014 年, Endo 等[15]研究了多点激光注入, 即在运行的密码模块两处或多处同时注入故障, 可在算法的一轮或几轮产生多个半字节故障. 考虑到SLIM 算法每轮中间状态与S 盒数据处理单元均为半字节, 本文采用基于多个半字节的随机故障注入模型进行分析.

轻量级分组密码算法SLIM[16]由Aboushosha 等人于2020 年提出, 分组长度为32 比特, 密钥长度为80 比特. 该算法采用典型的Feistel 结构, 所需硬件成本仅为553 等效门电路, 适用于物联网环境下的射频识别标签及智能卡的防护. 由于SLIM 算法面世时间较短, 目前仅有文献[16] 对其抗线性攻击和差分攻击的安全性进行了分析. 本文采用差分故障攻击方法对SLIM 算法展开研究, 主要成果和创新点如下:基于SLIM 算法的故障扩散规律, 分别在第2 至32 轮注入宽度为1 至4 个半字节的故障, 最少注入62组故障即可将主密钥恢复的计算复杂度降低至23; 在此基础上, 结合S 盒差分分布特性对差分故障攻击的成功率进行定量分析, 计算出各轮轮密钥的恢复概率及主密钥恢复故障注入组数期望值68.15, 对差分故障攻击的理论研究和SLIM 算法的软硬件实现方面均有一定指导意义; 通过1000 次仿真模拟实验, 得到恢复主密钥故障注入组数均值69.07 组, 与理论值较为接近.

2 SLIM 算法简介

2.1 符号说明

本文所用符号如表1 所示.

表1 符号说明Table 1 Symbol description

2.2 SLIM 算法介绍

SLIM 算法是Aboushosha 等人[16]于2020 年提出的一种基于Feistel 结构的轻量级分组密码算法,其分组长度为32 比特, 主密钥长度为80 比特, 迭代轮数为32 轮, SLIM 算法中所有迭代操作都是基于半字节的. 令M=L0||R0表示32 比特明文, 则中间状态为Li=Ri-1,Ri=F(Ri-1)⊕Li-1,i=1,2,··· ,31, 密文输出可表示为C=L32||R32=F(R31)⊕L31||R31, 加密流程如图1 所示. 轮函数F如图2 所示, 其中混淆层S 是轮函数F 的非线性组件, 并列排布着4 个相同的4×4 S 盒, 见表2.

图1 SLIM 算法结构Figure 1 Structure of SLIM algorithm

图2 SLIM 算法轮函数示意图Figure 2 Schematic diagram of round function

表2 SLIM 算法S 盒Table 2 S-box of SLIM algorithm

SLIM 算法P 层基于半字节置换, 如下所示.

SLIM 算法的密钥扩展方案设计思路较为独特, 其主密钥为80 比特, 记为MK = mk79mk78···mk0.首先将主密钥划为5 等份, 分别作为前5 轮轮密钥, 即K1= mk15mk14···mk0,K2= mk31mk30···mk16,K3=mk47mk46···mk32,K4=mk63mk62···mk48,K5=mk79mk78···mk64, 再将MK 存储于两个长度为40 比特的寄存器中, 即MK=MSB||LSB, 每轮寄存器执行下列伪代码(算法1), 并输出16比特轮密钥K.

算法1 密钥扩展算法Input: MSB, LSB Output: Ki 1 for i ＜= 32 do 2LSB = (LSB ≪2)⊕MSB;3LSB = S[LSB39LSB38LSB37LSB36] || ··· || S[LSB3LSB2LSB1LSB0];4MSB = LSB ⊕(MSB ≪3);5Ki = MSB[15 : 0];6i = i+1;7 end

3 SLIM 算法结构性质

3.1 SLIM 算法故障扩散规律

图3 SLIM 算法故障扩散实例Figure 3 Example of fault propagation process in SLIM algorithm

3.2 SLIM 算法S 盒差分分布情况

在SLIM 算法中, 轮函数的非线性变换复杂性基于4 比特S 盒. 因此, 研究S 盒的差分分布特性是很有必要的. 给定α ∈F42(α／=0),m ∈F42, 且满足S(m ⊕α)⊕S(m)=β, 则称m为S 盒输入值,α为S盒输入差分,β为S 盒输出差分. SLIM 算法S 盒在输入差分一定情况下输出差分与输入值的对应关系如表4 所示.

表4 SLIM 算法S 盒差分分布表Table 4 Differential distribution table of S-box in SLIM

观察该表, 容易归纳出SLIM 算法S 盒的差分分布统计特性:

(1) 固定输入值m, 共有15 种可能的“输入-输出”差分对(Din,Dout), 且Din与Dout分别遍历0x1到0xF 这15 个数;

(2) 当m一定时, (1) 中的15 组(Din,Dout) 有3 组对应可能输入值记为集合Y1, 3 组对应可能输入值记为集合Y2, #Y1=#Y2=4; 其余9 组对应可能输入值记为集合Zi(i=1,2,··· ,9),#Zi=2;

(3)Y1∩Y2=m;

(4)Zi ∩Zj=m,(i,j=1,2,··· ,9);

(5) 固定输入差分Din, 对应输出差分Dout可能有4, 6, 7, 8 种取值, 不存在Dout为5 种的情况.

4 SLIM 算法的差分故障攻击

本文采用基于多个半字节的随机故障注入模型对SLIM 算法进行分析, 在此给出攻击条件以及具体假设:

(1) 攻击者可以完全掌握密码设备, 可在加密过程中任意时刻任意位置注入若干半字节的随机故障.故障值非零, 但具体值未知.

(2) 攻击者可以在同一位置重复多次注入随机故障.

(3) 攻击者可以反复重启密码设备, 加密相同的明文和初始密钥.

4.1 攻击模型分析

为求解差分方程, 可在S 盒差分分布表中搜索. 首先进行一次故障注入, 找到满足差分方程的密钥候选值集合, 再进行多次故障注入, 对所得多个密钥候选值集合求交集, 可得半字节轮密钥的具体值. 特别地, 由表3 知右半部分注入的半字节故障相互之间对密文没有影响, 因此可在一轮中同时注入多个半字节故障进行差分故障分析.

表3 故障扩散位置索引Table 3 Index of fault diffusion position

下面进行主密钥MK=MSB||LSB 的恢复. 为表示方便, 记密钥扩展算法第r轮结束时寄存器LSB与MSB 的状态分别为Ur和V r. 首先考虑已知K32和K31条件下K30的恢复, 根据密钥扩展算法可知,V32=S[(U31≪2)⊕V31]⊕(V31≪3), 即U31≪2 =S-1[V32⊕(V31≪3)]⊕V31, 于是有下列等式成立:

4.2 攻击流程

表5 不同轮中故障注入宽度Table 5 Width of fault injection in different rounds

5 复杂度分析

证明: 由差分分布表统计特性(2) 知, 对于某一差分方程, 当两组故障注入后所得可能输入值集合完全相同时, 需要继续注入故障. 反之, 若两次所得可能输入值集合不同, 求其交集即为差分方程的解. 具体情形如图4 所示.

图4 两组故障注入后差分方程有无唯一解的情形Figure 4 Conditions whether or not differential equations have unique solutions

注入l组故障后各轮密钥Kr(r=2,3,··· ,32) 的恢复概率均可计算得到, 如表6 所示:

表6 不同故障注入组数下轮密钥恢复概率(%)Table 6 Probability of round key recovery in different times of faults injection (%)

6 结果对比

6.1 与其他轻量级分组密码的对比

随着侧信道分析技术的发展, 近两年提出的轻量级算法通常具备一定的抗故障攻击能力. SLIM 算法的抗差分故障分析手段主要体现在采用了较为复杂的密钥扩展方案. 早期轻量级分组密码密钥扩展方案往往采用类似PRESENT 算法的设计, 如2009 年提出的MIBS, 2011 年提出的LBlock 等. 在此类算法中求出倒数3 至5 轮密钥即可逆推主密钥. 在SLIM 算法中, 由于采用LSB 和MSB 两个互相影响的寄存器存储密钥中间值, 无法仅通过倒数若干轮密钥完成主密钥的恢复. 表7 给出了半字节故障模型下常见轻量级分组密码算法的差分故障分析结果.

表7 轻量级分组密码差分故障分析结果对比Table 7 Comparison of differential fault analysis results of lightweight block ciphers

6.2 不同故障注入策略的对比

7 实验仿真结果及分析

7.1 实验环境

硬件配置为一台PC 机(CPU 为Intel®CoreTM i7-10875H 5.0 GHz, 操作系统为64 位, 内存为12 GB), 编程环境为Microsoft Visual Studio 2015 平台下的Visual C++ 语言.

7.2 实验结果

明文选取12 345 678, 80 比特主密钥随机选取. 为了消除模拟故障注入过程中的人工干预, 采用轻量级流密码Trivium 算法生成伪随机01 数据流, 随机截取4 比特作为故障值. 模拟1000 组试验, 实验结果如图5 所示. 经计算, 恢复主密钥MK 所需故障注入组数均值为69.07 组, 与理论期望值较为接近. 表8 给出十次实验中各轮故障注入组数.

表8 十次实验中各轮故障注入组数Table 8 Number of fault injections per round in 10 experiments

图5 恢复主密钥所需故障注入总组数对应的实验组数Figure 5 Number of experiments corresponding to total number of fault injections

8 结束语

本文针对SLIM 算法提出了一种基于半字节的故障攻击策略, 在第2 至32 轮注入宽度为1 至4 个半字节的故障, 可将恢复主密钥MK 的计算复杂度降低至23. 通过分析轮函数故障扩散规律和S 盒差分分布特性, 运用相关数学知识求取轮密钥恢复概率, 并计算恢复主密钥所需故障注入组数期望68.15. 进一步地, 利用软件进行1000 次仿真实验, 故障注入组数均值为69.07 组, 与理论期望值较为接近. 文中对SLIM 算法差分故障攻击的复杂度分析和成功率证明, 为研究其他轻量级密码算法的故障攻击成功率提供了思路, 下一步将针对其他密码算法展开类似讨论和研究. 另一方面, 在后续研究中将继续探索减小故障注入宽度的方法, 尽可能通过少量故障恢复密钥值, 从而提升故障攻击效率, 同时运用已有结论分析SLIM算法硬件实现中抗差分故障攻击的相关性能.

作者信息

高杨(1994-), 河南洛阳人, 硕士. 主要研究领域为密码算法设计与侧信道分析.gaoyang_1279@126.com

王永娟(1982-), 河南开封人,研究员. 主要研究领域为侧信道分析与密码系统安全.pinkywyj@163.com

高光普(1984-), 天津人, 讲师.主要研究领域为对称密码设计与分析.guangpu.gao@gmail.com

袁庆军(1993-), 河北衡水人,讲师. 主要研究领域为侧信道攻击与防护技术.gcxyuan@outlook.com

王灿(1999-), 四川达州人, 硕士研究生在读. 主要研究领域为侧信道分析.1095976715@qq.com

附录

表8 中实验1 具体攻击流程:

明文为12 345 678, 80 比特主密钥随机选取(程序预置), 截取Trivium 算法生成数据流(非零) 作为故障值:

K29K28K27K26K25K24K23 1a991be4556655585bbd90bfd993 K22K21K20K19K18K17K16 b99508b9e2be0133b07c52bb4386 K15K14K13K12K11K10K9 23edc10a257c75cc8c45d7e203bf K8K7K6K5K4K3K2 16a06704d4d98d26ca73d166141d

(11) 由密钥扩展方案结合文中4.1 节分析可推知K1左13 比特为1001101010011, 穷举剩余3 比特可得K1的值为9a9b, 至此恢复出完整主密钥值8d26ca73d166141d9a9b.

在实际攻击过程中, 差分方程为S(K ⊕R)⊕S(K ⊕R*)=L ⊕L*的形式, 上述攻击流程中密钥侯选值集合与表4 中m解集不同, 但该方程可以转化为S(m)⊕S(m ⊕f) =f′, 具有与表4 相同的S 盒差分分布统计特性.