Side Channel Cube Attack Improvement and Application to Cryptographic Algorithm
-
摘要:
立方攻击的预处理阶段复杂度随输出比特代数次数的增长呈指数级增长,寻找有效立方集合的难度也随之增加。该文对立方攻击中预处理阶段的算法做了改进,在立方集合搜索时,由随机搜索变为带目标的搜索,设计了一个新的目标搜索优化算法,优化了预处理阶段的计算复杂度,进而使离线阶段时间复杂度显著降低。将改进的立方攻击结合旁路方法应用在MIBS分组密码算法上,从旁路攻击的角度分析MIBS的算法特点,在第3轮选择了泄露位置,建立关于初始密钥和输出比特的超定的线性方程组,可以直接恢复33 bit密钥,利用二次检测恢复6 bit密钥。所需选择明文量221.64,时间复杂度225。该结果较现有结果有较大改进,恢复的密钥数增多,在线阶段的时间复杂度降低。
Abstract:The complexity of the pre-processing phase of the cubic attack grows exponentially with the number of output bit algebras, and the difficulty of finding an effective cube set increases. In this paper, the algorithm of preprocessing stage in cubic attack is improved. In the cube set search, from random search to target search, a new target search optimization algorithm is designed to optimize the computational complexity of the preprocessing stage. In turn, the offline phase time complexity is significantly reduced. The improved cubic attack combined with the side-channel method is applied to the MIBS block cipher algorithm. The algorithm characteristics of MIBS are analyzed from the perspective of side-channel attack. The leak location is selected in the third round, and the overdetermined linear equations from initial key and output bit are established, which can directly recover 33bit key. Then the 6bit key can be recovered by quadric-detecting. The amount of plaintext required is 221.64, time complexity is 225. This result is greatly improved compared with the existing results, the number of keys recovered is increased, and the time complexity of the online phase is reduced.
-
Key words:
- Cube attack /
- Side channel attack /
- Preprocessing /
- Quadric-detecting /
- MIBS algorithm
-
表 1 MIBS算法S盒
x 0 1 2 3 4 5 6 7 8 9 a b c d e f S(x) 4 f 3 8 d a c 0 b 5 7 e 2 6 1 9 表 2 第3轮S盒输出比特代数次数
位置 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 次数 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 位置 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 次数 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 位置 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 次数 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 位置 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 次数 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 表 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$ 表 4 第3轮S盒输出比特覆盖密钥数
位置 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 密钥数 58 58 58 58 58 58 58 58 59 59 59 59 58 58 58 58 位置 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 密钥数 58 58 58 58 58 58 58 58 59 59 59 59 58 58 58 58 位置 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 密钥数 43 43 43 43 43 43 43 43 44 44 44 44 43 43 43 43 位置 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 密钥数 43 43 43 43 43 43 43 43 44 44 44 44 43 43 43 43 表 5 第3轮输出第8位泄露立方体
维数 立方体 超多项式 7 29 30 38 40 43 44 45 ${k_2} + {k_3} + {k_4} + {k_6} + {k_7} + {k_8} + {k_{13}} + {k_{16}} + {k_{38}}$ 7 23 27 28 35 47 60 61 ${k_1} + {k_4} + {k_{34}} + {k_{37}} + {k_{50}} + {k_{57}} + {k_{60}}$ 8 0 1 2 3 4 5 40 41 ${k_{55}}$ 8 0 1 2 3 8 9 52 53 ${k_{59}}$ 10 0 1 2 3 4 5 6 8 32 56 ${k_{59}} + {k_{60}}$ 10 0 1 2 3 4 5 6 16 43 48 ${k_3} + {k_4}$ 10 0 1 2 3 8 9 10 20 35 55 ${k_7} + {k_8}$ 10 4 7 16 19 29 30 31 32 33 34 ${k_2} + {k_{54}}$ 11 0 1 2 3 4 5 6 12 13 48 63 ${k_0}$ 11 0 1 2 3 4 5 6 16 17 40 49 ${k_3}$ 11 0 1 2 3 8 9 10 20 21 32 53 ${k_7}$ 12 0 1 2 3 4 5 6 8 10 24 36 39 ${k_{11}} + {k_{12}}$ 12 0 1 2 3 4 5 6 16 17 19 31 43 ${k_{13}}$ 12 1 2 3 4 5 6 7 8 9 10 18 32 ${k_2}$ 12 1 2 3 4 5 6 7 8 9 10 26 32 ${k_{10}}$ 12 0 1 2 3 4 5 6 8 9 11 15 43 ${k_{61}}$ 12 0 1 2 4 5 6 7 8 10 12 43 52 ${k_0} + {k_{63}}$ 12 0 1 2 3 4 5 6 8 9 11 12 14 41 ${k_{62}}$ 13 0 1 2 3 4 5 6 16 17 19 28 29 40 ${k_{15}}$ 13 0 1 2 3 4 5 6 16 17 19 28 29 41 ${k_{15}} + {k_{16}}$ 13 0 1 2 3 4 5 6 16 17 19 28 30 41 ${k_{14}}$ 13 5 6 17 19 25 26 27 28 29 30 31 32 33 $1 + {k_{53}}$ 13 9 11 21 23 29 30 31 32 33 35 36 38 39 ${k_5} + {k_{57}}$ 14 1 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}}$ 14 1 2 3 4 5 6 8 9 10 11 20 21 22 33 $1 + {k_0} + {k_{40}} + {k_{44}}$ 14 1 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}}$ 14 1 2 3 4 5 6 8 9 10 11 20 21 23 33 $1 + {k_{38}} + {k_{42}} + {k_{62}}$ 15 0 1 2 3 4 5 6 8 9 10 12 14 25 27 63 $1 + {k_{11}}$ 15 1 2 3 4 5 6 8 9 10 11 12 13 15 27 6227 62 ${k_9}$ 17 4 5 13 14 15 16 17 18 19 20 21 22 24 25 26 28 30 ${k_{56}}$ 18 1 2 3 4 5 6 7 8 9 11 12 13 14 16 17 18 20 23 ${k_6} + {k_7}$ 20 1 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}}$ 20 1 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}}$ 表 6 二次测试立方体
维数 立方体 超多项式 7 0 1 2 3 4 40 41 $1 \!+\! {k_{55} }\! +\! {k_{56} } \!+\! {k_{54} }{k_{55} } \!+\! {k_{55} }{k_{56} }$ 10 0 1 2 3 4 5 6 8 32 40 $1 + {k_{59}} + {k_{58}}{k_{60}} + {k_{59}}{k_{60}}$ 14 0 1 2 3 4 5 6 8 9 10 12 13 14 17 ${k_3} + {k_1}{k_4} + {k_3}{k_4}$ 14 0 1 2 3 4 5 6 8 9 10 12 13 14 21 ${k_7} + {k_5}{k_8} + {k_7}{k_8}$ 14 0 1 2 3 4 5 6 8 9 10 12 13 14 29 ${k_{15}} + {k_{13}}{k_{16}} + {k_{15}}{k_{16}}$ 19 1 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} }$ -
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.011MA 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.069LIU 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.