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

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

doi:10.11999/JEIT181075

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

doi: 10.11999/JEIT181075

1.
战略支援部队信息工程大学郑州 450001
2.
河南省网络密码技术重点实验室郑州 450001

基金项目: 国家自然科学基金(61872381, 61602512)

详细信息

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

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

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

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

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

通讯作者:
王涛　1072637697@qq.com

中图分类号: TP309.7
计量
- 文章访问数: 3857
- HTML全文浏览量: 1119
- PDF下载量: 89
- 被引次数: 0
出版历程
- 收稿日期: 2018-11-23
- 修回日期: 2019-11-27
- 网络出版日期: 2020-03-25
- 刊出日期: 2020-06-04

Side Channel Cube Attack Improvement and Application to Cryptographic Algorithm

1.
PLA Strategic Support Force Information Engineering University, Zhengzhou 450001, China
2.
Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China

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

摘要

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

HTML全文

图 1 MIBS算法结构

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

图 3 改进预处理阶段流程

下载: 全尺寸图片幻灯片

表 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

下载: 导出CSV

表 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

下载: 导出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盒输出比特覆盖密钥数

位置	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

下载: 导出CSV

表 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}}$

下载: 导出CSV

表 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} }$

下载: 导出CSV

表 7 结果对比

方法	攻击轮数	选择明文	密钥搜索空间
文献[16]	1	${2^{6.39}}$	${2^{40}}$
文献[19]	4	未提及	${2^{72}}$
本文	3	${2^{21.64}}$	${2^{25}}$

下载: 导出CSV

参考文献(19)

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.

施引文献

资源附件(0)

访问统计