留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

PRESENT密码的差分故障攻击

陈伟建 赵思宇 邹瑞杰 张晓宁

陈伟建, 赵思宇, 邹瑞杰, 张晓宁. PRESENT密码的差分故障攻击[J]. 电子科技大学学报, 2019, 48(6): 865-869. doi: 10.3969/j.issn.1001-0548.2019.06.010
引用本文: 陈伟建, 赵思宇, 邹瑞杰, 张晓宁. PRESENT密码的差分故障攻击[J]. 电子科技大学学报, 2019, 48(6): 865-869. doi: 10.3969/j.issn.1001-0548.2019.06.010
CHEN Wei-jian, ZHAO Si-yu, ZOU Rui-jie, ZHANG Xiao-ning. The Differential Fault Attack of PRESENT Cipher[J]. Journal of University of Electronic Science and Technology of China, 2019, 48(6): 865-869. doi: 10.3969/j.issn.1001-0548.2019.06.010
Citation: CHEN Wei-jian, ZHAO Si-yu, ZOU Rui-jie, ZHANG Xiao-ning. The Differential Fault Attack of PRESENT Cipher[J]. Journal of University of Electronic Science and Technology of China, 2019, 48(6): 865-869. doi: 10.3969/j.issn.1001-0548.2019.06.010

PRESENT密码的差分故障攻击

doi: 10.3969/j.issn.1001-0548.2019.06.010
详细信息
    作者简介:

    陈伟建(1956-), 男, 教授, 主要从事无线与移动通信、密码理论与技术方面的研究

    通讯作者: 赵思宇, E-mail:568142925@qq.com
  • 中图分类号: TP309

The Differential Fault Attack of PRESENT Cipher

图(2) / 表(1)
计量
  • 文章访问数:  3997
  • HTML全文浏览量:  1251
  • PDF下载量:  56
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-04-24
  • 修回日期:  2019-06-19
  • 刊出日期:  2019-11-30

PRESENT密码的差分故障攻击

doi: 10.3969/j.issn.1001-0548.2019.06.010
    作者简介:

    陈伟建(1956-), 男, 教授, 主要从事无线与移动通信、密码理论与技术方面的研究

    通讯作者: 赵思宇, E-mail:568142925@qq.com
  • 中图分类号: TP309

摘要: 针对PRESENT密码算法的差分故障攻击,分析PRESENT算法差分故障传播特点的方式,优化导入故障位置,利用组合穷举搜索,建立不同的攻击模型来快速获取原始密钥。结果表明,影响PRESENT算法的差分故障攻击结果有两个因素:攻击轮数和故障密文数目。在倒数第二轮攻击平均需要30个故障密文就可以成功恢复出该轮64 bit轮密钥,在低轮数针对该密码算法进行差分故障攻击,仅仅需要9个故障密文就能恢复全部密钥。同时这种攻击方式在单故障密文的密钥搜索复杂度和攻击复杂度分别为226和231

English Abstract

陈伟建, 赵思宇, 邹瑞杰, 张晓宁. PRESENT密码的差分故障攻击[J]. 电子科技大学学报, 2019, 48(6): 865-869. doi: 10.3969/j.issn.1001-0548.2019.06.010
引用本文: 陈伟建, 赵思宇, 邹瑞杰, 张晓宁. PRESENT密码的差分故障攻击[J]. 电子科技大学学报, 2019, 48(6): 865-869. doi: 10.3969/j.issn.1001-0548.2019.06.010
CHEN Wei-jian, ZHAO Si-yu, ZOU Rui-jie, ZHANG Xiao-ning. The Differential Fault Attack of PRESENT Cipher[J]. Journal of University of Electronic Science and Technology of China, 2019, 48(6): 865-869. doi: 10.3969/j.issn.1001-0548.2019.06.010
Citation: CHEN Wei-jian, ZHAO Si-yu, ZOU Rui-jie, ZHANG Xiao-ning. The Differential Fault Attack of PRESENT Cipher[J]. Journal of University of Electronic Science and Technology of China, 2019, 48(6): 865-869. doi: 10.3969/j.issn.1001-0548.2019.06.010
  • 差分故障攻击是由文献[1]结合数学研究方法和物理方法提出的一种新的密码分析方式。该方法被应用到多经典分组密码上,如AES[2]、SMS4[3]、FOX[4]等。同时,随着物联网的发展,轻量级分组密码在智能卡、RFID标签和无线传感器网络等资源受限的环境下有着很好的表现,许多密码学学者也对这些密码进行了差分故障攻击分析,如HIGHT[5]、PRINCE[6]、Piccolo[7]等等。

    PRESENT密码算法是由文献[8]提出的一种超轻量级密码算法。其分组长度为64 bit,密钥大小分别为80 bit和128 bit,密码结构设计为SPN。随后,为了确保PRESENT密码算法的安全强度,许多学者采用不同的攻击方式对该算法的安全性进行了一系列研究。文献[8]针对16轮的PRESENT算法进行了积分攻击结果分析,攻击复杂度为220。文献[9]对18轮的PRESENT算法进行了多重差分链攻击,最后计算攻击复杂度为281。文献[10]采用差分代数对PRESENT算法进行攻击,攻击复杂度为264.58。文献[11]利用多模型差分故障分析方法,分析结果表明在两种不同长度随机错误的条件下,最少需要17个故障密文才能恢复该轮64 bit原始密钥。文献[12]对21轮的PRESENT算法进行Biclique攻击分析,攻击复杂度为278.9。文献[13]采用差分能量对PRESENT算法进行攻击研究,根据分析3 000个波形就能还原原始密钥。

    本文主要对密钥为80 bit的PRESENT算法进行差分故障攻击研究,根据该算法在随机引入单字节故障后,故障传播只会在固定位置出现的特性,利用优化后的差分故障攻击方法对其整个加密过程进行攻击,最后得到实验结果,经过5轮以上加密,平均仅需要引入9个单字节故障密文就能恢复该轮的64 bit轮密钥。

    • PRESENT算法整个加密过程需要经过31轮加密后,再经过与轮密钥异或的白化操作,输出最后的密文。每轮具体的加密过程如下:

      1) 轮密钥异或运算层:每轮加密输出64 bit中间状态与64位的轮密钥进行异或运算。

      2) S盒代换层:将异或后64 bit输出在经过16个相同的4-bit输入和4-bit输出S盒。

      3) P置换层:通过查询置换表P(i),对S盒的64 bit输出进行重新排列。

      在经过31轮加密后,与第32轮轮密钥再进行一次白化异或运算,输出最后的64 bit密文。

      PRESENT密码的每轮轮密钥生成算法主要经过循环移位、S盒代换、与当前加密轮数数目异或运算后得到64bit的密钥。本文主要研究密钥为80 bit ($K = {k_{79}}{k_{78}} \cdots {k_1}{k_0}$)的PRESENT算法,具体密钥生成算法如下:

      $${k_{79}}{k_{78}} \cdots {k_1}{k_0} = {k_{18}}{k_{17}} \cdots {k_{20}}{k_{19}}$$
      $$\left\{ \begin{align} & 0d=0 \\ & \frac{2n}{d} 1\le d\le n \\ \end{align} \right.$$
      $${k_{19}}{k_{18}}{k_{17}}{k_{16}}{k_{15}} = [{k_{19}}{k_{18}}{k_{17}}{k_{16}}{k_{15}}] \oplus {\rm{roundconut}}$$

      式中,roundconut表示当前加密轮数,用与PRESENT加密过程相同的64 bit S盒代替运算所用的S盒。

    • 为了能更好地提高针对PRESENT算法的差分故障攻击效率,首先针对PRESENT算法的故障传播特性进行分析。假设在PRESENT算法加密过程的第r轮随机位引入一个单字节错误,输入为(${X_0}$, ${X_1}$, ${X_2}$, ${\gamma _3}$, ${X_4}$, ${X_5}$, ${X_6}{\kern 1pt} $, ${X_7}$),经过S盒代换层和P置换层后,它的第r+1轮输入为(${\gamma _0}$, ${X_1}$, ${\gamma _2}$, ${X_3}$, ${\gamma _4}$, ${X_5}$, ${\gamma _6}{\kern 1pt} $, ${X_7}$),经过分析可以发现PRESENT故障传播有如下特性,如图 1所示。

      图  1  PRESENT单字节差分故障传播图

      进一步在不同的位置插入故障,经过分析可以发现,在加密过程中任意r轮第0字节、第1字节、第2字节、第3字节引入故障,结果故障只会传播在最后密文${C_0},{C_2},{C_4},{C_6}$位置处,其他位置对应的密文不受影响;采用相同的故障引入方式,在任意r轮的第4字节、第5字节、第6字节、第7字节引入单字节故障,故障只会在最后密文的${C_1},{C_3},{C_5},{C_7}$位置发处,其他位置对应正确的单字节密文。由此可以在该密码算法的奇数或者偶数位置随机引入故障,最后错误密文会出现在相应的位置上,通过差分公式得出错误密文与原始密文,相应这些密码字节位置上的密文不一直为零。通过这种故障传播特性可以进一步对PRESENT算法进行差分故障攻击。

    • 针对PRESENT算法采用单字节攻击模型,在随机位置引入随机故障。为了能更好地对PRESENT算法进行分析,在攻击之前提出两点基本假设:

      1) 攻击者可以在加密过程中的任意轮对指定的中间状态位置加入故障,但具体的故障值和引入故障位置未知,能够正确记录原始密文和错误密文。

      2) 采用相同的明文和轮密钥加密过程中,攻击者能够多次对该密码算法加密相同的轮数和在相同位置引入故障,并记录最后错误密文结果。

    • 任意选择一组明文和密钥,通过加密算法得到正确密文。然后在加密过程的第30轮处导入故障,结合差分故障攻击特点,获取加密过程中密文的部分特性。进一步通过加密算法的逆过程,推导出该轮64 bit轮密钥。在同样的密文和密钥的条件下,多次重复上述过程,直到恢复的轮密钥为唯一值。在第29轮使用同样步骤获取第二个轮密钥后,通过密钥生成算法,就能推导出PRESENT算法的整个原始密钥。

    • 具体的攻击算法分为以下9个步骤:

      1) 随机生成PRESENT算法的一个明文P和一个轮密钥${K_i}$,经过31轮加密后得到正确密文C

      2) 用第1)步明文P和原始密钥${K_i}$再经过第30轮加密后,在PRESENT使用的S盒中随机诱导一个单字节的故障,经过最后一轮加密后得到错误密文$C_{31}^*$,再与第31轮正确密文进行差分运算得到差分错误密文$\Delta C_{31}^*$:

      $$\Delta C_{31}^{\rm{*}} = {C_{31}} \oplus C_{31}^*$$

      3) 第31轮经过P置换层后$\Delta C_{31}^*$的值用$\Delta {Y_{31}}$表示,经过S盒代换后的值用$\Delta {X_{31}}$表示,分别为:

      $$\Delta {Y_{31}} = \Delta C_{31}^{\rm{*}}$$
      $$\Delta {X_{31}} = {\rm{P}}{{\rm{L}}^{ - 1}}(\Delta {Y_{31}})$$

      式中,${\rm{P}}{{\rm{L}}^{ - 1}}$表示经过P置换层的逆运算。

      因此第30轮最后的输出差分密文为:

      $$\Delta C_{30}^{\rm{*}} = {\rm{S}}{{\rm{L}}^{ - 1}}(\Delta {X_{31}})$$

      式中,${\rm{S}}{{\rm{L}}^{ - 1}}$表示经过S盒的逆运算。

      经过差分运算后,非零位只会出现在4个位置上,每个位置可能值为256,所以$\Delta C_{30}^*$的所有值有1 020个,穷举出这1 020个值,并且把它们存入集合M中。由前面的分析得知,在$\Delta C_{30}^*$中所有非零字节只会出现4个位置($\Delta {X_0}$, 0, $\Delta {X_2}$, 0, $\Delta {X_4}$, 0, $\Delta {X_6}$, 0)或(0, $\Delta {X_1}$, 0, $\Delta {X_3}$, 0, $\Delta {X_5}$, 0, $\Delta {X_7}$),所以其他零位对差分故障攻击没有意义。假设对密文的0、2、4、6位置进行攻击,选择差分输出结果的前两个非零字节密文,根据下面公式计算得出:

      $$ {S^{ - 1}}({x_{0,30}}) \oplus {S^{ - 1}}({x_{0,30}} \oplus \Delta {x_{0,30}}) = \Delta {c_{0,30}}$$
      $$ {S^{ - 1}}({x_{2,30}}) \oplus {S^{ - 1}}({x_{2,30}} \oplus \Delta {x_{2,30}}) = \Delta {c_{2,30}} $$

      穷举$(\Delta {x_{0,30}},\Delta {x_{2,30}})$所有的216可能值,依次计算出$(\Delta {c_{0,30}},\Delta {c_{2,30}})$的所有值。

      4) 把第3)步得出的$(\Delta {c_{0,30}},\Delta {c_{2,30}})$和穷举集合M中第0、2位字节值进行比较,如匹配结果相同,就将对应的$(\Delta {c_{0,30}},\Delta {c_{2,30}})$存入一个新的集合${T_1}$中。

      5) 对集合${T_1}$中的每一条记录进行单字节扩展。首先从${T_1}$中取出一个元素${\alpha _t}$,穷举${x_{4,30}}$所有的28可能值,计算:

      $$ {S^{ - 1}}({\alpha _{0,30}}) \oplus {S^{ - 1}}({\alpha _{0,30}} \oplus \Delta {x_{0,30}}) = \Delta {c_{0,30}} $$
      $$ {S^{ - 1}}({\alpha _{2,30}}) \oplus {S^{ - 1}}({\alpha _{2,30}} \oplus \Delta {x_{2,30}}) = \Delta {c_{2,30}} $$
      $${S^{ - 1}}({x_{4,30}}) \oplus {S^{ - 1}}({x_{4,30}} \oplus \Delta {x_{4,30}}) = \Delta {c_{4,30}}$$

      然后把$(\Delta {c_{0,30}},\Delta {c_{2,30}},\Delta {c_{4,30}})$与集合M中的第0、2、4位字节值进行比较。如果匹配结果相同,将$(\Delta {c_{0,30}},\Delta {c_{2,30}},\Delta {c_{4,30}})$存入新的集合${T_2}$中。

      6) 重复步骤5),扩展出中间状态的最后一个字节${x_{6,30}}$,将结果存入集合${T_3}$中,此时${T_3}$中可能有多个4字节的元素。

      7) 多次重复步骤1)~6),在加密过程中随机引入故障密文,直至${T_3}$中只剩下唯一的4字节元素,此元素就代表正确加密中间状态。在加密过程中,对密文的后4位进行攻击,按照步骤1)~6),最后恢复出该算法的后4位中间状态。

      8) 此后再根据PRESENT的P置换层和轮密钥异或加密过程,推导出最后异或时使用的密钥${K_{32}}$:

      $${Y_{31}}{\rm{ = PL}}({X_{31}})$$
      $${K_{32}} = {C_{31}} \oplus {Y_{31}} = {C_{31}} \oplus {\rm{PL}}({X_{31}})$$

      9) 同样在第29轮对PRESENT密码算法进行差分故障攻击,根据已经恢复的${K_{32}}$计算出第30轮的密文${C_{30}}$,重复步骤1)~8),恢复出密钥${K_{31}}$。

    • 本文根据故障传播特性建立的攻击方式,相比于传统采用的PRESENT密钥直接穷尽搜索有一定的优化,如直接穷尽搜索密钥,需要264复杂度。本文采用依次扩展的方法,根据每一轮中间状态匹配的数量,来降低下一轮穷尽搜索数,复杂度为:

      $${n_1}{2^{16}}{\rm{ + }}{n_2}{2^8}{\rm{ + }}{n_3}{2^8}$$ (1)
      $$ {n_1} \leqslant {n_2} \leqslant {2^8}$$
      $$ {n_2} \leqslant {n_3} \leqslant {2^8} $$

      式中,${n_1}$代表穷举前两个字节与可能正确值相匹配数目;${n_2}$、${n_3}$代表秘钥后面两个字节匹配数目。在提供一个故障密文的情况下,通过大量实验获取${n_1}$、${n_2}$、${n_3}$的平均值,可以计算出搜索该轮32 bit密钥的平均计算复杂度为225,搜索该轮64 bit原始密钥的计算复杂度为226

      根据PRESENT算法特点,攻击者需要在不同的位置多次引入不同的错误,再根据匹配表把筛选出的可能正确的中间状态取交集。根据文献[14]可知,恢复出一个轮密钥需要的最少故障数目为:

      $$ \left\{ \begin{array}{l} 0& d = 0\\ \left\lceil {\frac{{2n}}{d}} \right\rceil \; & 1 \le d \le n \end{array} \right. $$ (2)

      式中,n表示经过S盒代换层运算后输出比特数目;d表示经过线性层P置换后,扩展最后故障输出的比特数目。本文对PRESENT算法进行单字节攻击,恢复出原始轮密钥需的攻击复杂度为:

      $$ \left\{ \begin{array}{l} 0&d = 0\\ ({n_1}{2^{16}}{\rm{ + }}{n_2}{2^8}{\rm{ + }} \cdots {\rm{ + }}{n_b}{2^8})\left\lceil {\frac{{ng}}{{{\rm{si}} \times d}}} \right\rceil & 1 \le d \le n \end{array} \right. $$ (3)

      式中,${n_b}$表示穷举搜索中间状态与正确状态匹配数目;g表示还原出密钥${K_0}$所需要的理论最少轮密钥数目;si表示S盒输入的比特数目。

      在加密运算过程中倒数第2轮的非线性层S盒或者线性P置换层引入任意一个单字节故障,最后产生的差分密文不一直零的只有32 bit,根据式(2)理论上最少需要4个单字节故障密文才能恢复出一个PRESENT算法的轮密钥。恢复出全部64 bit原始密钥至少需要8个单字节故障密文,并且经过连续两轮的随机攻击。根据式(3)可以计算理论攻击复杂度,其中${n_1}{n_2} \cdots {n_b})$根据多次实验得出平均值。那么在一个故障密文的情况下,恢复该轮PRESENT的32 bit密钥平均攻击复杂度为230,恢复该轮64 bit密钥的平均攻击复杂度为231。相比于多重差分链攻击、差分代数攻击、Biclique等攻击方式,本文采用的差分故障攻击在很大程度上降低了攻击时所需的复杂度。

    • 使用Visual Studio 2015工具在普通PC(CPU为Intel(R)Core(TM)i7 4790,3.60 GHz,内存8 GB)上用C++语言实现了PRESENT密码算法的加解密过程和差分故障攻击过程。实验加密明文取值为123456ab,初始密钥值取值为a0b1c2d3e4f5,建立随机攻击位置,随机故障值攻击模型一共完成100组实验。表 1为多次实验中的一组数据,给出了能够恢复出唯一轮密钥需要的故障数目和攻击时间。

      表 1  第30轮和第29轮攻击故障样本数据

      实验
      序号
      第30轮需要故障密文数目和
      攻击时间/ms
      第29轮需要故障密文数目和
      攻击时间/ms
      1 23(19 832) 25(23 874)
      2 24(20 340) 21(19 925)
      3 24(20 445) 26(23 722)
      4 23(19 534) 25(22 846)
      5 25(21 092) 25(22 641)
      6 22(18 542) 21(19 381)
      7 21(18 262) 22(20 697)
      8 21(17 719) 23(21 131)
      9 24(20 090) 24(21 543)
      10 22(18 477) 23(20 956)

      在PRESENT算法加密过程中的第30轮和29轮导入随机故障,最后恢复该轮密钥大约需要24个故障密文。继续降低估计轮数,所需要的故障密文也逐渐下降,图 2给出了在不同轮数攻击,需要的故障数目与攻击成功率之间的关系。

      图  2  PRESENT不同轮数与故障数目攻击结果

      通过图 2可以得出,差分故障攻击轮数和导入故障数目对PRESENT最后的攻击结果会产生显著影响。在低轮数导入故障只需要12个故障密文就能100%恢复该轮密钥,最好情况下只需要6个故障密文。经过大量重复试验统计得出在低轮数进行差分故障攻击平均需要9个故障密文,这与式(2)所描述的理论故障数目基本相符。

    • 利用优化后差分故障攻击方法,对PRESENT整个加密轮数进行攻击。通过C++语言得到实验结果,最后发现影响PRESENT攻击结果的因素有攻击轮数和故障密文数目。分析表明随着攻击轮数的降低,我们需要的故障密文数目随之下降。在低轮数进行随机位置随机故障值的差分故障攻击,平均只需要9个故障密文就能恢复该轮64 bit原始密钥,该方法的单故障密文密钥搜索复杂度和攻击复杂度也同时降低为226和231

参考文献 (14)

目录

    /

    返回文章
    返回