基于机器学习的分组密码结构识别

doi:10.11959/j.issn.2096-109x.2023040

摘要/Abstract

摘要：

加密算法的识别与区分是密码分析领域的重要组成部分，是密钥恢复技术的前提条件之一，随着人工智能技术的不断发展，利用机器学习、神经网络等技术研究密码分析问题日趋成熟，这为实现以加密算法为代表的密码体制识别技术提供了有效的思路与启发。通过研究机器学习的基本原理，从理论和实验两个角度对Feistel和SPN结构的多种常见分组密码算法进行了识别实验，解决了随机密钥条件下利用未知密文识别分组密码加密结构的问题。引入游程分布指标、特征分布函数和KL散度等概念，通过分析两种分组密码结构加密后的密文特征分布，推导随机密钥条件下两种结构密文游程分布表达式，利用KL散度计算分布的差异性，证明两种结构密文间存在差异性，论证了实验的可行性；根据理论结果，建立了随机森林和Adaboosting2种机器学习模型，对12种分组密码算法在随机密钥条件下全轮加密后的密文提取密文游程分布指标，按照同种结构单一算法和同种结构混合算法两种标准对不同结构分组密码算法进行了识别。实验结果显示，两组实验中对各个具体算法的结构识别准确率高于80%，较已有工作提高40%左右，有效解决了随机密钥情况下分组密码结构识别问题，严格证明了两种分组密码结构之间在密文扩散性、分布关系上确实存在可区分的差异性，也为密码算法设计和安全性评估提供一定的参考。

关键词: 分组密码, 机器学习, 特征指标, 概率统计, 密数据识别

Abstract:

Cryptographic identification is a critical aspect of cryptanalysis and a fundamental premise for key recovery.With the advancement of artificial intelligence, cryptanalysis based on machine learning has become increasingly mature, providing more effective methods and valuable insights for cryptographic identification.The distinguishability experiments were performed based on the Machine Learning to identify the structures of block ciphers in conditions of random keys.The identification of two structures of block ciphers from theoretical and experimental angles was studied.The differences of features in two structures’ cipher texts have been deduced by introducing the runs distribution index, feature distribution functions, KL-divergence, etc.After completing the feasibility research, experiments to identify the structures of two block ciphers using two Machine Learning models and the runs distribution index were conducted.The experiments were divided into two groups: single algorithm group and mixture algorithms group.It is found that the accuracy of both groups are more than 80%, which is around 40% higher than former work.The problem of identifying the structures of Block Ciphers in the conditions of random keys is solved in detail.Meanwhile, differences between the two structures of block ciphers are verified, which can serve as a reference for the design of cryptography algorithms.

Key words: block ciphers, machine learning, feature indices, probabilities and statistic, cryptography identification

中图分类号:

TP393

夏锐琪, 李曼曼, 陈少真. 基于机器学习的分组密码结构识别[J]. 网络与信息安全学报, 2023, 9(3): 79-89.

Ruiqi XIA, Manman LI, Shaozhen CHEN. Identification on the structures of block ciphers using machine learning[J]. Chinese Journal of Network and Information Security, 2023, 9(3): 79-89.

图/表 14

图1

图2

图3

图4

图5

表1

图6

图7

图8

表2

图9

表3

表4

表5

参考文献 30

[1]	RIVEST R L . Cryptography and machine learning[C]// The International Conference on the Theory and Application of Cryptology. 1991: 427-439.
[2]	RAMZAN Z . On using neural networks to break cryptosystems[J]. Manuscript, 1998.
[3]	POOJA M . Classification of ciphers[R]. Indian Institute of Technology,Kanpur, 2001.
[4]	DILEEP A D , SEKHAR C C . Identification of block ciphers using support vector machines[C]// The 2006 IEEE International Joint Conference on Neural Network Proceedings. 2006: 2696-2701.
[5]	MANJULA R , ANITHA R . Identification of encryption algorithm using decision tree[C]// International Conference on Computer Science and Information Technology. 2011: 237-246.
[6]	MISHRA S , BHATTACHARJYA A . Pattern analysis of cipher text:a combined approach[C]// 2013 International Conference on Recent Trends in Information Technology (ICRTIT). 2013: 393-398.
[7]	BARBOSA F , VIDAL A , MELLO F . Machine learning for cryptographic algorithm identification[J]. Journal of Information Security and Cryptography (Enigma), 2016,3(1): 3-8.
[8]	CHOU J W , LIN S D , CHENG C M . On the effectiveness of using state-of-the-art machine learning techniques to launch cryptographic distinguishing attacks[C]// Proceedings of the 5th ACM Workshop on Security and Artificial Intelligence. 2012: 105-110.
[9]	赵志诚 . 基于机器学习的密码体制识别研究[D]. 郑州:信息工程大学, 2018.
	ZHAO Z C . The Research of Cryptosystem Recognition Scheme Based on Machine Learning[D]. Zhengzhou:Information Engineering University, 2018.
[10]	李洪超 . 基于密文特征的密码算法识别研究[D]. 西安:西安电子科技大学, 2018.
	LI H C . Cipher-text features based cipher system recognition[D]. Xi’an:Xidian University, 2018.
[11]	SOUZA W A R , TOMLINSON A . A distinguishing attack with a neural network[C]// 2013 IEEE 13th International Conference on Data Mining Workshops. 2013: 154-161.
[12]	PAMIDIPARTHI S , VELAMPALLI S . Cryptographic algorithm identification using deep learning techniques[M]// Evolution in Computational Intelligence. 2021: 785-793.
[13]	曹莉茹 . 基于深度学习的密码算法识别研究[D]. 成都:电子科技大学, 2021.
	CAO L R . A research of cryptographic algorithm recognition scheme based on machine learning[D]. Chengdu:University of Electronic Science and Technology of China, 2021.
[14]	ZAMAN J , GHOSH R . Review on fifteen statistical tests proposed by NIST[J]. Journal of Theoretical Physics and Cryptography, 2012,1: 18-31.
[15]	HOFFSTEIN J , SILVERMAN J H . Random small hamming weight products with applications to cryptography[J]. Discrete Applied Mathematics, 2003,130(1): 37-49.
[16]	WU C K , FENG D . Boolean function representation of S-boxes and boolean permutations[M]// Boolean Functions and Their Applications in Cryptography. 2016: 217-241.
[17]	COVER T M , THOMAS J A . Entropy,relative entropy and mutual information[J]. Elements of Information Theory, 1991,2(1): 12-13.
[18]	BIAU G , SCORNET E . A random forest guided tour[J]. Test, 2016,25(2): 197-227.
[19]	YING C , QI GUANG M , JIA Chen L ,et al. Advance and prospects of AdaBoost algorithm[J]. Acta Automatica Sinica, 2013,39(6): 745-758.
[20]	AKKAR M L , GIRAUD C . An implementation of DES and AES,secure against some attacks[C]// International Workshop on Cryptographic Hardware and Embedded Systems. 2001: 309-318.
[21]	BIHAM E , ANDERSON R , KNUDSEN L . Serpent:a new block cipher proposal[C]// International Workshop on Fast Software Encryption. 1998: 222-238.
[22]	LIU G , GHOSH M , SONG L . Security analysis of SKINNY under related-tweakey settings[J]. Cryptology ePrint Archive, 2016.
[23]	BOGDANOV A , KNUDSEN L R , LEANDER G ,et al. PRESENT:an ultra-lightweight block cipher[C]// International Workshop on Cryptographic Hardware and Embedded Systems. 2007: 450-466.
[24]	BANIK S , BOGDANOV A , ISOBE T ,et al. Midori:a block cipher for low energy[C]// International Conference on the Theory and Application of Cryptology and Information Security. 2015: 411-436.
[25]	PARK J , YUN Y , KIM Y D ,et al. Design and implementation of ARIA cryptic algorithm[J]. Journal of the Institute of Electronics Engineers of Korea SD, 2005,42(4): 29-36.
[26]	SCHNEIER B . The Twofish encryption algorithm[J]. Dr.Dobb's Journal:Software Tools for the Professional Programmer, 1998,23(12): 30-34.
[27]	BEAULIEU R , SHORS D , SMITH J ,et al. The SIMON and SPECK lightweight block ciphers[C]// Proceedings of the 52nd Annual Design Automation Conference. 2015: 1-6.
[28]	HALAGALI B P , DESAI V V . Implementation of chaos based cryptography in kasumi block cipher[C]// 2018 International Conference on Communication and Signal Processing (ICCSP). 2018: 165-169.
[29]	SUZAKI T , MINEMATSU K , MORIOKA S ,et al. Twine:a lightweight,versatile block cipher[C]// ECRYPT Workshop on Lightweight Cryptography. 2011, 2011.
[30]	THAKUR J , KUMAR N . DES,AES and blowfish:symmetric key cryptography algorithms simulation based performance analysis[J]. International Journal of Emerging Technology and Advanced Engineering, 2011,1(2): 6-12.

SPN结构	Feistel结构
AES-128^[20]	DES^[30]
Serpent-128^[21]	SIMON-64^[27]
SKINNY-64^[22]	Speck-32^[27]
PRESENT^[23]	KASUMI^[28]
Midori-64^[24]	Twofish^[26]
ARIA-128^[25]	TWINE^[29]

密文特征算法	标签
AES-128	S1
Serpent-128	S2
SKINNY-64	S3
PRESENT	S4
Midori-64	S5
ARIA-128	S6
DES	F1
SIMON-64	F2
Speck-32	F3
KASUMI	F4
Twofish	F5
TWINE	F6

—	F1	F2	F3	F4	F5	F6
S1	88.2%	96.7%	95.6%	91.2%	90.7%	92.3%
S2	93.4%	97.8%	98.9%	98.9%	99.0%	92.7%
S3	99.3%	97.8%	97.0%	94.5%	91.3%	90.8%
S4	91%	81.4%	86.2%	93.7%	95.7%	97.6%
S5	91.2%	97.3%	97.3%	88.5%	96.4%	95.9%
S6	91.1%	91.0%	89.2%	89.3%	92.7%	93.8%

—	F1	F2	F3	F4	F5	F6
S1	92.2%	96.7%	95.6%	99%	99.7%	92.3%
S2	97.8%	97.8%	98.9%	98.9%	99.0%	92.7%
S3	99.3%	97.8%	97.0%	94.5%	91.3%	99.8%
S4	91%	95.2%	99.5%	93.7%	95.7%	97.6%
S5	91.2%	97.3%	97.3%	96.2%	96.4%	95.9%
S6	99.1%	88.9%	97.0%	99.3%	99.7%	99.8%

模型	准确率
随机森林模型	90.1%
Adaboosting模型	92.9%