密碼算法旁路立方攻擊改進(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
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
-
摘要:
立方攻擊的預(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密鑰。所需選擇明文量221.64,時(shí)間復(fù)雜度225。該結(jié)果較現(xiàn)有結(jié)果有較大改進(jìn),恢復(fù)的密鑰數(shù)增多,在線階段的時(shí)間復(fù)雜度降低。
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
-
表 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
-
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.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 劉會(huì)英, 王韜, 郭世澤, 等. MIBS密碼旁路立方體攻擊[J]. 計(jì)算機(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. -