高级搜索

留言板

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

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

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

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

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

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

doi: 10.11999/JEIT181075
基金项目: 国家自然科学基金(61872381, 61602512)
详细信息
    作者简介:

    王永娟:女,1972年生,副教授,主要研究方向为网络空间安全、密码算法分析

    王涛:男,1995年生,硕士生,研究方向为侧信道攻击

    袁庆军:男,1993年生,助教,研究方向为侧信道攻击

    高杨:男,1994年生,硕士生,研究方向为故障攻击

    王相宾:男,1996年生,硕士生,研究方向为侧信道攻击

    通讯作者:

    王涛 1072637697@qq.com

  • 中图分类号: TP309.7

Side Channel Cube Attack Improvement and Application to Cryptographic Algorithm

Funds: The National Natural Science Foundation of China(61872381, 61602512)
  • 摘要:

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

  • 图  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
  • DINUR I and SHAMIR A. Cube attacks on tweakable black box polynomials[C]. 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.
    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.
    VIELHABER M. Breaking ONE. FIVIUM by AIDA an algebraic IV differential attack[R]. 2007.
    AUMASSON J P, DINUR I, MEIER W, et al. Cube testers and key recovery attacks on reduced-round MD6 and trivium[C]. The 16th International Workshop on Fast Software Encryption, Leuven, Belgium, 2009: 1–22. doi: 10.1007/978-3-642-03317-9_1.
    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
    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
    SZMIDT J. The cube attack on Courtois toy cipher[C]. The 1st International Conference on Number-Theoretic Methods in Cryptology, Warsaw, Poland, 2017: 241–253. doi: 10.1007/978-3-319-76620-1_14.
    DINUR I and SHAMIR A. Side channel cube attacks on block ciphers[J]. IACR Cryptology Eprint Archive, 2009: 127.
    DINUR I and SHAMIR A. Breaking Grain-128 with dynamic cube attacks[C]. The 18th International Workshop on Fast Software Encryption, Lyngby, Denmark, 2011: 167–187. doi: 10.1007/978-3-642-21702-9_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
    HUANG Senyang, WANG Xiaoyun, XU Guangwu, et al. Conditional cube attack on reduced-round Keccak sponge function[C]. The 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, 2017: 259–288. doi: 10.1007/978-3-319-56614-6_9.
    LIU Meicheng, YANG Jingchun, WANG Wenhao, et al. Correlation cube attacks: From weak-key distinguisher to key recovery[C]. The 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 2018: 715–744. doi: 10.1007/978-3-319-78375-8_23.
    YANG Lin, WANG Meiqin, and QIAO Siyuan. Side channel cube attack on PRESENT[C]. The 8th International Conference on Cryptology and Network Security, Kanazawa, Japan, 2009: 379–391. doi: 10.1007/978-3-642-10433-6_25.
    ABDUL-LATIP S F, REYHANITABAR M R, SUSILO W, et al. On the security of NOEKEON against side channel cube attacks[C]. The 6th International Conference on Information Security Practice and Experience, Seoul, South Korea, 2010: 45–55. doi: 10.1007/978-3-642-12827-1_4.
    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
    刘会英, 王韬, 郭世泽, 等. 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
    FISCHER S, KHAZAEI S, and MEIER W. Chosen IV statistical analysis for key recovery attacks on stream ciphers[C]. The 1st International Conference on Cryptology in Africa, Casablanca, Morocco, 2008: 236–245. doi: 10.1007/978-3-540-68164-9_16.
    IZADI M, SADEGHIYAN B, SADEGHIAN S S, et al. MIBS: A new lightweight block cipher[C]. The 8th International Conference on Cryptology and Network Security, Kanazawa, Japan, 2009: 334–348. doi: 10.1007/978-3-642-10433-6_22.
    ZAHERI M and SADEGHIAN B. Comparing resistance against cube like attacks[C]. The 24th Iranian Conference on Electrical Engineering, At Shiraz, Iran, 2016.
  • 加载中
图(3) / 表(7)
计量
  • 文章访问数:  3832
  • HTML全文浏览量:  1103
  • PDF下载量:  88
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-11-23
  • 修回日期:  2019-11-27
  • 网络出版日期:  2020-03-25
  • 刊出日期:  2020-06-04

目录

    /

    返回文章
    返回