Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (8): 2462-2470.DOI: 10.11772/j.issn.1001-9081.2022060886
Special Issue: 网络空间安全
• Cyber security • Previous Articles Next Articles
Dongdong LIN1,2, Manman LI1,2(), Shaozhen CHEN1,2
Received:
2022-06-20
Revised:
2022-08-30
Accepted:
2022-09-01
Online:
2022-09-22
Published:
2023-08-10
Contact:
Manman LI
About author:
LIN Dongdong,born in 1998, M. S. candidate. His research interests include deep learning, intelligent cryptanalysis of block cipher.Supported by:
通讯作者:
李曼曼
作者简介:
林东东(1998—),男,河南邓州人,硕士研究生,主要研究方向:深度学习、智能化分组密码分析基金资助:
CLC Number:
Dongdong LIN, Manman LI, Shaozhen CHEN. Conditional differential cryptanalysis method of KATAN48 algorithm based on neural distinguishers[J]. Journal of Computer Applications, 2023, 43(8): 2462-2470.
林东东, 李曼曼, 陈少真. 基于神经区分器的KATAN48算法条件差分分析方法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2462-2470.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2022060886
攻击类型 | 攻击条件 | 攻击 轮数 | 时间 复杂度 | 数据 复杂度 | 参考 文献 |
---|---|---|---|---|---|
条件差分 分析 | 单密钥 | 70 | 234 | 234CP | 文献[ |
相关密钥 | 103 | 225 | 225CP | 文献[ | |
相关密钥 | 140 | 277.4 | 227CP | 文献[ | |
MIMT ASR | 单密钥 | 105 | 279.1 | 144CP | 文献[ |
Match Box MIMT | 单密钥 | 129 | 278.5 | 32CP | 文献[ |
多维MIMT | 单密钥 | 148 | 279 | 2KP | 文献[ |
基于神经区分器的条件差分分析 | 单密钥 | 80 | 219.68 | 216.39CP | 本文 |
Tab. 1 Attack results of KATAN48 algorithm
攻击类型 | 攻击条件 | 攻击 轮数 | 时间 复杂度 | 数据 复杂度 | 参考 文献 |
---|---|---|---|---|---|
条件差分 分析 | 单密钥 | 70 | 234 | 234CP | 文献[ |
相关密钥 | 103 | 225 | 225CP | 文献[ | |
相关密钥 | 140 | 277.4 | 227CP | 文献[ | |
MIMT ASR | 单密钥 | 105 | 279.1 | 144CP | 文献[ |
Match Box MIMT | 单密钥 | 129 | 278.5 | 32CP | 文献[ |
多维MIMT | 单密钥 | 148 | 279 | 2KP | 文献[ |
基于神经区分器的条件差分分析 | 单密钥 | 80 | 219.68 | 216.39CP | 本文 |
符号 | 含义 | 符号 | 含义 |
---|---|---|---|
48比特明文数据 | 第 | ||
48比特密文数据 | 第 | ||
第 | |||
第 | |||
80比特主密钥 | 明文组 | ||
第 | 明文结构 | ||
第 | 密文结构 | ||
第 |
Tab. 2 Symbol description
符号 | 含义 | 符号 | 含义 |
---|---|---|---|
48比特明文数据 | 第 | ||
48比特密文数据 | 第 | ||
第 | |||
第 | |||
80比特主密钥 | 明文组 | ||
第 | 明文结构 | ||
第 | 密文结构 | ||
第 |
超参数 | 参数取值 | 超参数 | 参数取值 |
---|---|---|---|
训练集规模 | 107 | 优化器 | Adam |
测试集规模 | 106 | 学习率 | 10-4 |
批处理规模 | 1 000 | 损失函数 | MSE |
迭代周期 | 200 |
Tab. 3 Hyperparameter setting of neural network
超参数 | 参数取值 | 超参数 | 参数取值 |
---|---|---|---|
训练集规模 | 107 | 优化器 | Adam |
测试集规模 | 106 | 学习率 | 10-4 |
批处理规模 | 1 000 | 损失函数 | MSE |
迭代周期 | 200 |
区分器轮数 | 多差分堆叠数 | 准确率/% |
---|---|---|
40 | 1 | 61.7 |
40 | 4 | 74.2 |
40 | 16 | 90.9 |
40 | 48 | 98.7 |
50 | 1 | 50.1 |
50 | 48 | 54.0 |
Tab. 4 MODND accuracy of KATAN48 algorithm with different numbers of stacked differences
区分器轮数 | 多差分堆叠数 | 准确率/% |
---|---|---|
40 | 1 | 61.7 |
40 | 4 | 74.2 |
40 | 16 | 90.9 |
40 | 48 | 98.7 |
50 | 1 | 50.1 |
50 | 48 | 54.0 |
准确率/% | 准确率/% | 准确率/% | 准确率/% | ||||
---|---|---|---|---|---|---|---|
47 | 84.9 | 35 | 61.6 | 23 | 75.6 | 11 | 59.8 |
46 | 91.8 | 34 | 64.1 | 22 | 86.5 | 10 | 62.3 |
45 | 93.1 | 33 | 66.7 | 21 | 85.4 | 9 | 66.3 |
44 | 97.2 | 32 | 66.9 | 20 | 86.4 | 8 | 65.4 |
43 | 97.4 | 31 | 65.5 | 19 | 60.5 | 7 | 72.6 |
42 | 98.7 | 30 | 73.7 | 18 | 58.9 | 6 | 69.7 |
41 | 77.5 | 29 | 78.3 | 17 | 62.9 | 5 | 76.4 |
40 | 83.7 | 28 | 77.5 | 16 | 66.7 | 4 | 74.7 |
39 | 72.9 | 27 | 76.7 | 15 | 58.6 | 3 | 76.9 |
38 | 72.5 | 26 | 76.9 | 14 | 54.0 | 2 | 75.0 |
37 | 73.3 | 25 | 88.5 | 13 | 57.9 | 1 | 77.9 |
36 | 78.5 | 24 | 87.1 | 12 | 58.1 | 0 | 79.5 |
Tab. 5 MODND accuracy of 40-round KATAN48 algorithm with different input differences
准确率/% | 准确率/% | 准确率/% | 准确率/% | ||||
---|---|---|---|---|---|---|---|
47 | 84.9 | 35 | 61.6 | 23 | 75.6 | 11 | 59.8 |
46 | 91.8 | 34 | 64.1 | 22 | 86.5 | 10 | 62.3 |
45 | 93.1 | 33 | 66.7 | 21 | 85.4 | 9 | 66.3 |
44 | 97.2 | 32 | 66.9 | 20 | 86.4 | 8 | 65.4 |
43 | 97.4 | 31 | 65.5 | 19 | 60.5 | 7 | 72.6 |
42 | 98.7 | 30 | 73.7 | 18 | 58.9 | 6 | 69.7 |
41 | 77.5 | 29 | 78.3 | 17 | 62.9 | 5 | 76.4 |
40 | 83.7 | 28 | 77.5 | 16 | 66.7 | 4 | 74.7 |
39 | 72.9 | 27 | 76.7 | 15 | 58.6 | 3 | 76.9 |
38 | 72.5 | 26 | 76.9 | 14 | 54.0 | 2 | 75.0 |
37 | 73.3 | 25 | 88.5 | 13 | 57.9 | 1 | 77.9 |
36 | 78.5 | 24 | 87.1 | 12 | 58.1 | 0 | 79.5 |
输出 差分 | 约束条件数 | 差分路径轮数 | 输出 差分 | 约束条件数 | 差分路径轮数 |
---|---|---|---|---|---|
42 | 15 | 23 | 45 | 12 | 16 |
43 | 12 | 17 | 46 | 18 | 20 |
44 | 16 | 17 |
Tab. 6 Number of constraint conditions and rounds of differential paths of MILP model with different output differences
输出 差分 | 约束条件数 | 差分路径轮数 | 输出 差分 | 约束条件数 | 差分路径轮数 |
---|---|---|---|---|---|
42 | 15 | 23 | 45 | 12 | 16 |
43 | 12 | 17 | 46 | 18 | 20 |
44 | 16 | 17 |
轮数 | 差分状态 | 约束条件 |
---|---|---|
0 | 000100000000000000000000100000000100000000100100 001000000000000000000001000000001000000001001000 | |
1 | 010000000000000000000010000000010000000010010000 100000000000000000000100000000100000000100100000 | |
2 | 000000000000000000001000000001000000001001000001 000000000000000000000000000010000000010010000010 | |
3 | 000000000000000000000000000100000000100100000100 000000000000000000000000001000000001001000001000 | |
4 | 000000000000000000000000010000000010010000010000 000000000000000000000000100000000100100000100000 | |
5 | 000000000000000000000001000000001001000001000000 000000000000000000000010000000010010000010000000 | |
6 | 000000000000000000000100000000100100000100000000 000000000000000000001000000001001000001000000000 | |
7 | 000000000000000000010000000010010000010000000000 000000000000000000000000000100100000100000000000 | |
8 | 000000000000000000000000001001000001000000000000 000000000000000000000000010010000010000000000000 | |
9 | 000000000000000000000000100100000100000000000000 000000000000000000000001001000001000000000000000 | |
10 | 000000000000000000000010010000010000000000000000 000000000000000000000100100000100000000000000000 | |
11 | 000000000000000000001001000001000000000000000000 000000000000000000010010000010000000000000000000 | |
12 | 000000000000000000000100000100000000000000000000 000000000000000000001000001000000000000000000000 | |
13 | 000000000000000000010000010000000000000000000000 000000000000000000100000100000000000000000000000 | |
14 | 000000000000000001000001000000000000000000000000 000000000000000010000010000000000000000000000000 | |
15 | 000000000000000100000100000000000000000000000000 000000000000001000001000000000000000000000000000 | |
16 | 000000000000010000010000000000000000000000000000 000000000000100000100000000000000000000000000000 | |
17 | 000000000001000001000000000000000000000000000000 000000000010000010000000000000000000000000000000 | |
18 | 000000000100000100000000000000000000000000000000 000000001000001000000000000000000000000000000000 | |
19 | 000000010000010000000000000000000000000000000000 000000100000100000000000000000000000000000000000 | |
20 | 000001000001000000000000000000000000000000000000 000010000010000000000000000000000000000000000000 | |
21 | 000100000100000000000000000000000000000000000000 001000001000000000000000000000000000000000000000 | |
22 | 010000010000000000000000000000000000000000000000 100000100000000000000000000000000000000000000000 | |
23 | 000001000000000000000000000000000000000000000000 |
Tab. 7 Differential paths and corresponding constraint conditions of KATAN48 algorithm
轮数 | 差分状态 | 约束条件 |
---|---|---|
0 | 000100000000000000000000100000000100000000100100 001000000000000000000001000000001000000001001000 | |
1 | 010000000000000000000010000000010000000010010000 100000000000000000000100000000100000000100100000 | |
2 | 000000000000000000001000000001000000001001000001 000000000000000000000000000010000000010010000010 | |
3 | 000000000000000000000000000100000000100100000100 000000000000000000000000001000000001001000001000 | |
4 | 000000000000000000000000010000000010010000010000 000000000000000000000000100000000100100000100000 | |
5 | 000000000000000000000001000000001001000001000000 000000000000000000000010000000010010000010000000 | |
6 | 000000000000000000000100000000100100000100000000 000000000000000000001000000001001000001000000000 | |
7 | 000000000000000000010000000010010000010000000000 000000000000000000000000000100100000100000000000 | |
8 | 000000000000000000000000001001000001000000000000 000000000000000000000000010010000010000000000000 | |
9 | 000000000000000000000000100100000100000000000000 000000000000000000000001001000001000000000000000 | |
10 | 000000000000000000000010010000010000000000000000 000000000000000000000100100000100000000000000000 | |
11 | 000000000000000000001001000001000000000000000000 000000000000000000010010000010000000000000000000 | |
12 | 000000000000000000000100000100000000000000000000 000000000000000000001000001000000000000000000000 | |
13 | 000000000000000000010000010000000000000000000000 000000000000000000100000100000000000000000000000 | |
14 | 000000000000000001000001000000000000000000000000 000000000000000010000010000000000000000000000000 | |
15 | 000000000000000100000100000000000000000000000000 000000000000001000001000000000000000000000000000 | |
16 | 000000000000010000010000000000000000000000000000 000000000000100000100000000000000000000000000000 | |
17 | 000000000001000001000000000000000000000000000000 000000000010000010000000000000000000000000000000 | |
18 | 000000000100000100000000000000000000000000000000 000000001000001000000000000000000000000000000000 | |
19 | 000000010000010000000000000000000000000000000000 000000100000100000000000000000000000000000000000 | |
20 | 000001000001000000000000000000000000000000000000 000010000010000000000000000000000000000000000000 | |
21 | 000100000100000000000000000000000000000000000000 001000001000000000000000000000000000000000000000 | |
22 | 010000010000000000000000000000000000000000000000 100000100000000000000000000000000000000000000000 | |
23 | 000001000000000000000000000000000000000000000000 |
区分器轮数 | 准确率/% | 区分器轮数 | 准确率/% |
---|---|---|---|
43 | 85.8 | 47 | 60.0 |
44 | 76.8 | 48 | 56.4 |
45 | 73.1 | 49 | 55.5 |
46 | 67.3 | 50 | 54.0 |
Tab. 8 Distinguisher accuracy of KATAN48 algorithm
区分器轮数 | 准确率/% | 区分器轮数 | 准确率/% |
---|---|---|---|
43 | 85.8 | 47 | 60.0 |
44 | 76.8 | 48 | 56.4 |
45 | 73.1 | 49 | 55.5 |
46 | 67.3 | 50 | 54.0 |
攻击轮数 | 成功次数 | 攻击轮数 | 成功次数 |
---|---|---|---|
78 | 97 | 80 | 98 |
79 | 94 |
Tab. 9 Key recovery attack results of KATAN48 algorithm
攻击轮数 | 成功次数 | 攻击轮数 | 成功次数 |
---|---|---|---|
78 | 97 | 80 | 98 |
79 | 94 |
攻击类型 | 攻击 轮数 | 恢复的密钥 比特数 | 时间 复杂度 | 数据 复杂度 |
---|---|---|---|---|
条件差分分析[ | 70 | 2 | 234 | 234 |
基于神经区分器的 条件差分分析 | 78 | 20 | 218.10 | 214.26 |
79 | 22 | 218.28 | 214.54 | |
80 | 24 | 219.68 | 216.39 |
Tab. 10 Key recovery attack results of KATAN48 algorithm in single key setting
攻击类型 | 攻击 轮数 | 恢复的密钥 比特数 | 时间 复杂度 | 数据 复杂度 |
---|---|---|---|---|
条件差分分析[ | 70 | 2 | 234 | 234 |
基于神经区分器的 条件差分分析 | 78 | 20 | 218.10 | 214.26 |
79 | 22 | 218.28 | 214.54 | |
80 | 24 | 219.68 | 216.39 |
1 | 张政馗,庞为光,谢文静,等. 面向实时应用的深度学习研究综述[J]. 软件学报, 2020, 31(9): 2654-2677. |
ZHANG Z K, PANG W G, XIE W J, et al. Deep learning for real-time applications: a survey[J]. Journal of Software, 2020, 31(9): 2654-2677. | |
2 | HINTON G E, OSINDERO S, TEH Y W. A fast learning algorithm for deep belief nets[J]. Neural Computation, 2006, 18(7): 1527-1554. 10.1162/neco.2006.18.7.1527 |
3 | LAWRENCE S, GILES C L, TSOI A C, et al. Face recognition: a convolutional neural network approach[J]. IEEE Transactions on Neural Networks, 1997, 8(1):98-113. 10.1109/72.554195 |
4 | WILLIAMS R, ZIPSER D. A learning algorithm for continually running fully recurrent neural networks[J]. Neural Computation, 1989, 1(2):270-280. 10.1162/neco.1989.1.2.270 |
5 | RIVEST R L. Cryptography and machine learning[C]// Proceedings of the 1991 International Conference on the Theory and Application of Cryptology, LNCS 739. Berlin: Springer, 1993: 427-439. 10.1007/3-540-57332-1_36 |
6 | GREYDANUS S. Learning the enigma with recurrent neural networks[EB/OL]. (2017-09-07) [2022-06-24].. |
7 | GOMEZ A N, HUANG S C, ZHANG I, et al. Unsupervised cipher cracking using discrete GANs[EB/OL]. (2018-01-15) [2022-06-15].. |
8 | GOHR A. Improving attacks on round-reduced speck32/64 using deep learning[C]// Proceedings of the 2019 Annual International Cryptology Conference. Cham: Springer, 2019: 150-179. 10.1007/978-3-030-26951-7_6 |
9 | BAO Z Z, GUO J, LIU M C, et al. Conditional differential-neural cryptanalysis[EB/OL]. (2021-05-31) [2021-07-19].. |
10 | BENAMIRA A, GERAULT D, PEYRIN T, et al. A deeper look at machine learning-based cryptanalysis[C]// Proceedings of the 2021 Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 12696. Cham: Springer, 2021: 805-835. |
11 | HOU Z Z, REN J J, CHEN S Z. Improve neural distinguishers of SIMON and SPECK[J]. Security and Communication Networks, 2021, 2021: No.9288229. 10.1155/2021/9288229 |
12 | CHEN Y, SHEN Y T, YU H B, et al. A new neural distinguisher considering features derived from multiple ciphertext pairs[EB/OL].[2022-01-20]. . 10.1093/comjnl/bxac019 |
13 | DE CANNIÈRE C, DUNKELMAN O, KNEŽEVIĆ M. KATAN and KTANTAN — a family of small and efficient hardware-oriented block ciphers[C]// Proceedings of the 2009 International Workshop on Cryptographic Hardware and Embedded Systems, LNCS 5747. Berlin: Springer, 2009: 272-288. |
14 | KNELLWOLF S, MEIER W, NAYA-PLASENCIA M. Conditional differential cryptanalysis of NLFSR-based cryptosystems[C]// Proceedings of the 2010 International Conference on the Theory and Application of Cryptology and Information Security, LNCS 6477. Berlin: Springer, 2010: 130-145. |
15 | KNELLWOLF S, MEIER W, NAYA-PLASENCIA M. Conditional differential cryptanalysis of Trivium and KATAN[C]// Proceedings of the 2011 International Workshop on Selected Areas in Cryptography, LNCS 7118. Berlin: Springer, 2012: 200-212. |
16 | 刘爱森,王美琴,李艳斌. KATAN密码算法的相关密钥差分攻击[J]. 密码学报, 2015, 2(1): 77-91. |
LIU A S, WANG M Q, LI Y B. Related-key conditional differential cryptanalysis of KATAN family[J]. Journal of Cryptologic Research, 2015, 2(1): 77-91. | |
17 | ISOBE T, SHIBUTANI K. Improved all-subkeys recovery attacks on FOX, KATAN and SHACAL-2 block ciphers[C]// Proceedings of the 2014 International Workshop on Fast Software Encryption, LNCS 8540. Berlin: Springer, 2015: 104-126. |
18 | FUHR T, MINAUD B. Match box meet-in-the-middle attack against KATAN[C]// Proceedings of the 2014 International Workshop on Fast Software Encryption, LNCS 8540. Berlin: Springer, 2015: 61-81. |
19 | SHAHRAM R, HAVARD R. Improved multi-dimensional meet-in-the-middle cryptanalysis of KATAN[J]. Tatra Mountains Mathematical Publications, 2016, 67(1): 149-166. 10.1515/tmmp-2016-0037 |
20 | PELIKAN M, GOLDBERG D E, CANTÚ-PAZ E. BOA: the Bayesian optimization algorithm[C]// Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation. San Francisco: Morgan Kaufmann Publishers Inc., 1999: 525-532. 10.1162/106365600750078808 |
21 | HE K M, ZHANG X Y, REN S Q, et al. Deep residual learning for image recognition[C]// Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2016: 770-778. 10.1109/cvpr.2016.90 |
22 | BIHAM E, CHEN R. Near-collisions of SHA-0[C]// Proceedings of the 2004 Annual International Cryptology Conference, LNCS 3152. Berlin: Springer, 2004: 290-305. |
23 | XING Z H, ZHANG W Y, HAN G Y. Improved conditional differential analysis on NLFSR-based block cipher KATAN32 with MILP[C]// Proceedings of the 2020 International Conference on Security and Privacy in New Computing Environments, LNICST 344. Cham: Springer, 2020: 370-393. 10.1007/978-3-030-66922-5_26 |
[1] | Yanjun LI, Yaodong GE, Qi WANG, Weiguo ZHANG, Chen LIU. Improved KLEIN algorithm and its quantum analysis [J]. Journal of Computer Applications, 2024, 44(9): 2810-2817. |
[2] | Yong XIANG, Yanjun LI, Dingyun HUANG, Yu CHEN, Huiqin XIE. Differential and linear characteristic analysis of full-round Shadow algorithm [J]. Journal of Computer Applications, 2024, 44(12): 3839-3843. |
[3] | Guangyao ZHAO, Xuan SHEN, Bo YU, Chenhui YI, Zhen LI. Impossible differential cryptanalysis of reduced-round ultra-lightweight block cipher PFP [J]. Journal of Computer Applications, 2023, 43(9): 2784-2788. |
[4] | LIU Zongfu, YUAN Zheng, ZHAO Chenxi, ZHU Liang. Integral attack on PICO algorithm based on division property [J]. Journal of Computer Applications, 2020, 40(10): 2967-2972. |
[5] | MA Yunfei, WANG Tao, CHEN Hao, HUANG Changyang. Algebraic fault attack on lightweight block ciphers SIMON [J]. Journal of Computer Applications, 2017, 37(7): 1953-1959. |
[6] | CHENG Lu, WEI Yuechuan, PAN Xiaozhong, LI Anhui. Multidimensional zero-correlation linear cryptanalysis on Zodiac cipher algorithm [J]. Journal of Computer Applications, 2017, 37(6): 1605-1608. |
[7] | WANG Shoucheng, XU Jinhui, YAN Yingjian, LI Gongli, JIA Yongwang. Software pipelining realization method of AES algorithm based on cipher stream processor [J]. Journal of Computer Applications, 2017, 37(6): 1620-1624. |
[8] | QIN Guanjie, MA Jianshe, CHENG Xuemin. Method for increasing S-box nonlinearity based on combination of hill climbing [J]. Journal of Computer Applications, 2015, 35(8): 2195-2198. |
[9] | LI Lingchen, WEI Yongzhuang, ZHU Jialiang. Meet-in-the-middle attack on 11-round reduced 3D block cipher [J]. Journal of Computer Applications, 2015, 35(3): 700-703. |
[10] | WEI Hongru ZHEN Yafei WANG Xinyu. Biclique cryptanalysis of ARIRANG-256 [J]. Journal of Computer Applications, 2014, 34(1): 69-72. |
[11] | SU Chong-mao. New impossible deferential attack on 7-round reduced ARIA [J]. Journal of Computer Applications, 2012, 32(01): 45-48. |
[12] | Dan-hua LU Cheng ZHONG Feng YANG. AES security model based on multi-core multithread [J]. Journal of Computer Applications, 2011, 31(04): 1003-1005. |
[13] | . Construction method of S-box suitable for hardware implementation [J]. Journal of Computer Applications, 2010, 30(3): 674-676. |
[14] | . S-boxes reorganization algorithm for a class of block ciphers [J]. Journal of Computer Applications, 2009, 29(08): 2198-2199. |
[15] | . New chaotic image encryption algorithm based on hybrid feedback [J]. Journal of Computer Applications, 2008, 28(2): 434-436. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||