2. 浙江大学 信息与电子工程学院, 浙江 杭州 310027;
3. 九八〇四厂军代室, 云南 曲靖 655000
2. College of Information Science and Electrical Engineering, Zhejiang University, Hangzhou 310027, China;
3. The Nine Eight Zero Four Military Representative Office, Qujing 655000, China
SIMON系列轻量级分组密码[1]由美国国家安全局在2013年提出, 主要用于资源受限环境.SIMON密码由于设计简单(大部分SIMON密码门电路数量小于1 000) 且灵活性较高, 在硬件和软件方面均表现出优越的性能, 受到了广泛关注.SIMON密码“ & ”运算的低次性使其易遭受各类攻击, 因此针对SIMON密码的安全性评估研究较多, 主要有线性攻击[2-3]、不可能差分攻击[4]、差分攻击[5-6]以及代数攻击[7]等.
目前, 针对SIMON密码的立方攻击和故障攻击研究如下.Rabbaninejad等[8]对SIMON32/64进行立方和动态立方攻击, 破解全部密钥的计算复杂度分别为251.49和251.09.Tupsamudre等[9]对SIMON系列密码进行了传统差分故障分析.基于单比特故障模型的研究结论如下：“SIMON系列密码倒数第2轮左半部分每注入1 bit故障可恢复最后一轮2 bit轮密钥”.在文献[8]中, 由于多项式次数和项数随轮数呈指数级增长, 导致得到的立方体维数较大, 计算复杂度较高, 仅能实现约简轮SIMON32/64的攻击.文献[9]利用差分推导进行故障定位, 仅适用于倒数第2轮左半部分故障注入, 单独对左半部分进行故障注入在实际攻击中较难实现.此外, 差分故障分析需要结合具体密码进行推导, 自动化程度较差.
针对上述不足, 本文将立方与故障结合, 给出故障立方攻击方法.目前旁路立方攻击采用的泄露模型主要是基于中间状态泄露的模型, 如：单比特模型[10-11]和汉明重模型[12-13], 而基于故障信息泄露的旁路立方攻击研究较少.曾文[14]针对流密码提出一种“fault-cube”方法, 通过故障将高维立方体截成2个低维立方体, 并对其分别进行立方攻击.该方法对1 056拍以下的Trivium算法有效, 计算复杂度不超过253.Abdul-latip等[15]结合立方, 对KATAN系列分组密码进行故障攻击, 通过115次故障注入, 将KATAN32的计算复杂度降低为259.
本文利用故障立方攻击对SIMON系列密码进行安全性评估研究.给出故障立方攻击基本原理和模型, 在此基础上对3种SIMON系列密码进行攻击.通过仿真实验验证了故障立方攻击有效性, 并将该方法与立方攻击和故障攻击对比分析.
1 相关知识 1.1 SIMON系列密码SIMON系列轻量级分组密码采用平衡Feistel结构, 为了提高算法灵活性, 设计者提供了10个版本, 均可用SIMON 2n/(en)表示.其中n为字长, 2n为分组长度, en表示密钥长度.本文选取的研究对象是SIMON32/64、SIMON48/72和SIMON64/96, 对应的算法轮数分别为32、36、42轮.
SIMON系列密码的轮函数主要包含3种操作：按位异或(⊕)、按位与( & )、循环左移( < < < ).设Lr和Rr分别表示经过r轮加密后中间状态的左半部分和右半部分, Kr为轮密钥, 则SIMON系列密码每一轮加密过程表示为
| $ {L_{r + 1}} = F\left( {{L_r}} \right) \oplus {R_r} \oplus {K_r},{R_{r + 1}} = {L_r}. $ | (1) |
式中：F(Lr)=((Lr < < < 1) & (Lr < < < 8))⊕(Lr < < < 2).
SIMON系列密码轮函数的具体结构如图 1所示.SIMON的核心为" & "运算, 相比于代数方程最高次数为3的S盒、代数方程最高次数为d的模加运算(d为运算单位二进制长度), " & "运算后的代数方程最高次数仅为2, 具有低次性的特点.
|
图 1 SIMON系列分组密码轮函数 Fig. 1 Round function of SIMON family block ciphers |
若将任意密码算法看作一个黑盒, 则输出结果的每一位都能表示成关于u位明文变量v1, v2, …, vu以及l位密钥变量w1, w2, …, wl的多项式p(v, w).假设I是明文集合{v1, v2, …, vu}的子集, I中变量下标的集合为{y1, y2, …, ym}, 令
| $ {t_1} = \prod\nolimits_{y \in \left\{ {{y_1},{y_2}, \cdots ,{y_m}} \right\}} {{v_y}} , $ |
则通过tI可以将多项式p(v, w)分解为
| $ p\left( {v,w} \right) = {t_1} \cdot {p_{S\left( I \right)}} + q\left( {v,w} \right). $ | (2) |
式中:pS(I)为关于密钥w的多项式, q(v, w)为所有不能被tI整除项的累积和.特别地, 当pS(I)最高次等于1时, 称tI为极大项, pS(I)为超级多项式.
立方攻击实现的关键在于下列定理的成立.
定理1[16]集合CI={(v1, v2, …, vu), 当y=y1, y2, …ym时, vy=0, 1;当y≠y1, y2, …ym时, vy的取值固定, 那么
| $ \sum\limits_{{v_1},{v_2}, \cdots ,{v_u} \in {C_I}} {p\left( {v,w} \right)} \equiv {p_{S\left( I \right)}}\bmod 2. $ |
立方攻击可分为预处理阶段和在线分析阶段.预处理阶段主要利用下式判断立方体对应的pS(I)是否为关于密钥的线性或二次函数, 其中a, b, c∈{0, 1}l, l为密钥比特位数:
| $ {p_{S\left( I \right)}}\left( 0 \right) + {p_{S\left( I \right)}}\left( \mathit{\boldsymbol{a}} \right) + {p_{S\left( I \right)}}\left( \mathit{\boldsymbol{b}} \right) = {p_{S\left( I \right)}}\left( {\mathit{\boldsymbol{a}} + \mathit{\boldsymbol{b}}} \right), $ | (3) |
| $ \begin{array}{l} {p_{S\left( I \right)}}\left( 0 \right) + {p_{S\left( I \right)}}\left( \mathit{\boldsymbol{a}} \right) + {p_{S\left( I \right)}}\left( \mathit{\boldsymbol{b}} \right) + {p_{S\left( I \right)}}\left( \mathit{\boldsymbol{c}} \right) + {p_{S\left( I \right)}}\left( {\mathit{\boldsymbol{a}} + \mathit{\boldsymbol{b}}} \right) + \\ {p_{S\left( I \right)}}\left( {\mathit{\boldsymbol{a}} + \mathit{\boldsymbol{c}}} \right) + {p_{S\left( I \right)}}\left( {\mathit{\boldsymbol{b}} + \mathit{\boldsymbol{c}}} \right) = {p_{S\left( I \right)}}\left( {\mathit{\boldsymbol{a}} + \mathit{\boldsymbol{b + c}}} \right). \end{array} $ | (4) |
在线阶段利用预处理阶段获得的立方体, 通过0/1赋值, 对目标比特进行累加以获取对应多项式的值.立方攻击的详细内容可参考文献[17].
1.3 故障攻击故障攻击[18]是一种利用密码设备在外界干扰下(温度、电压等)产生的故障行为或错误信息来恢复密钥的攻击方法.1997年, Biham等[19]结合差分分析与故障攻击, 提出了差分故障攻击.
差分故障攻击通常根据某一非线性部件的差分特性进行分析.现有的故障注入技术按照成本和精度可分为高成本和低成本故障注入技术[20].如果攻击者可以承受较高的预算, 则不能忽略一些高成本故障注入技术可能造成的潜在威胁.高成本故障技术通过直接访问硅片, 可以将故障精确地注入芯片中, 攻击威胁较大.利用这类技术可实现本文特定轮单比特故障注入模型, 该类技术主要有3种, 如表 1所示.
|
表 1 高成本故障注入技术 Table 1 High-cost fault injection technology |
本文故障模型设定如下：
a)攻击者掌握了密码设备, 可在任意加密轮注入单比特随机翻转故障(即某一中间状态位由“0”变为“1”或由“1”变为“0”)；
b)攻击者只能控制故障注入轮数, 而不知道故障注入该轮的准确位置；
c)攻击者能够重启密码设备，使其恢复初始状态, 即密码设备允许反复注入单比特故障.
定义 1 设某SIMON密码算法Λ的加密轮数为T, 明密文长度都是2n, 轮密钥长度为n.攻击者在t时刻向Λ第s(1≤s≤T)加密轮中间状态X注入单比特随机故障α, 生成错误密文C′.假设故障注入了一个未知的位置xs+i(i为该轮的某一比特位), 错误密文C′与正确密文C的差值是ΔC=(Δc0, Δc1, …, Δc2n-1).第s轮轮密钥表示为k(s-1)+0, k(s-1)+1, …, k(s-1)+n-1.
根据代数攻击思想, 在正常加密情况下密文C的某一比特cj可以看成是关于某一轮s中间状态xs+0, xs+1, …, xs+2n-1和(s+1)~T轮所有轮密钥ks+0, bs+1, …, k(T-1)+n-1的布尔函数.将密文比特cj看作立方攻击中的目标多项式p(v, kk), 将故障注入位xs+i看作tI, 可以得到推论1.
推论 1 假设cj是正确密文C的某一比特, xs+i是s轮某一中间状态比特, 则在xs+i处注入故障后, Δcj可表示为关于s轮中间状态xs+0, xs+1, …, xs+2n-1和(s+1)~T轮所有轮密钥ks+0, ks+1, …, k(T-1)+n-1, 但不包含xs+i的一个特定布尔函数.
证明：如果将第s轮之后的加密过程分割出来单独考虑, 则cj可以表示为关于s轮中间状态和(s+1)~T轮所有轮密钥的布尔函数cj(xs+0, xs+1, …, xs+2n-1, ks+0, ks+1, …, k(T-1)+n-1), 令
| $ \begin{array}{*{20}{c}} {X = \left\{ {{x_{s + 0}},{x_{s + 1}}, \cdots ,{x_{s + i - 1}},{x_{s + i + 1}},{x_{s + i + 2}}, \cdots ,{x_{s + 2n - 1}}} \right\},}\\ {K = \left\{ {{k_{s + 0}},{k_{s + 1}}, \cdots ,{k_{\left( {T - 1} \right) + n - 1}}} \right\},} \end{array} $ |
则有
| $ \begin{array}{l} {c_j}\left( {{x_{s + 0}},{x_{s + 1}}, \cdots ,{x_{s + 2n - 1}},{k_{s + 0}},{k_{s + 1}}, \cdots ,{k_{\left( {T - 1} \right) + n - 1}}} \right) = \\ \;\;{x_{s + i}} \cdot p\left( {X,K} \right) + q\left( {X,K} \right). \end{array} $ | (5) |
式中：p(X, K)和q(X, K)表示关于集合X和集合K中元素的布尔函数.
将xs+i看作式(2) 的tI, 将集合X和集合K中变量看作未知量.令集合CI={0, 1}, 由于xs+i和xs+i⊕1一定能取遍CI, 根据定理1可知
| $ \begin{array}{l} {c_j}\left( {{x_{s + 0}},{x_{s + 1}}, \cdots ,{x_{s + i}}, \cdots ,{x_{s + 2n - 1}},K} \right) \oplus \\ \;\;\;\;{c_j}\left( {{x_{s + 0}},{x_{s + 1}}, \cdots ,{x_{s + i}} \oplus 1, \cdots ,{x_{s + 2n - 1}},K} \right) = \\ \;\;\;\;\sum\limits_{{x_{s + i}} \in {C_I}} {{c_j} \equiv p\left( {X,K} \right)\bmod 2} . \end{array} $ | (6) |
故障注入后有
| $ \begin{array}{l} \Delta {c_j}\left( {{x_{s + 0}},{x_{s + 1}}, \cdots ,{x_{s + i}}, \cdots ,{x_{s + 2n - 1}},K} \right) \oplus \\ \;\;{c_j}\left( {{x_{s + 0}},{x_{s + 1}}, \cdots ,{x_{s + i}} \oplus 1, \cdots ,{x_{s + 2n - 1}},K} \right). \end{array} $ | (7) |
综合式(6)、式(7) 易得
| $ \Delta {c_j} \equiv p\left( {X,K} \right)\bmod 2. $ | (8) |
综上, Δcj是一个不包含xs+i的特定布尔函数.利用推论1可将故障与立方结合, 高效地获取密钥, 故障立方攻击模型如图 2所示.由于现有立方攻击仅能提取线性和二次多项式, 故障立方攻击实现条件如下：目标轮存在xs+i, 使得密文某比特cj对应的p(X, K)最高次≤2.通过初步研究发现, SIMON密码低次性特点恰好符合这一要求.
|
图 2 故障立方攻击模型 Fig. 2 Model of fault-cube attack |
为获得尽可能多的多项式以求解密钥, 攻击者需要统计每一轮p(X, K)为线性或二次多项式的数量, 最多的即为候选故障注入轮.假设要分析第s轮, 令xs+i(0≤i≤2n-1) 表示第s轮中间状态比特, cj(0≤j≤2n-1) 表示密文比特, 循环遍历每一对(xs+i, cj), 考察其对应p(X, K), 利用式(3) 和(4) 可判断该多项式是否为线性或二次多项式.利用上述方法统计3种SIMON密码各轮线性及二次多项式数量，如图 3所示, δ为多项式个数, s为故障注入轮.观察发现：SIMON32/64、SIMON48/72、SIMON64/96候选故障注入轮分别为30轮、34轮和40轮.
|
图 3 各轮低次多项式数量统计 Fig. 3 Statistics of low-degree polynomials for different rounds |
在确定了故障注入轮后, 攻击者对该轮进行单比特随机故障注入.为确定故障注入位置, 每次选择一个xs+i, 观察密文比特的差分特征.由式(8) 可知, 密文比特差分就是p(X, K), 如果该多项式的值是常数“0”或“1”, 则当故障注入xs+i时, 密文比特差分一定是特定值“0”或“1”, 由此可构建某一轮xs+i的密文差分特征表.
以SIMON32/64密码为例, 计算第30轮差分特征表，结果如表 2所示.第i行代表在xs+i处注入故障后得到的密文差分, 第j列代表故障注入后第j比特的密文差分Δcj.“0”和“1”表示该位密文差分是确定值, “*”表示该位密文差分不确定.如果32位密文差分和表 2中的第i行吻合, 则证明故障注入位是xs+i.
|
|
表 2 SIMON32/64第30轮故障注入差分特征表 Table 2 Difference-characteristics table for SIMON32/64 with 30th faulty round |
利用差分特征表进行推断也存在一些不确定性.例如, 第6行和第20行分别为
| $ \begin{array}{l} 001 * * 0 * 00000 * 0000001 * 00000000 * 0,\\ 001 * 00000000 * 0000000100000000000. \end{array} $ |
在某些情况下, 密文差分可能同时满足第6和第20行.为此, 本文提出一种策略：如果存在密文差分同时满足某2行的情况, 判定“*”较少的行对应的中间比特为故障注入位, 证明如下.
规则：存在第φ1行和第φ2行同时满足密文差分, 这2行中“*”数量分别为λ和μ.如果λ≥μ, 则输出φ2, 否则输出φ1.
证明：如果将密文差分的每一比特看作相互独立的变量, 可以得出差分表第φ1行和第φ2行满足密文差分的概率分别为
| $ {P_\lambda } = {\left( {\frac{1}{2}} \right)^\lambda }\left[ {1 - {{\left( {\frac{1}{2}} \right)}^\mu }} \right],{P_\mu } = {\left( {\frac{1}{2}} \right)^\mu }\left[ {1 - {{\left( {\frac{1}{2}} \right)}^\lambda }} \right]. $ |
若存在λ≥μ, 则有
| $ \begin{array}{l} {P_\lambda } = {\left( {\frac{1}{2}} \right)^\lambda } \cdot \left[ {1 - {{\left( {\frac{1}{2}} \right)}^\mu }} \right] \le \frac{1}{2}\left[ {{{\left( {\frac{1}{2}} \right)}^{2\lambda }} + } \right.\\ \;\;\;\;\;\;\;\;\left. {{{\left( {1 - {{\left( {\frac{1}{2}} \right)}^\mu }} \right)}^2}} \right] = \frac{1}{2} - {\left( {\frac{1}{2}} \right)^\mu } + {\left( {\frac{1}{2}} \right)^{2\mu + 1}} + \\ \;\;\;\;\;\;\;\;{\left( {\frac{1}{2}} \right)^{2\lambda + 1}} \le \frac{1}{2} - {\left( {\frac{1}{2}} \right)^\mu } + 2 \times {\left( {\frac{1}{2}} \right)^{2\mu + 1}} = \\ \;\;\;\;\;\;\;\;\frac{1}{2} - {\left( {\frac{1}{2}} \right)^\mu } + {\left( {\frac{1}{2}} \right)^{2\mu }} < \frac{1}{2}. \end{array} $ |
因此, 第φ2行满足密文差分概率更大.λ < μ的证明与此类似.
针对SIMON32/64第30轮差分特征表进一步研究发现, 所有可能出现冲突的行号组合(6, 20)、(1, 31)、(0, 30)、(13, 27)、(4, 18)、(7, 21)、(9, 23)、(5, 19)、(15, 29)、(12, 26)、(2, 16)、(3, 17)、(11, 25)、(8, 22)、(14, 28)、(10, 24), 都有λ=7和μ=2.因此对于SIMON32/64第30轮差分特征表来说, “*”较多的行为故障注入位的概率：
| $ {P_\lambda } = {\left( {\frac{1}{2}} \right)^\lambda }\left[ {1 - {{\left( {\frac{1}{2}} \right)}^\mu }} \right] = \frac{3}{{512}}. $ |
这一概率较小, 后续仿真实验进一步证实了利用上述策略对SIMON32/64第30轮故障定位的成功率达到100%.实际成功率高于理论值, 因为在本文的理论分析中, “*”是相互独立的, 事实上可能并非如此.以SIMON32/64第30轮第0 bit注入单比特故障为例说明“*”之间并非相互独立的.
如图 4所示为手工推导故障传播路径, 阴影部分为受影响比特位(比特值不一定发生变化), 其余为不受影响的比特位.另取表 2第0行列于图 4下方, 假设s轮的比特值依次为Ls, 0, Ls, 1, …, Ls, 15, Rs, 0, Rs, 1, …, Rs, 15, 而L(R)s, η受影响后表示为L(R)′s, η.在差分表第0行的7个“*”分别为ΔLT, 0, ΔLT, 6, ΔLT, 7, ΔLT, 13, ΔLT, 14, ΔRT, 8, ΔRT, 15.依次推导出密文每一个阴影部分的差分值:
|
图 4 SIMON32/64第30轮第0 bit故障传播路径 Fig. 4 Fault propagation path of 0 bit in SIMON32/64 with 30th faulty round |
| $ \Delta {L_{T,0}} = \left( {{L_{T - 1,8}}\;\& \;{L_{T - 1,1}}} \right) \oplus \left( {{{L'}_{T - 1,8}}\;\& \;{L_{T - 1,1}}} \right) \oplus 1, $ |
| $ \begin{array}{l} \Delta {L_{T,6}} = \left( {{L_{T - 1,7}}\;\& \;{L_{T - 1,14}}} \right) \oplus \left( {{L_{T - 1,7}}\;\& \;{{L'}_{T - 1,14}}} \right) \oplus \\ \left( {{L_{T - 1,8}}\;\& \;{{L'}_{T - 1,8}}} \right), \end{array} $ |
| $ \Delta {L_{T,7}} = \left( {{L_{T - 1,8}}\;\& \;{L_{T - 1,15}}} \right) \oplus \left( {{{L'}_{T - 1,8}}\;\& \;{L_{T - 1,15}}} \right), $ |
| $ \Delta {L_{T,12}} = {L_{T - 1,14}} \oplus {{L'}_{T - 1,14}} = \Delta {L_{T - 1,14}} = 1, $ |
| $ \begin{array}{l} \Delta {L_{T,13}} = \left( {{L_{T - 1,14}}\;\& \;{L_{T - 1,5}}} \right) \oplus \left( {{{L'}_{T - 1,14}}\;\& \;{L_{T - 1,5}}} \right) \oplus \\ \left( {{L_{T - 1,15}}\;\& \;{{L'}_{T - 1,15}}} \right), \end{array} $ |
| $ \Delta {L_{T,14}} = \left( {{L_{T - 1,15}}\;\& \;{L_{T - 1,6}}} \right) \oplus \left( {{{L'}_{T - 1,15}}\;\& \;{L_{T - 1,6}}} \right), $ |
| $ \Delta {R_{T,8}} = \Delta {L_{T - 1,8}} = {L_{T - 1,8}} \oplus {{L'}_{T - 1,8}}, $ |
| $ \Delta {R_{T,14}} = \Delta {L_{T - 1,14}} = 1, $ |
| $ \Delta {R_{T,15}} = \Delta {L_{T - 1,15}} = {L_{T - 1,15}} \oplus {{L'}_{T - 1,15}}. $ |
以ΔLT, 0和ΔRT, 8为例, 发现LT-1, 8和L′T-1, 8会同时对两者的值产生影响.为进一步证明, 随机选取100 000组明文、密钥及故障作为样本, 计算得相关系数：
| $ \rho = \frac{{{\rm{Cov}}\left( {\Delta {L_{T,0}},\Delta {R_{T,8}}} \right)}}{{\sqrt {D\left( {\Delta {L_{T,0}}} \right)} \sqrt {D\left( {\Delta {R_{T,8}}} \right)} }} = - 0.579602, $ |
从而证明其并非相互独立.类似地, 可计算出其余“*”值之间也并非相互独立.
以随机明文P=0x 6120 6e69, 初始密钥(k3, k2, k1, k0)=0x 1211 100a 0908 0201为例, 在第30轮注入单比特随机故障, 如表 3所示为利用差分特征表推断故障比特的过程.分析结果表明：利用上述方法, 可准确定位0~31故障比特.
|
|
表 3 基于SIMON32/64第30轮差分特征表的故障比特推断 Table 3 Faulty bits deduction of 30th round in SIMON32/64 with difference-characteristics table |
利用故障注入将目标轮到最后一轮加密过程分离出来, 等效于约简轮立方攻击.求解轮密钥分为离线阶段和在线阶段.离线阶段利用立方攻击, 寻找低次多项式(线性或者二次).若故障注入位xs+i和密文比特cj对应的p(X, K)是低次多项式, 则将(xs+i, cj)放入一个特定集合Ф, 并记录该多项式.在线阶段随机注入故障, 如果判断故障注入位与集合Ф中某元素的xs+i一致, 则相应密文差分Δcj即为对应多项式的值.
针对SIMON32/64第30轮的故障立方攻击找到112个二次多项式和32个线性多项式, 表 4列举了其中一部分.在上述144个多项式中, 排除冗余以及次数过高无法利用的多项式, 筛选得到32个多项式, 如表 5所示.
|
|
表 4 SIMON32/64第30轮多项式举例 Table 4 Equations for example of SIMON32/64 in round 30 |
|
|
表 5 SIMON32/64第30轮多项式的筛选结果 Table 5 Selected equations of SIMON32/64 in round 30 |
对SIMON48/72第34轮实施故障立方攻击, 筛选后得到24个二次多项式和24个线性多项式.类似地, SIMON64/96第40轮筛选后得到32个二次和32个线性多项式, 受篇幅限制不再一一列举.
4 仿真实验与复杂度分析 4.1 利用差分特征表进行故障定位的成功率分析编程模拟利用SIMON32/64各轮差分特征表(以下简称“差分表”)确定故障位置的过程.定义故障注入轮到密文输出之间的故障传播轮数为故障深度, 记为fd=T-s.不同故障深度分别随机选取100组明文、密钥及故障注入位置, 观察每组数据的密文差分在差分表中匹配的行数, 如图 5所示.图中, ε为实验样本, θ为密文差分在差分表中匹配的行数.分析实验结果发现：随故障深度fd增加, 密文差分在差分表中匹配的行数越来越多, 由此也导致定位成功率下降.
|
图 5 差分特征表故障定位仿真结果 Fig. 5 Simulation results of fault determination with difference-characteristics table |
进一步模拟SIMON48/72和SIMON64/96利用差分表定位的过程.当故障深度fd∈[1, 6]时, 这3种SIMON密码差分表定位情况如
图 6所示.其中, χ为故障定位成功率.
|
图 6 SIMON系列密码差分表定位成功率 Fig. 6 Success rates for fault determination with difference-characteristics table of SIMON family ciphers |
观察发现：1) 差分表定位成功率随故障深度增加而呈下降趋势；2) 这3种SIMON密码候选故障注入轮的差分表定位成功率均为100%, 因此第3.1节确定的轮数可认为是最佳故障注入轮；3) 当fd≤4时, 3种密码的定位成功率均≥96%.
文献[9]利用差分推导仅能实现故障深度为2的左半部分故障注入的定位, 而本文方法能够实现故障深度为4任意位置的故障定位, 且通用性良好, 可以为其他分组密码故障定位提供一定的借鉴.
4.2 计算复杂度以SIMON32/64为例介绍如何利用第3.3节获得的多项式, 结合密钥猜测攻击, 获取初始密钥.由密钥迭代公式[1]可知, 要恢复初始密钥必须得到任意连续4轮密钥.从第30轮至最后一轮的加密过程如图 7所示.其中，CL和CR分别为密文C的左半部分和右半部分.
|
图 7 SIMON最后2轮加密过程 Fig. 7 SIMON encryption process for last two rounds |
观察表 5发现, 通过线性多项式攻击者可得到L30(xs+0, xs+1, xs+2, …, xs+15), 分析第32轮加密过程, 由SIMON轮函数可得
| $ {K_{31}} = F\left( {{L_{31}}} \right) \oplus {R_{31}} \oplus {C_{\rm{L}}}. $ | (9) |
由于L31=CR, R31=L30, 利用式(9) 易求得第32轮密钥k31+i.此外, 利用表 5中二次多项式还可求得R30⊕K30, 猜测第31轮密钥K30, 可以得到R30, 此时第30轮中间状态全部获得.继续猜测第30轮和第29轮密钥, 得到连续4轮密钥, 进一步可恢复全轮密钥信息.将获得的密钥带入1~30轮加密过程(第30轮中间状态比特全部获得)验证猜测是否正确, 计算复杂度为
| $ \frac{{30}}{{32}} \times {2^{48}} \approx {2^{47.91}}. $ |
故障注入后得到方程都是低次的, 求解时间可忽略不计, 因此故障立方攻击和密钥猜测总的计算复杂度约为247.91.类似地, 可求得对SIMON48/72、SIMON64/96攻击总计算复杂度分别为247.92和263.93.
4.3 数据复杂度用平均注入故障数来评估数据复杂度.理论上, SIMON32/64要覆盖表 5中的故障注入位最少需要8次故障注入.通过软件模拟故障随机注入过程, 对SIMON32/64进行10 000次攻击, 平均故障注入次数为69次, 多于文献[9]的仿真结果25次, 原因如下：该文献假设能够对倒数第2轮左半部分进行故障注入, 假设条件较强.同理, 可得到其余2种SIMON密码的故障注入情况：对SIMON48/72进行10 000次攻击, 平均故障注入次数为128次；对SIMON64/96进行10 000次攻击, 平均故障注入次数为185次.
4.4 结果分析本文对SIMON32/64密码的故障立方攻击结果与文献[8]进行的立方攻击研究成果对比如表 6所示.本文中69次故障注入相当于69×2≈27.11个选择明文, 数据复杂度为27.11.相比于立方攻击和动态立方攻击, 故障立方攻击在数据复杂度和计算复杂度方面都更优.
|
|
表 6 SIMON32/64立方攻击对比 Table 6 Comparison of cube attacks on SIMON32/64 |
对比本文的故障立方攻击结果与文献[9]差分故障攻击结果.以SIMON32/64为例, 本文通过对第30轮最少8次的故障注入, 利用提取的多项式可恢复第32轮16比特密钥, 与文献[9]中“倒数第2轮每一比特故障可恢复最后一轮2bit密钥”的结论一致.相比于传统的差分故障攻击, 故障立方攻击存在下列优点：
1) 故障定位方法有效性好, 更易实现.利用差分表进行故障定位可实现SIMON32/64倒数4轮任意故障注入位置定位, 成功率≥96%, 文献[9]仅能对倒数第2轮左半部分进行故障定位；此外, 相比文献[9]单独对目标轮左半部分进行故障注入的模型, 本文采用的随机故障注入模型更易实现.
2) 避免了繁琐的差分分析过程, 自动化程度高.故障立方攻击将传统的手工分析转化为搜索线性或二次多项式的过程, 自动化程度高, 且对不同密码攻击过程是通用的.
5 结语本文给出一种故障立方攻击方法, 对SIMON系列密码安全性进行评估研究.结合代数攻击思想和立方攻击原理给出故障立方攻击所需推论, 在此基础上分3步进行：确定故障注入轮、确定单比特故障注入位、利用立方攻击提取的低次多项式恢复部分轮密钥并结合密钥猜测攻击恢复全轮密钥.结果表明：故障立方攻击在复杂度方面优于此前的立方攻击.相比于差分故障攻击, 本文的故障模型更加贴近实际, 自动化程度较高.此外, 本文给出的方法通用性好, 可为其他轻量级分组密码提供一定借鉴.
本文方法仍存在下列不足：1) 由于不能直接求解密钥, 搜索得到的一部分二次多项式并未得到充分利用；2) 故障注入深度仅为倒数第2轮, 能够覆盖到的轮密钥数量有限.因此, 如何充分利用二次多项式及增加故障注入深度是故障立方攻击下一步的研究方向.
| [1] | BEAULIEU R, SHORS D, SMITH J, et al. The SIMON and speck families of lightweight block ciphers[EB/OL]. (2013-06-19)[2016-11-30]. http://eprint.iacr.org/2013/404.pdf. http://eprint.iacr.org/2013/404.pdf |
| [2] | ALIZADEH J, BAGHERI N, GAURAVARAM P, et al. Linear cryptanalysis of round reduced SIMON[EB/OL]. (2014-10-16)[2016-11-30]. http://eprint.iacr.org/2013/663.pdf. http://eprint.iacr.org/2013/663.pdf |
| [3] | KÖLBL S, LEANDER G, TIESSEN T. Observations on the SIMON block cipher family[C]//Proceedings of the 35th International Cryptology Conference. SantaBarbara:Springer, 2015:161-185. https://rd.springer.com/chapter/10.1007/978-3-662-47989-6_8 |
| [4] | ALIZADEH J, ALKHZAIMI H A, AREF M R, et.al. Cryptanalysis of SIMON variants with connections[C]//Proceedings of the 10th workshop on RFID Security. Oxford:Springer, 2014:90-107. https://link.springer.com/chapter/10.1007%2F978-3-319-13066-8_6 |
| [5] | BIRYUKOV A, ROY A, VELICHKOV V. Differential analysis of block ciphers SIMON and SPECK[C]//Proceedings of the 21st International Workshop on Fast Software Encryption. London:Springer, 2015:546-570. https://link.springer.com/chapter/10.1007%2F978-3-662-46706-0_28 |
| [6] | ABED F, LIST E, LUCKS S, et al. Differential cryptanalysis of round-reduced simon and speck[C]//Proceedings of the 21st International Workshop on Fast Software Encryption. London:Springer, 2015:525-545. https://link.springer.com/chapter/10.1007%2F978-3-662-46706-0_27 |
| [7] | RADDUM H. Algebraic analysis of the simon blockcipher family[C]//Proceedings of the Fourth International Conference on Cryptology and Information Security in Latin America. Guadalajara:Springer, 2015:157-169. https://link.springer.com/chapter/10.1007%2F978-3-319-22174-8_9 |
| [8] | RABBANINEJAD R, AHMADIAN Z, SALMASIZADEH M, et al. Cube and dynamic cube attacks on SIMON32/64[C]//Proceedings of the 11th International ISC Conference on Information Security and Cryptology. Piscataway:IEEE, 2014:98-103. http://ieeexplore.ieee.org/document/6994030/ |
| [9] | TUPSAMUDRE H, BISHT S, MUKHOPADHYAY D. Differential fault analysis on the families of SIMON and SPECK ciphers[EB/OL]. (2014-05-30)[2016-11-30]. http://eprint.iacr.org/2014/267.pdf. https://www.computer.org/csdl/proceedings/fdtc/2014/6292/00/6292a040-abs.html |
| [10] | YANG L, WANG M Q, QIAO S Y. Side channel cube attack on PRESENT[C]//Proceedings of the International Conference on Cryptology and Network Security. Kanazawa:Springer, 2009:379-391. http://dl.acm.org/citation.cfm?id=1695774 |
| [11] | ABDUL-LATIP S F, REYHANITABAR M R, SUSILO W, et al. On the security of NOEKEON against side channel cube attacks[C]//Proceedings of the 6th Information Security Practice and Experience Conference. Seoul:Springer, 2010:45-55. https://link.springer.com/chapter/10.1007%2F978-3-642-12827-1_4 |
| [12] |
赵新杰, 郭世泽, 王韬, 等. EPCBC密码旁路立方体攻击[J].
成都信息工程学院学报, 2012, 27(6): 525–530.
ZHAO Xin-jie, GUO Shi-ze, WANG Tao, et al. Side-channel cube attacks on EPCBC[J]. Journal of Chengdu University of Information Technology, 2012, 27(6): 525–530. |
| [13] | LI Z Q, ZHANG B, YAO Y, et al. Cube cryptanalysis of LBlock with noisy leakage[C]//Proceedings of the 15th Annual International Conference on Information Security and Cryptology. Seoul:Springer, 2013:141-155. http://dl.acm.org/citation.cfm?id=2482434 |
| [14] |
曾文. Trivium算法的Fault Cube攻击与可滑动对研究[D]. 郑州: 信息工程大学, 2011.
ZENG Wen. The fault cube attack and slid pairs research on trivium[D]. Zhengzhou:Information Engineering University, 2011. http://cdmd.cnki.com.cn/Article/CDMD-90008-1012325162.htm |
| [15] | ABDUL-LATIP S F, REYHANITABAR M R, SUSILO W, et al. Fault analysis of the KATAN family of block ciphers[C]//Proceedings of the 8th Information Security Practice and Experience Conference. Hangzhou:Springer, 2012:319-336. https://link.springer.com/chapter/10.1007%2F978-3-642-29101-2_22?LI=true |
| [16] | DINUR I, SHAMIR A. Cube attacks on tweakable black box polynomials[C]//Proceedings of the 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cologne:Springer, 2009:278-299. https://link.springer.com/chapter/10.1007%2F978-3-642-01001-9_16 |
| [17] | 郭世泽, 王韬, 赵新杰. 密码旁路分析原理与方法[M]. 北京: 科学出版社, 2014: 248-277. |
| [18] | BONEH D, DEMILLO R A, LIPTON R J. On the Importance of checking cryptographic protocols for faults[C]//Proceedings of the 15th Annual EUROCRYPT Conference on the Theory and Applications of Cryptologic Techniques. Konstanz:Springer, 1997:37-51. http://dl.acm.org/citation.cfm?id=1754548 |
| [19] | BIHAM E, SHAMIR A. Differential fault analysis of secret key cryptosystems[C]//Proceedings of the 17th Annual International Cryptology Conference. Santa Barbara, US:Springer, 1997:513-525. https://link.springer.com/chapter/10.1007%2FBFb0052259 |
| [20] | 马克裘依, 腾斯托尔. 密码故障分析与防护[M]. 赵新杰, 郭世泽, 张帆, 等, 译. 北京: 科学出版社, 2015: 240-245. |