密碼算法旁路立方攻擊改進(jìn)與應(yīng)用

王永娟; 王濤; 袁慶軍; 高楊; 王相賓

doi:10.11999/JEIT181075

密碼算法旁路立方攻擊改進(jìn)與應(yīng)用

doi: 10.11999/JEIT181075

1.
戰(zhàn)略支援部隊(duì)信息工程大學(xué) 鄭州 450001
2.
河南省網(wǎng)絡(luò)密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室鄭州 450001

基金項(xiàng)目: 國家自然科學(xué)基金(61872381, 61602512)

詳細(xì)信息

作者簡介:
王永娟：女，1972年生，副教授，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全、密碼算法分析

王濤：男，1995年生，碩士生，研究方向?yàn)閭?cè)信道攻擊

袁慶軍：男，1993年生，助教，研究方向?yàn)閭?cè)信道攻擊

高楊：男，1994年生，碩士生，研究方向?yàn)楣收瞎?/p>
王相賓：男，1996年生，碩士生，研究方向?yàn)閭?cè)信道攻擊

通訊作者:
王濤　1072637697@qq.com

中圖分類號(hào): TP309.7
計(jì)量
- 文章訪問數(shù): 3901
- HTML全文瀏覽量: 1150
- PDF下載量: 92
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-11-23
- 修回日期: 2019-11-27
- 網(wǎng)絡(luò)出版日期: 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)

摘要

摘要:
立方攻擊的預(yù)處理階段復(fù)雜度隨輸出比特代數(shù)次數(shù)的增長呈指數(shù)級(jí)增長，尋找有效立方集合的難度也隨之增加。該文對(duì)立方攻擊中預(yù)處理階段的算法做了改進(jìn)，在立方集合搜索時(shí)，由隨機(jī)搜索變?yōu)閹繕?biāo)的搜索，設(shè)計(jì)了一個(gè)新的目標(biāo)搜索優(yōu)化算法，優(yōu)化了預(yù)處理階段的計(jì)算復(fù)雜度，進(jìn)而使離線階段時(shí)間復(fù)雜度顯著降低。將改進(jìn)的立方攻擊結(jié)合旁路方法應(yīng)用在MIBS分組密碼算法上，從旁路攻擊的角度分析MIBS的算法特點(diǎn)，在第3輪選擇了泄露位置，建立關(guān)于初始密鑰和輸出比特的超定的線性方程組，可以直接恢復(fù)33 bit密鑰，利用二次檢測恢復(fù)6 bit密鑰。所需選擇明文量2^21.64，時(shí)間復(fù)雜度2²⁵。該結(jié)果較現(xiàn)有結(jié)果有較大改進(jìn)，恢復(fù)的密鑰數(shù)增多，在線階段的時(shí)間復(fù)雜度降低。
- 立方攻擊 /
- 旁路攻擊 /
- 預(yù)處理 /
- 二次檢測 /
- 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算法結(jié)構(gòu)

下載: 全尺寸圖片幻燈片

圖 2 標(biāo)準(zhǔn)預(yù)處理階段流程圖

下載: 全尺寸圖片幻燈片

圖 3 改進(jìn)預(yù)處理階段流程

下載: 全尺寸圖片幻燈片

表 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

下載: 導(dǎo)出CSV

表 2 第3輪S盒輸出比特代數(shù)次數(shù)

位置	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
次數(shù)	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
次數(shù)	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
次數(shù)	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
次數(shù)	9	9	9	9	9	9	9	9	9	9	9	9	9	9	9	9

下載: 導(dǎo)出CSV

表 3 算法2的過程

算法2 第3輪S盒輸出覆蓋密鑰變量個(gè)數(shù)檢測

輸出：每個(gè)比特覆蓋的密鑰變量個(gè)數(shù)

　$\left( 1 \right)\;{\rm{set}}\;D[64]\;{\rm{to}}\;0$

　$\left( 2 \right)\;{\rm{for}}\;i = 0\;{\rm{to}}\;63\;{\rm{do//}}$表示64個(gè)輸出比特

　$\left( 3 \right)\;\;\;\;\;\;{\rm{for}}\;j = 0\;{\rm{to}}\;63\;{\rm{do//}}$檢測64個(gè)密鑰是否參與輸出比特運(yùn)算

　$\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$

下載: 導(dǎo)出CSV

表 4 第3輪S盒輸出比特覆蓋密鑰數(shù)

位置	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
密鑰數(shù)	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
密鑰數(shù)	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
密鑰數(shù)	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
密鑰數(shù)	43	43	43	43	43	43	43	43	44	44	44	44	43	43	43	43

下載: 導(dǎo)出CSV

表 5 第3輪輸出第8位泄露立方體

維數(shù)	立方體	超多項(xiàng)式
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}}$

下載: 導(dǎo)出CSV

表 6 二次測試立方體

維數(shù)	立方體	超多項(xiàng)式
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} }$

下載: 導(dǎo)出CSV

表 7 結(jié)果對(duì)比

方法	攻擊輪數(shù)	選擇明文	密鑰搜索空間
文獻(xiàn)[16]	1	${2^{6.39}}$	${2^{40}}$
文獻(xiàn)[19]	4	未提及	${2^{72}}$
本文	3	${2^{21.64}}$	${2^{25}}$

下載: 導(dǎo)出CSV

參考文獻(xiàn)(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í)分組密碼故障立方攻擊[J]. 浙江大學(xué)學(xué)報(bào): 工學(xué)版, 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

劉會(huì)英, 王韜, 郭世澤, 等. MIBS密碼旁路立方體攻擊[J]. 計(jì)算機(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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)