高级搜索

密码算法旁路立方攻击改进与应用

王永娟 王涛 袁庆军 高杨 王相宾

引用本文: 王永娟, 王涛, 袁庆军, 高杨, 王相宾. 密码算法旁路立方攻击改进与应用[J]. 电子与信息学报, doi: 10.11999/JEIT181075 shu
Citation:  Yongjuan WANG, Tao WANG, Qingjun YUAN, Yang GAO, Xiangbin WANG. Side Channel Cube Attack Improvement and Application on Cryptographic Algorithm[J]. Journal of Electronics and Information Technology, doi: 10.11999/JEIT181075 shu

密码算法旁路立方攻击改进与应用

    作者简介: 王永娟: 女,1972年生,副教授,主要研究方向为网络空间安全、密码算法分析;
    王涛: 男,1995年生,硕士生,研究方向为侧信道攻击;
    袁庆军: 男,1993年生,助教,研究方向为侧信道攻击;
    高杨: 男,1994年生,硕士生,研究方向为故障攻击;
    王相宾: 男,1996年生,硕士生,研究方向为侧信道攻击
    通讯作者: 王涛,1072637697@qq.com
  • 基金项目: 国家自然科学基金(61872381, 61602512)

摘要: 立方攻击的预处理阶段复杂度随输出比特代数次数的增长呈指数级增长,寻找有效立方集合的难度也随之增加。该文对立方攻击中预处理阶段的算法做了改进,在立方集合搜索时,由随机搜索变为带目标的搜索,设计了一个新的目标搜索优化算法,优化了预处理阶段的计算复杂度,进而使离线阶段时间复杂度显著降低。将改进的立方攻击结合旁路方法应用在MIBS分组密码算法上,从旁路攻击的角度分析MIBS的算法特点,在第3轮选择了泄露位置,建立关于初始密钥和输出比特的超定的线性方程组,可以直接恢复33bit密钥,利用二次检测恢复6bit密钥。所需选择明文量221.64,时间复杂度225。该结果较现有结果有较大改进,恢复的密钥数增多,在线阶段的时间复杂度降低。

English

    1. [1]

      DINUR I and 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, Germany, 2009: 278–299. doi: 10.1007/978-3-642-01001-9_16.

    2. [2]

      LAI Xuejia. Higher order derivatives and differential cryptanalysis[M]. BLAHUT R E, COSTELLO JR D J, MAURER U, et al. Communications and Cryptography. Boston: Springer, 1994: 227–233. doi: 10.1007/978-1-4615-2694-0_23.

    3. [3]

      VIELHABER M. Breaking ONE. FIVIUM by AIDA an algebraic IV differential attack[R]. 2007. (请核对文献类型并且补充报告编号)

    4. [4]

      AUMASSON J P, DINUR I, MEIER W, et al. Cube testers and key recovery attacks on reduced-round MD6 and trivium[C]. Proceedings of the 16th International Workshop on Fast Software Encryption, Belgium, 2009: 1–22. doi: 10.1007/978-3-642-03317-9_1.

    5. [5]

      MROCZKOWSKI P and SZMIDT J. The cube attack on stream cipher trivium and quadraticity tests[J]. Fundamenta Informaticae, 2012, 114(3/4): 309–318. doi: 10.3233/FI-2012-631

    6. [6]

      TODO Y, ISOBE T, HAO Yonglin, et al. Cube attacks on non-blackbox polynomials based on division property[J]. IEEE Transactions on Computers, 2018, 67(12): 1720–1736. doi: 10.1109/TC.2018.2835480

    7. [7]

      SZMIDT J. The cube attack on Courtois toy cipher[C]. Proceedings of the 1st International Conference on Number-Theoretic Methods in Cryptology, Warsaw, 2017: 241–253. doi: 10.1007/978-3-319-76620-1_14.

    8. [8]

      DINUR I and SHAMIR A. Side channel cube attacks on block ciphers[J]. IACR Cryptology Eprint Archive, 2009, 2019: 127.

    9. [9]

      DINUR I and SHAMIR A. Breaking Grain-128 with dynamic cube attacks[C]. Proceedings of the 18th International Workshop on Fast Software Encryption, Lyngby, 2011: 167–187. doi: 10.1007/978-3-642-21702-9_10.

    10. [10]

      马云飞, 王韬, 陈浩, 等. SIMON系列轻量级分组密码故障立方攻击[J]. 浙江大学学报: 工学版, 2017, 51(9): 1770–1779. doi: 10.3785/j.issn.1008-973X.2017.09.011
      MA Yunfei, WANG Tao, CHEN Hao, et al. Fault-cube attack on SIMON family of lightweight block ciphers[J]. Journal of Zhejiang University:Engineering Science, 2017, 51(9): 1770–1779. doi: 10.3785/j.issn.1008-973X.2017.09.011

    11. [11]

      HUANG Senyang, WANG Xiaoyun, XU Guangwu, et al. Conditional cube attack on reduced-round Keccak sponge function[C]. Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, 2017: 259–288. doi: 10.1007/978-3-319-56614-6_9.

    12. [12]

      LIU Meicheng, YANG Jingchun, WANG Wenhao, et al. Correlation cube attacks: From weak-key distinguisher to key recovery[C]. Proceedings of the 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, 2018: 715–744. doi: 10.1007/978-3-319-78375-8_23.

    13. [13]

      YANG Lin, WANG Meiqin, and QIAO Siyuan. Side channel cube attack on PRESENT[C]. Proceedings of the 8th International Conference on Cryptology and Network Security, Kanazawa, 2009: 379–391. doi: 10.1007/978-3-642-10433-6_25.

    14. [14]

      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 International Conference on Information Security Practice and Experience, Seoul, 2010: 45–55. doi: 10.1007/978-3-642-12827-1_4.

    15. [15]

      BUJA A G, ABDUL-LATIP S F, and AHMAD R. A security analysis of IoT encryption: Side-channel cube attack on Simeck32/64[J]. International Journal of Computer Networks & Communications, 2018, 10(4): 79–90. doi: 10.5121/ijcnc.2018.10406

    16. [16]

      刘会英, 王韬, 郭世泽, 等. MIBS密码旁路立方体攻击[J]. 计算机仿真, 2013, 30(5): 302–305. doi: 10.3969/j.issn.1006-9348.2013.05.069
      LIU Huiying, WANG Tao, GUO Shize, et al. Side channel cube attacks on MIBS[J]. Computer Simulation, 2013, 30(5): 302–305. doi: 10.3969/j.issn.1006-9348.2013.05.069

    17. [17]

      FISCHER S, KHAZAEI S, and MEIER W. Chosen IV statistical analysis for key recovery attacks on stream ciphers[C]. Proceedings of the 1st International Conference on Cryptology in Africa, Casablanca, 2008: 236–245. doi: 10.1007/978-3-540-68164-9_16.

    18. [18]

      IZADI M, SADEGHIYAN B, SADEGHIAN S S, et al. MIBS: A new lightweight block cipher[C]. Proceedings of the 8th International Conference on Cryptology and Network Security, Kanazawa, 2009: 334–348. doi: 10.1007/978-3-642-10433-6_22.

    19. [19]

      ZAHERI M and SADEGHIAN B. Comparing resistance against cube like attacks[C]. Proceedings of the 24th Iranian Conference on Electrical Engineering, At Shiraz, 2016.

    1. [1]

      王建新, 方华威, 段晓毅, 佘高健. 基于滑动平均的能量分析攻击研究与实现. 电子与信息学报,

    2. [2]

      刘阳, 季新生, 刘彩霞. 网络社区发现优化:基于随机游走的边权预处理方法. 电子与信息学报,

    3. [3]

      袁庆军, 王安, 王永娟, 王涛. 基于流形学习能量数据预处理的模板攻击优化方法. 电子与信息学报,

    4. [4]

      曹瑛, 李志永, 卢晓鹏, 邹谋炎. 基于自适应邻域双边滤波的点目标检测预处理算法. 电子与信息学报,

    5. [5]

      莫韬甫, 邵士海, 刘田, 唐友喜. 异步MIMO-OFDM中基于预处理矩阵的迭代检测算法. 电子与信息学报,

    6. [6]

      何明浩, 李膺东, 张贤达. 基于均匀圆阵的宽频段二维零点预处理MUSIC算法. 电子与信息学报,

    7. [7]

      傅洪亮, 酆广增. 一种基于天线阵列的预处理盲多用户检测算法. 电子与信息学报,

    8. [8]

      赵发勇, 酆广增. 异步CDMA系统中基于预处理递归最小二乘恒模算法的盲自适应接收. 电子与信息学报,

    9. [9]

      张鹏, 李瑞林, 李超. Zodiac算法新的Square攻击. 电子与信息学报,

    10. [10]

      任炯炯, 李航, 陈少真. 减轮Simeck算法的积分攻击. 电子与信息学报,

    11. [11]

      海昕, 唐学海, 李超. 对Zodiac算法的中间相遇攻击. 电子与信息学报,

    12. [12]

      常亚勤, 金晨辉. 对Shannon算法的线性区分攻击. 电子与信息学报,

    13. [13]

      赵光辉, 陈伯孝, 吴向东, 张守宏. 基于差分预处理的米波雷达低仰角处理算法. 电子与信息学报,

    14. [14]

      王会梅, 鲜明, 王国玉. 基于扩展网络攻击图的网络攻击策略生成算法. 电子与信息学报,

    15. [15]

      宋昕, 汪晋宽, 韩英华. 基于二次型约束的鲁棒自适应波束形成算法. 电子与信息学报,

    16. [16]

      徐图, 罗瑜, 何大可. HSMC-SVM的二次逼近快速训练算法. 电子与信息学报,

    17. [17]

      郭业才, 赵俊渭. 基于信噪歪度比的二次相位耦合信号增强新算法. 电子与信息学报,

    18. [18]

      吴舟, 赵春晖. 基于博弈论的二次博弈波束成形算法. 电子与信息学报,

    19. [19]

      朱良学, 朱近康. 采用动态窗口宽度和二次平均算法的SSOA定位方法. 电子与信息学报,

    20. [20]

      张铭, 杨万麟, 李乐民. 空间滤波预处理法及其在单次快摄阵处理中的应用. 电子与信息学报,

  • 图 1  MIBS算法结构

    图 2  标准预处理阶段流程图

    图 3  改进预处理阶段流程

    表 1  MIBS算法S盒

    x0123456789abcdef
    S(x)4f38dac0b57e2619
    下载: 导出CSV

    表 2  第3轮S盒输出比特代数次数

    位置0123456789101112131415
    次数27272727272727272727272727272727
    位置16171819202122232425262728293031
    次数27272727272727272727272727272727
    位置32333435363738394041424344454647
    次数9999999999999999
    位置48495051525354555657585960616263
    次数9999999999999999
    下载: 导出CSV

    表 3  算法2的过程

     算法2 第3轮S盒输出覆盖密钥变量个数检测
    输出:每个比特覆盖的密钥变量个数
     $\left( 1 \right)\;{\rm{set}}\;D[64]\;{\rm{to}}\;0$
     $\left( 2 \right)\;{\rm{for}}\;i = 0\;{\rm{to}}\;63\;{\rm{do//}}$表示64个输出比特
     $\left( 3 \right)\;\;\;\;\;\;{\rm{for}}\;j = 0\;{\rm{to}}\;63\;{\rm{do//}}$检测64个密钥是否参与输出比特运算
     $\left( 4 \right)\;\;\;\;\;\;\;\;\;\;\;{\rm{for}}\;k = 1\;{\rm{to}}\;N\;{\rm{do//}}$测试N
     $\left( 5 \right)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{GetRandom}}(K)$
     $\left( 6 \right)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;K' = \neg K(j)$
     $\left( 7 \right)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;t = f(K) \oplus f(K')$
     $\left( 8 \right)\;\;\;\;\;\;\;\;\;\;\;{\rm{if}}\;\exists t = 1$
     $\left( 9 \right)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;D[i] + + $
     $\left( {10} \right)\;{\rm{return}}\;\;\;\;D$
    下载: 导出CSV

    表 4  第3轮S盒输出比特覆盖密钥数

    位置0123456789101112131415
    密钥数58585858585858585959595958585858
    位置16171819202122232425262728293031
    密钥数58585858585858585959595958585858
    位置32333435363738394041424344454647
    密钥数43434343434343434444444443434343
    位置48495051525354555657585960616263
    密钥数43434343434343434444444443434343
    下载: 导出CSV

    表 5  第3轮输出第8位泄露立方体

    维数立方体超多项式
    729 30 38 40 43 44 45${k_2} + {k_3} + {k_4} + {k_6} + {k_7} + {k_8} + {k_{13}} + {k_{16}} + {k_{38}}$
    723 27 28 35 47 60 61${k_1} + {k_4} + {k_{34}} + {k_{37}} + {k_{50}} + {k_{57}} + {k_{60}}$
    80 1 2 3 4 5 40 41${k_{55}}$
    80 1 2 3 8 9 52 53${k_{59}}$
    100 1 2 3 4 5 6 8 32 56${k_{59}} + {k_{60}}$
    100 1 2 3 4 5 6 16 43 48${k_3} + {k_4}$
    100 1 2 3 8 9 10 20 35 55${k_7} + {k_8}$
    104 7 16 19 29 30 31 32 33 34${k_2} + {k_{54}}$
    110 1 2 3 4 5 6 12 13 48 63${k_0}$
    110 1 2 3 4 5 6 16 17 40 49${k_3}$
    110 1 2 3 8 9 10 20 21 32 53${k_7}$
    120 1 2 3 4 5 6 8 10 24 36 39${k_{11}} + {k_{12}}$
    120 1 2 3 4 5 6 16 17 19 31 43${k_{13}}$
    121 2 3 4 5 6 7 8 9 10 18 32${k_2}$
    121 2 3 4 5 6 7 8 9 10 26 32${k_{10}}$
    120 1 2 3 4 5 6 8 9 11 15 43${k_{61}}$
    120 1 2 4 5 6 7 8 10 12 43 52${k_0} + {k_{63}}$
    120 1 2 3 4 5 6 8 9 11 12 14 41${k_{62}}$
    130 1 2 3 4 5 6 16 17 19 28 29 40${k_{15}}$
    130 1 2 3 4 5 6 16 17 19 28 29 41${k_{15}} + {k_{16}}$
    130 1 2 3 4 5 6 16 17 19 28 30 41${k_{14}}$
    135 6 17 19 25 26 27 28 29 30 31 32 33$1 + {k_{53}}$
    139 11 21 23 29 30 31 32 33 35 36 38 39${k_5} + {k_{57}}$
    141 2 3 4 5 6 8 9 10 11 20 21 22 32$1 + {k_0} + {k_{39}} + {k_{40}} + {k_{43}} + {k_{44}} + {k_{63}}$
    141 2 3 4 5 6 8 9 10 11 20 21 22 33$1 + {k_0} + {k_{40}} + {k_{44}}$
    141 2 3 4 5 6 8 9 10 11 20 21 23 32${k_0} + {k_1} + {k_{38}} + {k_{39}} + {k_{40}} + {k_{41}} $ $ + {k_{42}} + {k_{43}}+ {k_{44}} + {k_{45}} + {k_{62}} + {k_{63}}$
    141 2 3 4 5 6 8 9 10 11 20 21 23 33$1 + {k_{38}} + {k_{42}} + {k_{62}}$
    150 1 2 3 4 5 6 8 9 10 12 14 25 27 63$1 + {k_{11}}$
    151 2 3 4 5 6 8 9 10 11 12 13 15 27 6227 62${k_9}$
    174 5 13 14 15 16 17 18 19 20 21 22 24 25 26 28 30${k_{56}}$
    181 2 3 4 5 6 7 8 9 11 12 13 14 16 17 18 20 23${k_6} + {k_7}$
    201 2 3 4 5 6 8 9 10 12 13 14 16 17 19 20 22 23 58 61${k_{38}} + {k_{41}} + {k_{58}} + {k_{61}}$
    201 2 3 4 5 7 8 9 10 12 13 14 16 17 18 28 30 31 38 61$1 + {k_1} + {k_{42}} + {k_{45}} + {k_{54}} + {k_{57}} + {k_{58}} + {k_{61}} + {k_{62}}$
    下载: 导出CSV

    表 6  二次测试立方体

    维数立方体超多项式
    70 1 2 3 4 40 41$1 \!+\! {k_{55} }\! +\! {k_{56} } \!+\! {k_{54} }{k_{55} } \!+\! {k_{55} }{k_{56} }$
    100 1 2 3 4 5 6 8 32 40$1 + {k_{59}} + {k_{58}}{k_{60}} + {k_{59}}{k_{60}}$
    140 1 2 3 4 5 6 8 9 10 12 13 14 17${k_3} + {k_1}{k_4} + {k_3}{k_4}$
    140 1 2 3 4 5 6 8 9 10 12 13 14 21${k_7} + {k_5}{k_8} + {k_7}{k_8}$
    140 1 2 3 4 5 6 8 9 10 12 13 14 29${k_{15}} + {k_{13}}{k_{16}} + {k_{15}}{k_{16}}$
    191 2 3 4 5 6 8 9 10 12 13 14 16
    17 19 20 22 58 61
    ${k_8}{k_{38} } \!+\! {k_8}{k_{41} } \!+\! {k_8}{k_{58} } \!+\! {k_8}{k_{61} }$
    下载: 导出CSV

    表 7  结果对比

    方法攻击轮数选择明文密钥搜索空间
    文献[16]1${2^{6.39}}$${2^{40}}$
    文献[19]4未提及${2^{72}}$
    本文3${2^{21.64}}$${2^{25}}$
    下载: 导出CSV
  • 加载中
图(3)表(7)
计量
  • PDF下载量:  2
  • 文章访问数:  57
  • HTML全文浏览量:  19
文章相关
  • 通讯作者:  王涛, 1072637697@qq.com
  • 收稿日期:  2018-11-23
  • 录用日期:  2019-11-27
  • 网络出版日期:  2020-03-25
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章