Differential Analysis of ARX Block Ciphers Based on an Improved Genetic Algorithm

KANG Man; LI Yongqiang; JIAO Lin; WANG Mingsheng

doi:10.23919/cje.2021.00.415

Volume 32 Issue 2

Mar. 2023

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2023 > 32(2): 225-236

KANG Man, LI Yongqiang, JIAO Lin, et al., “Differential Analysis of ARX Block Ciphers Based on an Improved Genetic Algorithm,” Chinese Journal of Electronics, vol. 32, no. 2, pp. 225-236, 2023, doi: 10.23919/cje.2021.00.415

Citation:

KANG Man, LI Yongqiang, JIAO Lin, et al., “Differential Analysis of ARX Block Ciphers Based on an Improved Genetic Algorithm,” Chinese Journal of Electronics, vol. 32, no. 2, pp. 225-236, 2023, doi: 10.23919/cje.2021.00.415

Citation:

PDF( 2675 KB)

Differential Analysis of ARX Block Ciphers Based on an Improved Genetic Algorithm

doi: 10.23919/cje.2021.00.415

KANG Man^{1, 2
,},
LI Yongqiang^{1, 2
,},
JIAO Lin^3
,,
WANG Mingsheng^{1, 2
,}

1.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100195, China
2.
School of Cyber Security, University of Chinese Academy of Sciences, Beijing 071051, China
3.
State Key Laboratory of Cryptology, Beijing 100878, China

Funds: This work was supported by the National Natural Science Foundation of China (61772516, 61902030, 61772517)

More Information

Author Bio:
Man KANG received the B.S. degree from Hebei GEO University, Shijiazhuang, China, in 2013, and the M.S. degree from the Beijing University of Chemical Technology, Beijing, China, in 2017. She is currently pursuing the Ph.D. degree at the Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China. Her research interests include cryptography and information security. (Email: kangman@iie.ac.cn)

Yongqiang LI (corresponding author) received the B.S. and M.S. degrees in mathematics from Beijing Normal University, Beijing, China, in 2005 and 2008, respectively, and the Ph.D. degree in information security from the Institute of Software, Chinese Academy of Sciences, China, in January 2012. He is currently an Associate Professor with the Institute of Information Engineering, Chinese Academy of Sciences. His research interests include symmetric cryptography and related areas. (Email: liyongqiang@iie.ac.cn)

Lin JIAO received the B.S. degree from Jilin University, Jilin, China, in 2010, and the Ph.D. degree from the Institute of Software, Chinese Academy of Sciences, Beijing, China, in 2016. She is currently working with the State Key Laboratory of Cryptology, Beijing. Her research interests include symmetric cryptography and related areas. (Email: jiaolin_jl@126.com)

Mingsheng WANG received the Ph.D. degree from Beijing Normal University, Beijing, China, in 1994. He is currently a Professor with the Institute of Information Engineering, Chinese Academy of Sciences, Beijing. His research interests include computational algebra, cryptography, and information security. (Email: wangmingsheng@iie.ac.cn)
Received Date: 2021-11-06
Accepted Date: 2022-02-11

Available Online: 2022-03-07

Publish Date: 2023-03-05

Abstract

Abstract

Differential cryptanalysis is one of the most critical analysis methods to evaluate the security strength of cryptographic algorithms. This paper first applies the genetic algorithm to search for differential characteristics in differential cryptanalysis. A new algorithm is proposed as the fitness function to generate a high-probability differential characteristic from a given input difference. Based on the differential of the differential characteristic found by genetic algorithm, Boolean satisfiability (SAT) is used to search all its differential characteristics to calculate the exact differential probability. In addition, a penalty-like function is also proposed to guide the search direction for the application of the stochastic algorithm to differential cryptanalysis. Our new automated cryptanalysis method is applied to SPECK32 and SPECK48. As a result, the 10-round differential probability of SPECK32 is improved to 2^−30.34, and a 12-round differential of SPECK48 with differential probability 2^−46.78 is achieved. Furthermore, the corresponding differential attacks are also performed. The experimental results show our method’s validity and outstanding performance in differential cryptanalysis.
- Genetic algorithm,
- Differential cryptanalysis,
- SPECK,
- Satisfiability (SAT)

FullText(HTML)

References(40)

References

[1]	E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” in Advances in Cryptology – CRYPTO’90, Santa Barbara, California, USA, 1990.
[2]	M. Matsui, “On correlation between the order of S-boxes and the strength of DES,” in Advances in Cryptology – EUROCRYPT’94, Springer Berlin Heidelberg, Berlin, Heidelberg, pp.366–375, 1994.
[3]	K. Fu, M. Wang, Y. Guo, et al., “MILP-based automatic search algorithms for differential and linear trails for speck,” in Fast Software Encryption – FSE 2016, Springer Berlin Heidelberg, Berlin, Heidelberg, pp.268–288, 2016.
[4]	N. Mouha, Q. Wang, D. Gu, et al., “Differential and linear cryptanalysis using mixed-integer linear programming,” in Information Security and Cryptology – Inscrypt 2011, Springer Berlin Heidelberg, Berlin, Heidelberg, pp.57–76, 2012.
[5]	S. Wu and M. Wang, “Security evaluation against differential cryptanalysis for block cipher structures,” Cryptology ePrint Archive, Report 2011/551, 2011.
[6]	L. Song, Z. Huang, and Q. Yang, “Automatic differential analysis of ARX block ciphers with application to SPECK and LEA,” in Information Security and Privacy – ACISP 2016, Springer International Publishing, Cham, pp.379–394, 2016.
[7]	D. Gérault, P. Lafourcade, M. Minier, et al., “Computing AES relatedkey differential characteristics with constraint programming,” Artificial Intelligence, vol.278, pp.103–183, 2020.
[8]	J. Holland, “Adaptation in natural and artificial systems,” Ph.D.Thesis, University of Michigan Press, Ann Arbor, USA, 1975.
[9]	I. Nikolić, “How to use metaheuristics for design of symmetric-key primitives,” in Advances in Cryptology – ASIACRYPT 2017, Springer International Publishing, Cham, pp.369–391, 2017.
[10]	G. Ivanov, N. Nikolov, and S. Nikova, “Reversed genetic algorithms for generation of bijective s-boxes with good cryptographic properties,” Cryptography & Communications, vol.8, no.2, pp.247–276, 2016.
[11]	S. Picek, L. Mariot, B. Yang, et al., “Design of s-boxes defined with cellular automata rules,” in Proceedings of the Computing Frontiers Conference, Siena, Italy, pp.409–414, 2017.
[12]	S. Picek, K. Knezevic, D. Jakobovic, et al., “C³PO: Cipher construction with cartesian genetic programming,” in Proceedings of the Genetic and Evolutionary Computation Conference Companion, Prague, Czech Republic, pp.1625–1633, 2019.
[13]	A. M. B. Albassall and A. A. Wahdan, “Genetic algorithm cryptanalysis of a feistel type block cipher,” in Proceedings of International Conference on Electrical, Electronic and Computer Engineering (ICEEC’04), Cairo, Egypt, pp.217–221, 2004.
[14]	K. Dworak and U. Boryczka, “Genetic algorithm as optimization tool for differential cryptanalysis of DES6,” in Computational Collective Intelligence – ICCCI 2017, Springer International Publishing, Cham, pp.107–116, 2017.
[15]	A. Garrett, J. Hamilton, and G. Dozier, “A comparison of genetic algorithm techniques for the cryptanalysis of tea,” International Journal of Intelligent Control & Systems, vol.12, no.4, Available at: https://www.researchgate.net/publication/228671512_A_Comparison_of_Genetic_Algorithm_Techniques_for_the_Cryptanalysis_of_TEA, 2007.
[16]	J. C. Hernandez and P. Isasi, “Finding efficient distinguishers for cryptographic mappings, with an application to the block cipher TEA,” in Proceedings of The 2003 Congress on Evolutionary Computation (CEC03), Canberra, ACT, Australia, vol.3, pp.2189–2193, 2003.
[17]	R. Ratan, “Applications of genetic algorithms in cryptology,” in Proceedings of the Third International Conference on Soft Computing for Problem Solving, Springer India, New Delhi, pp.821–831, 2014.
[18]	Z. Zhang, W. Zhang, and H. Shi, “Genetic algorithm assisted state-recovery attack on round-reduced xoodyak,” in Computer Security – ESORICS 2021, Springer International Publishing, Cham, pp.257–274, 2021.
[19]	K. Jayachandiran, “A machine learning approach for cryptanalysis,” RIT Computer Science, Available at: https://www.semanticscholar.org/paper/A-Machine-Learning-Approach-for-Cryptanalysis-Jayachandiran/e1616cdb40415a6444a4b2dbfbf197d60bcc43d3, 2016.
[20]	H. Maghrebi, T. Portigliatti, and E. Prouff, “Breaking cryptographic implementations using deep learning techniques,” Security, Privacy, and Applied Cryptography Engineering – SPACE 2016, Springer International Publishing, Cham, pp.3–26, 2016.
[21]	A. Gohr, “Improving attacks on round-reduced speck 32/64 using deep learning,” in Advances in Cryptology – CRYPTO 2019, Springer International Publishing, Cham, pp.150–179, 2019.
[22]	A. Jain, V. Kohli, and G. Mishra, “Deep learning based differential distinguisher for lightweight cipher present,” Cryptology ePrint Archive, Paper 2020/846, 2020.
[23]	A. Baksi, J. Breier, Y. Chen, et al., “Machine learning assisted differential distinguishers for lightweight ciphers,” in Proceedings of 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE 2021), Grenoble, France, pp.176–181, 2021.
[24]	A. Benamira, D. Gerault, T. Peyrin, et al., “A deeper look at machine learning-based cryptanalysis,” in Advances in Cryptology – EUROCRYPT 2021, Springer International Publishing, Cham, pp.805–835, 2021.
[25]	T. Yadav and M. Kumar, “Differential-ML distinguisher: Machine learning based generic extension for differential cryptanalysis,” in Progress in Cryptology – LATINCRYPT 2021, Springer International Publishing, Cham, pp.191–212, 2021.
[26]	Z. Liu, Y. Li, L. Jiao, et al., “A new method for searching optimal differential and linear trails in ARX ciphers,” IEEE Transactions on Information Theory, vol.67, no.2, pp.1054–1068, 2021. doi: 10.1109/TIT.2020.3040543
[27]	A. Biryukov, A. Roy, and V. Velichkov, “Differential analysis of block ciphers SIMON and SPECK,” in Fast Software Encryption – FSE 2014, Springer Berlin Heidelberg, Berlin, Heidelberg, pp.546–570, 2015.
[28]	A. D. Dwivedi, D. Ashutosh, P. Morawiecki, et al., “Differential cryptanalysis of round-reduced SPECK suitable for Internet of things devices,” IEEE Access, vol.7, pp.16476–16486, 2019. doi: 10.1109/ACCESS.2019.2894337
[29]	I. Dinur, “Improved differential cryptanalysis of round-reduced speck,” in Selected Areas in Cryptography – SAC 2014, Springer International Publishing, Cham, pp.147–164, 2014.
[30]	X. Lai, J. L. Massey, and S. Murphy, “Markov ciphers and differential cryptanalysis,” in Advances in Cryptology – EUROCRYPT’91, Springer Berlin Heidelberg, Berlin, Heidelberg, pp.17–38, 1991.
[31]	R. Beaulieu, S. Treatman-Clark, D. Shors, et al., “The simon and speck lightweight block ciphers,” in Proceedings of 2015 52nd ACM/EDAC/IEEE Design Automation Conference (DAC), San Francisco, CA, USA, article no.175, 2015.
[32]	R. Beaulieu, D. Shors, J. Smith, et al., “Simon and speck: Block ciphers for the internet of things,” Cryptology ePrint Archive, Paper 2015/585, 2015.
[33]	H. Lipmaa and S. Moriai, “Efficient algorithms for computing differential properties of addition,” in Fast Software Encryption – FSE 2001, Springer Berlin Heidelberg, Berlin, Heidelberg, pp.336–350, 2002.
[34]	K. Dejong, “Analysis of the behavior of a class of genetic adaptive systems,” Ph.D. Thesis, University of Michigan, USA, 1975.
[35]	T. Weise, Global Optimization Algorithm: Theory and Application, 2nd ed., Self-published, Available at: http://www.it-weise.de/projects/book.pdf, 2009.
[36]	M. Soos, K. Nohl, and C. Castelluccia, “Extending SAT solvers to cryptographic problems,” in Theory and Applications of Satisfiability Testing – SAT 2009, Springer Berlin Heidelberg, Berlin, Heidelberg, pp.244–257, 2009.
[37]	N. Mouha and B. Preneel, “Towards finding optimal differential characteristics for ARX: Application to salsa20,” Cryptology ePrint Archive, Paper 2013/328, 2013.
[38]	A. Biryukov, V. Velichkov, and Y. Corre, “Automatic search for the best trails in ARX: Application to block cipher speck,” in Fast Software Encryption – FSE 2016, Springer Berlin Heidelberg, Berlin, Heidelberg, pp.289–310, 2016.
[39]	L. Sun, W. Wang, and M. Wang, “Accelerating the search of differential and linear characteristics with the SAT method,” IACR Trans. on Symmetric Cryptology, vol.2021, no.1, pp.269–315, 2021. doi: 10.46586/tosc.v2021.i1.269-315
[40]	F. Abed, E. List, S. Lucks, et al., “Differential cryptanalysis of round-reduced SIMON and SPECK,” in Fast Software Encryption – FSE 2014, Springer Berlin Heidelberg, Berlin, Heidelberg, pp.525–545, 2015.