留言板

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

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

对MIBS分组密码的差分故障攻击

王永娟 张诗怡 王涛 高杨

王永娟, 张诗怡, 王涛, 高杨. 对MIBS分组密码的差分故障攻击[J]. 电子科技大学学报, 2018, 47(4): 601-605. doi: 10.3969/j.issn.1001-0548.2018.04.020
引用本文: 王永娟, 张诗怡, 王涛, 高杨. 对MIBS分组密码的差分故障攻击[J]. 电子科技大学学报, 2018, 47(4): 601-605. doi: 10.3969/j.issn.1001-0548.2018.04.020
WANG Yong-juan, ZHANG Shi-yi, WANG Tao, GAO Yang. Differential Fault Attack on Block Cipher MIBS[J]. Journal of University of Electronic Science and Technology of China, 2018, 47(4): 601-605. doi: 10.3969/j.issn.1001-0548.2018.04.020
Citation: WANG Yong-juan, ZHANG Shi-yi, WANG Tao, GAO Yang. Differential Fault Attack on Block Cipher MIBS[J]. Journal of University of Electronic Science and Technology of China, 2018, 47(4): 601-605. doi: 10.3969/j.issn.1001-0548.2018.04.020

对MIBS分组密码的差分故障攻击

doi: 10.3969/j.issn.1001-0548.2018.04.020
基金项目: 

国家博士后基金面上资助 2014M552603

国家自然科学基金 61502524

详细信息
    作者简介:

    王永娟(1982-), 女, 博士, 副教授, 主要从事密码学理论和对称密码算法的设计与分析方面的研究

  • 中图分类号: TN918

Differential Fault Attack on Block Cipher MIBS

图(3) / 表(3)
计量
  • 文章访问数:  5172
  • HTML全文浏览量:  1516
  • PDF下载量:  100
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-04-06
  • 修回日期:  2017-09-20
  • 刊出日期:  2018-07-01

对MIBS分组密码的差分故障攻击

doi: 10.3969/j.issn.1001-0548.2018.04.020
    基金项目:

    国家博士后基金面上资助 2014M552603

    国家自然科学基金 61502524

    作者简介:

    王永娟(1982-), 女, 博士, 副教授, 主要从事密码学理论和对称密码算法的设计与分析方面的研究

  • 中图分类号: TN918

摘要: MIBS分组密码是一个基于Feistel结构的轻量级分组密码,适用于RFID、无线传感器等资源受限的硬件环境。差分故障攻击是针对硬件密码算法较为有效的旁路分析手段,通过插入故障和故障传播中涉及的相关密钥之间的关系进行密钥恢复。该文利用S盒的差分不均匀性,通过建立明文差分、密文差分和候选输入值之间的关系,在MIBS密码的最后一轮注入两次故障,可以快速恢复最后一轮密钥信息,进而恢复全部密钥。该攻击思想具有一般性,对基于Feistel结构的轻量级分组密码算法普遍适用。

English Abstract

王永娟, 张诗怡, 王涛, 高杨. 对MIBS分组密码的差分故障攻击[J]. 电子科技大学学报, 2018, 47(4): 601-605. doi: 10.3969/j.issn.1001-0548.2018.04.020
引用本文: 王永娟, 张诗怡, 王涛, 高杨. 对MIBS分组密码的差分故障攻击[J]. 电子科技大学学报, 2018, 47(4): 601-605. doi: 10.3969/j.issn.1001-0548.2018.04.020
WANG Yong-juan, ZHANG Shi-yi, WANG Tao, GAO Yang. Differential Fault Attack on Block Cipher MIBS[J]. Journal of University of Electronic Science and Technology of China, 2018, 47(4): 601-605. doi: 10.3969/j.issn.1001-0548.2018.04.020
Citation: WANG Yong-juan, ZHANG Shi-yi, WANG Tao, GAO Yang. Differential Fault Attack on Block Cipher MIBS[J]. Journal of University of Electronic Science and Technology of China, 2018, 47(4): 601-605. doi: 10.3969/j.issn.1001-0548.2018.04.020
  • 随着物联网技术的蓬勃发展,近年来,适用于资源受限环境的轻量级密码算法受到研究者青睐,MIBS算法[1]是2009年提出的一个基于Feistel结构的轻量级分组密码算法,分组长度64 bit,支持64 bit和80 bit密钥长度,记为MIBS-64和MIBS-80,迭代轮数为32轮。MIBS算法所需硬件成本仅为1 396 GE和1 530 GE,适用于微型计算设备。目前,对MIBS的分析方法主要有差分分析、不可能差分分析、线性分析、零相关分析和积分分析等。文献[2]利用MILP(mixed-integer linear programming)技术研究了MIBS抵抗差分攻击的活跃S-盒下界,结果表明18轮的迭代足以抵抗单密钥的差分分析,39轮对于相关密钥差分分析是安全的;文献[3]提出了一种改进的差分故障分析方法,通过在第2~4轮的密钥中导入半字节故障,可将主密钥搜索空间降至22;文献[4]利用轮密钥间的制约关系与查表操作对13轮的MIBS-80算法进行了较为高效的不可能差分分析,总共需要${{\rm{2}}^{60.1}}$个选择明文,${{\rm{2}}^{69.5}}$次13轮加密与${{\rm{2}}^{77.2}}$ bit的存储量;文献[5]利用${{\rm{2}}^{57.87}}$个明密文对对19轮的MIBS-80实施了时间复杂度为${{\rm{2}}^{74.23}}$的线性分析;而文献[6]则通过构造一个9轮的相关密钥不变偏差线性分析区分器,给出了对13轮的MIBS-80的线性分析算法,该算法可在${{\rm{2}}^{59.62}}$的时间复杂度与${{\rm{2}}^{62.29}}$的数据复杂度的条件下恢复部分轮子密钥信息;文献[7]研究了MIBS-80抵抗零相关线性分析的能力,结合MIBS-80算法轮函数嵌套SP的Feistel结构特点,给出了8轮零相关线性逼近,并对12轮MIBS-80进行零相关线性分析;文献[8]则对13轮的MIBS-80进行了多维零相关分析,需要约${{\rm{2}}^{62.1}}$个明文和${{\rm{2}}^{74.9}}$次加密,此外还对11轮的MIBS-80开展了积分攻击,需要约${{\rm{2}}^{60}}$个明文和${{\rm{2}}^{59.8}}$次加密。

    差分故障攻击是将差分分析和故障攻击相结合提出的一种基于硬件的密码攻击技术。攻击原理是在密码算法加密过程某一轮注入故障,制造明文差分,利用得到的故障密文和故障动作,结合差分方程得到轮密钥可能值,通过多次注入故障可以快速缩小密钥空间,实现密钥破解。差分故障攻击将侧信道攻击和传统分析思想相结合,对基于硬件实现的轻量级密码算法攻击效果显著,差分故障攻击对SMS4[9]、PRESENT[10]、LED[11]、Piccolo[12]、Keeloq[13]、Trivium[14]等轻量级密码算法具有较好的攻击结果。

    故障攻击模型由故障时机、故障位置、故障动作和故障效果四方面构成,通常故障注入轮数越高,攻击效率越高。本文针对MIBS算法,提出改进差分故障攻击,通过建立输入差分、输出差分、可能输入值之间的三次元关系,只需在最后一轮半字节位置注入两次故障,即可确定最后一轮白话密钥,继而进行密钥恢复。攻击效率和成功率较标准差分故障攻击结果均有所提高。

    • MIBS算法是一种Feistel结构的轻量级分组密码算法,采用Feistel结构,MIBS密码的分组长度为64 bit,支持64 bit和80 bit的密钥长度,分别记为MIBS-64和MIBS-80,迭代轮数为32轮。MIBS中所有迭代操作都是基于半字节的,即一个字有4 bit。MIBS的轮函数F是SPN结构的,包括异或子密钥,S盒(4×4)层和一个线性层P(分枝数为5),此处线性层是设计文档中线性混淆和字节置换的复合。一轮MIBS及轮函数如图 1图 2表 1所示。

      图  1  MIBS算法结构图

      图  2  MIBS算法的轮函数

      表 1  MIBS算法轮函数

      a 0 1 2 3 4 5 6 7 8 9 a b c d e f
      S(a) 4 f 3 8 d a c 0 b 5 7 e 2 6 1 9

      图 1可知,MIBS加密轮函数为:${L_i} = {R_{i - 1}} \oplus $ $F(M(S({k_{i - 1}} \oplus {L_{i - 1}})))$,${R_i} = {L_{i - 1}}$,轮函数$F({L_{i - 1}},{K_i})$包括轮密钥加、S盒变换、线性层P(包括线性混淆和字节置换)。其中S是4×4的非线性S盒,混合层P可以描述为如下线性变换:

      $${y'_1} = {y_1} \oplus {y_2} \oplus {y_4} \oplus {y_5} \oplus {y_7} \oplus {y_8}$$
      $${y'_2} = {y_2} \oplus {y_3} \oplus {y_4} \oplus {y_5} \oplus {y_6} \oplus {y_7}$$
      $${y'_3} = {y_1} \oplus {y_2} \oplus {y_3} \oplus {y_5} \oplus {y_6} \oplus {y_8}$$
      $${y'_4} = {y_2} \oplus {y_3} \oplus {y_4} \oplus {y_7} \oplus {y_8}$$
      $${y'_5} = {y_1} \oplus {y_3} \oplus {y_4} \oplus {y_5} \oplus {y_8}$$
      $${y'_6} = {y_1} \oplus {y_2} \oplus {y_4} \oplus {y_5} \oplus {y_6}$$
      $${y'_7} = {y_1} \oplus {y_2} \oplus {y_3} \oplus {y_6} \oplus {y_7}$$
      $${y'_8} = {y_1} \oplus {y_3} \oplus {y_4} \oplus {y_6} \oplus {y_7} \oplus {y_8}$$

      由于密钥长度不同,MIBS-64和MIBS-80的密钥扩展方案略有不同,关于MIBS算法的详细加解密过程参见文献[1],本文不再赘述。

    • MIBS的差分S盒如表 2所示。差分S盒体现S盒的差分分布全局特性,但对具体参数未有直观刻画。

      表 2  MIBS差分S盒

      0x 1x 2x 3x 4x 5x 6x 7x 8x 9x Ax Bx Cx Dx Ex
      0x 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0
      1x 0 0 0 0 2 0 0 2 2 2 0 4 2 0 2
      2x 0 2 0 2 0 0 0 4 0 0 2 2 2 0 0
      3x 0 0 2 0 0 2 2 2 0 0 0 2 4 2 0
      4x 0 0 0 2 0 2 2 2 2 4 0 0 0 0 0
      5x 0 0 2 2 2 0 0 2 0 0 0 0 0 2 4
      6x 0 0 2 0 0 2 0 0 4 0 2 0 2 0 2
      7x 0 2 2 2 4 2 0 0 0 2 0 0 2 0 0
      8x 0 0 0 0 2 0 2 0 0 2 2 0 2 2 0
      9x 0 4 0 0 2 2 0 0 2 0 0 2 0 2 0
      Ax 0 2 0 4 0 0 2 0 2 0 0 0 2 2 2
      Bx 0 0 2 2 2 0 2 0 2 0 4 2 0 0 0
      Cx 0 2 2 0 0 0 4 0 0 2 0 2 0 0 2
      Dx 0 2 4 0 0 0 0 2 2 2 2 0 0 2 0
      Ex 0 2 0 0 2 4 2 2 0 0 2 0 0 0 2

      目前分组密码算法普遍采用查找S盒来提高算法非线性度,但正是S盒的差分特性,导致其面临严重的故障攻击威胁。假设S盒输入值a未知,若在分组密码查表时导入随机故障值f,得到故障差分(密文差分)$f'$,则$a,f,f'$三者之间满足差分关系:

      $$S[a] \oplus S[a \oplus f] = f'$$ (1)

      通过分析可以获得最后一轮S盒的输入值a,主要思路是通过故障分析降低f的搜索空间,代入式(1)恢复aS[a]。输入值a与扩张密钥紧密相关,结合密文可以获取相关扩展密钥,再根据需要多次注入故障或者进行迭代分析直至获取主密钥。

      本文在文献[10]基础上,分析分组密码算法S盒的差分传播特性,发现当S盒($n \times n$)输入差分f一定的情况下,对于每一个可能的输出差分$f'$,其对应的输入a可看成一个集合${\rm{\{ }}{a_1},{a_2}, \cdots ,{a_n}\} $。记为:

      $$\{ f,f'\} = \{ a|S[a] \oplus S[a + f] = f',a \in F_2^n\} $$ (2)

      由式(2)易知,$\{ f,f'\} $有如下性质:

      性质 1  对分组密码算法S盒注入故障值f,对于不同的输出差分${f'_1},{\rm{ }}{f'_2}$,对应输入值可能不交,即${\rm{\{ }}f,{f'_1}{\rm{\} }} \cap {\rm{\{ }}f,{f'_2}{\rm{\} }} = \mathit{\Phi} $。

      性质 2  在输入a一定的情况下,对于两个特定不同的输入差分${f_1},{f_2}$,一定存在${f'_1},{\rm{ }}{f'_2}$,使得$a \in \{ {f_1},{f'_1}\} \cap \{ {f_2},{f'_2}\} $。

      证明:令S是一个($n \times n$)的S盒,对S盒注入故障${f_1}$,对应的故障差分空间为${F'_1} = \{ f'|\exists a \in F_2^n$,${\rm{sat}}.\;S(a) + S(a + {f_1}) = f'\} $。由S盒差分不均匀性可知$F'$是输入空间$F_2^n$的一个真子空间,记${F'_1} = \{ {f'_1},{f'_2}, \cdots ,{f'_k}\} ,\;k < {2^n}$,则由定义和性质1可知${\rm{\{ }}{f_1},{f'_1}\} ,$${\rm{\{ }}{f_1},{f'_2}\} ,$…, ${\rm{\{ }}{f_1},{f'_k}\} $是$F_2^n$的一个分割,满足$\bigcup\limits_{i = 1}^k {\{ {f_1},{{f'}_i}} \} = F_2^n$且$\{ {f_1},{f'_i}\} \cap \{ {f_1},{f'_j}\} = \varphi $,$i \ne j$。

      故对任意的输入值a,存在唯一一个集合$\{ {f_1},{f_i}'\} $,使得$a \in \{ {f_1},{f_i}'\} $,不失一般性,记$a \in {\rm{\{ }}{f_1},{f_2}'{\rm{\} }}$;同理,对于故障值${f_2}$,存在唯一的集合${\rm{\{ }}{f_2},{f_2}'{\rm{\} }}$,满足$a \in {\rm{\{ }}{f_2},{f_2}'{\rm{\} }}$。从而有$a \in {\rm{\{ }}{f_1},{f_2}'{\rm{\} }} \cap $ ${\rm{\{ }}{f_2},{f_2}'{\rm{\} }}$。#

      根据性质1和性质2,本文通过对MIBS算法建立$a,f,f'$的对应关系如表 3所示,可以快速直观缩小输入值取值空间,进而快速确定对应扩展密钥。对于不同故障值(输入差分),对应的输出差分和可能输入值均不相同,根据表 3可以得到二元关系集合,根据式(2)和表 3对应关系得$\# (1,4) = \{ c,d\} $,$\# (a,6) = \{ 7,d\} $。如果分别注入故障值1和a,则通过查表,对可能输入值取交集即可快速确定唯一可能输入值为d。(${\rm{\# (}}1,4{\rm{)}} \cap {\rm{\# (}}a,6{\rm{)}} = \{ d\} $)。同时对于任意两个输入差分,其对应的输出差分不完全相同,这样通过观察输出差分可以很大概率确定输入差分的值。攻击流程如图 3所示。

      表 3  输入差分、输出差分、可能输入值对应关系

      输入差分(0X) 在输入差分一定情况下输出差分与输入对应关系(0X)
      1 输出差分 4 7 8 9 b c e
      输入值 c, d 4, 5 e, f a, b 0, 1, 2, 3 6, 7 8, 9
      2 输出差分 1 3 7 a b c f
      输入值 4, 6 c, e 0, 1, 2, 3 5, 7 9, b 8, a d, f
      3 输出差分 2 5 6 7 b c d
      输入值 9, a 8, b 5, 6 d, e c, f 0, 1, 2, 3 4, 7
      4 输出差分 3 5 6 7 8 9 f
      输入值 9, d 1, 5 a, e b, f 3, 7 0, 4, 8, c 2, 6
      5 输出差分 2 3 4 7 d e f
      输入值 1, 4 2, 7 3, 6 9, c 8, d 0, 5, a, f b, e
      6 输出差分 2 5 8 a c e f
      输入值 3, 5 a, c 0, 6, b, d 8, e 9, f 2, 4 1, 7
      7 输出差分 1 2 3 4 5 9 c
      输入值 a, d 8, f 1, 6 0, 7, 9, e 3, 4 2, 5 b, c
      8 输出差分 4 6 9 a c d f
      输入值 2, a 3, b 7, f 1, 9 5, d 6, e 0, 4, 8, c
      9 输出差分 1 4 5 8 b d f
      输入值 0, 7, 9, e 1, 8 6, f 5, c 4, d 2, b 3, a
      a 输出差分 1 3 6 8 c d e
      输入值 1, b 0, 5, a, f 7, d 2, 8 4, e 3, 9 6, c
      b 输出差分 2 3 4 6 8 a b
      输入值 7, c 3, 8 4, f 2, 9 1, a 0, 6, b, d 5, e
      c 输出差分 1 2 6 9 b e f
      输入值 3, f 2, e 0, 4, 8, c 1, d 7, b 2, b 5, 9
      d 输出差分 1 2 7 8 9 a b
      输入值 5, 8 0, 6, b, d 7, a 4, 9 3, e 2, f 1, c
      e 输出差分 1 4 5 6 7 a e
      输入值 2, c 5, b 0, 7, 9, e 1, f 6, 8 4, a 3, d
      f 输出差分 3 5 9 a b d e
      输入值 4, b 2, d 6, 9 3, c 7, 8 0, 5, a, f 1, e

      图  3  改进的差分故障攻击流程

      由MIBS算法的差分S盒可知,在理想情况下,只需在算法最后一轮注入两次不同故障,即可快速获得S盒输入$a$,从而高效准确地恢复出轮密钥,最后通过密钥扩展算法恢复主密钥。将此方法扩展到不同SP结构分组密码算法和部分Feistel结构的轻量级分组密码算法,均取得了良好的攻击效果。

    • 本节选取明文:01 23 45 67 89 ab cd ef,密钥:01 23 45 67 89 ab cd ef。

      1) 首先进行一次正确加密,得密文:a7 00 60 37 bf 97 81 07。

      2) 在最后一轮${{\rm{L}}^{31}}$引入差分故障11 11 11 11,得到故障密文:4e 7d 29 e9 ae 86 90 16。将故障密文同正确密文异或得到:e9 7d 49 de 11 11 11 11。

      3) 将密文差分e9 7d 49 de通过逆P置换、逆列混淆后得到S盒的输出差分:e4 9e 49 79。

      4) 改变故障值为aa aa aa aa,得到另一组故障密文:a9 e8 03 b7 15 3d 2b ad。相应的可以得到差分密文:0e e8 63 80 aa aa aa aa。将左半部分密文差分0e e8 63 80通过逆P置换、逆列混淆后得到S盒的另一组输出差分:d6 3d 63 33。

      5) 结合表确定出S盒未加故障时的输入:每一个未知的输入候选值均只有一个交集,这样就唯一确定出S盒的输入为:9d a9 da 5a。

      6) 将S盒输入:9d a9 da 5a与密文右半部分:bf 97 81 07异或得到最后一轮轮密钥${k^{31}}$:22 3e 5b 5d。从而得到31轮加密后的输出:bf 97 81 07 78 29 07 aa。

      利用31轮加密后输出值,在第30轮注入两次故障,可以得到K30,具体流程如下:

      1) 在${{\rm{L}}^{30}}$引入差分故障11 11 11 11,得到故障密文:c7 89 c4 9c 10 2d 3f d6。通过${k^{31}}$得到31轮加密后的密文:10 2d 3f d6 69 38 16 bb。将故障密文同正确密文异或得到:af ba be d1 11 11 11 11。将密文差分af ba be d1通过逆P置换、逆列混淆后得到S盒的输出差分:77 ec 9b 87。

      2) 在${{\rm{L}}^{30}}$引入差分故障aa aa aa aa,得到故障密文:f0 3c 68 d4 c1 2a 77 ab。通过${k^{31}}$得到31轮加密后的密文:c1 2a 77 ab d2 83 ad 00。将故障密文同正确密文异或得到:7e bd f6 ac aa aa aa aa。将密文差分7e bd f6 ac通过逆P置换、逆列混淆后得到S盒的输出差分:33 86 11 33。

      3) 结合表确定出S盒未加故障时的输入:每一个未知的输入候选值均只有一个交集,这样就唯一确定出S盒的输入为:55 87 b1 f5。

      4) 将S盒输入:55 87 b1 f5与31轮后密文右半部分:78 29 07 aa异或得到${k^{30}}$:2d ae b6 5f。从而得到30轮加密后的密文:78 29 07 aa 66 95 d0 da。

      综上可得${k^{30}}$:2d ae b6 5f,${k^{31}}$:22 3e 5b 5d。再由密钥扩展方案可知,所得${k^{30}}$为K30的高位32 bit,经过一次密钥扩展算法,得到最后一轮轮密钥K31为:

      $$\begin{gathered} {K^{31}} = S[K_{49}^{30},K_{50}^{30},K_{51}^{30},K_{52}^{30}]||[K_{53}^{30}, \cdots ,K_{32}^{30}]|| \\ [K_{33}^{30},K_{34}^{30},K_{35}^{30},K_{36}^{30},K_{37}^{30}] \oplus {(31)_2}||[K_{38}^{30}, \cdots ,K_{48}^{30}] \\ \end{gathered} $$

      实验中得到k31K30的高位32 bit,去掉重复比特,经过两次密钥扩展,可得到K30的15+32= 47 bit,剩余17 bit可以通过遍历求取,数据复杂度为217

    • 本文分析轻量级分组密码算法S盒差分传播特性,通过建立<输入差分、输出差分、可能输入值>的对应关系表,利用不同故障条件下故障差分对应的输入值集合交集唯一的特性,针对基于Feistel结构的MIBS算法,分别在第30轮和31轮注入两次故障,可以恢复47 bit轮密钥,进而通过穷举恢复其余密钥比特,时间复杂度为217

参考文献 (14)

目录

    /

    返回文章
    返回