The Exchange Attack and the Mixture Differential Attack Revisited: From the Perspective of Automatic Evaluation

QIAO Kexin; ZHANG Zhiyu; NIU Zhongfeng; ZHU Liehuang

doi:10.23919/cje.2023.00.008

Volume 33 Issue 1

Jan. 2024

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2024 > 33(1): 19-29

Kexin QIAO, Zhiyu ZHANG, Zhongfeng NIU, et al., “The Exchange Attack and the Mixture Differential Attack Revisited: From the Perspective of Automatic Evaluation,” Chinese Journal of Electronics, vol. 33, no. 1, pp. 19–29, 2024 doi: 10.23919/cje.2023.00.008

Citation:

Kexin QIAO, Zhiyu ZHANG, Zhongfeng NIU, et al., “The Exchange Attack and the Mixture Differential Attack Revisited: From the Perspective of Automatic Evaluation,” Chinese Journal of Electronics, vol. 33, no. 1, pp. 19–29, 2024 doi: 10.23919/cje.2023.00.008

Citation:

PDF( 3188 KB)

The Exchange Attack and the Mixture Differential Attack Revisited: From the Perspective of Automatic Evaluation

doi: 10.23919/cje.2023.00.008

QIAO Kexin^{1, 2
,
,},
ZHANG Zhiyu^{3, 4
,},
NIU Zhongfeng^4
,,
ZHU Liehuang^1
,

1.
School of Cyberspace Science and Technology, Beijing Institute of Technology, Beijing 100081, China
2.
State Key Laboratory of Cryptology, P.O.Box 5159, Beijing 100878, China
3.
Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100085, China
4.
School of Cryptography, University of Chinese Academy of Sciences, Beijing 100049, China

More Information

Author Bio:
Kexin QIAO is currently an Assistant Professor at School of Cyberspace Science and Technology, Beijing Institute of Technology. She received the Ph.D. degree from the University of Chinese Academy of Sciences in 2017, then worked at Bank Card Test Center until 2020. Her research interest includes cryptanalysis on symmetric ciphers and side-channel attacks. (Email: qiao.kexin@bit.edu.cn)

Zhiyu ZHANG is currently a Ph.D. student at the Institute of Information Engineering, Chinese Academy of Sciences. His research interest is cryptanalysis on symmetric ciphers. (Email: zhangzhiyu@iie.ac.cn)

Zhongfeng NIU is currently a Ph.D. student at the School of Cryptography, University of Chinese Academy of Sciences. His research interest is cryptanalysis on symmetric ciphers. (Email: niuzhongfeng1996@163.com)

Liehuang ZHU is currently a Professor at the Department of Cyberspace Science, Beijing Institute of Technology. He is selected into the Program for New Century Excellent Talents in University from the Ministry of Education, China. His research interests include the Internet of things, cloud computing security, Internet, and mobile security. (Email: liehuangz@bit.edu.cn)
Corresponding author: Email: qiao.kexin@bit.edu.cn
Received Date: 2023-01-05
Accepted Date: 2023-03-22

Available Online: 2023-07-06

Publish Date: 2024-01-05

Abstract

Abstract

Recent results show that the differential properties within quadruples boom as a new inspiration in cryptanalysis of Advanced Encryption Standard (AES)-like constructions. These methods include the exchange attack proposed in Asiacrypt’19, the mixture differential attack proposed in ToSC’18, etc., where the essential properties are obtained by manually scrutinizing the structures of the AES-like constructions. This paper presents a novel framework and an automatic tool based on mixed integer linear programming to search for mixture differential distinguishers for general constructions. This framework considers what equality patterns among quadruples can make a distinguisher and traces how the patterns propagate through cipher components with accurate probability estimation. With this tool, a 5-round AES distinguishing attack with lower complexity and more 6-round distinguishing attacks in the chosen plaintext scenarios are deduced. We prove that no exchange-type or mixture differential distinguisher exists for 7 and above rounds AES if the details of the Sbox and MixColumns matrix are not taken into account.
- Mixed integer linear programming,
- Automatic search,
- Mixture differential cryptanalysis,
- Exchange attack,
- Advanced Encryption Standard (AES)

FullText(HTML)

References(30)

References

[1]	National Institute of Standards and Technology, “FIPS PUB 197: Advanced encryption standard (AES),” Federal Information Processing Standards Publication, Gaithersburg, MD, USA, pp. 1–38, 2001.
[2]	C. Boura, V. Lallemand, M. Naya-Plasencia, et al., “Making the impossible possible,” Journal of Cryptology, vol. 31, no. 1, pp. 101–133, 2018. doi: 10.1007/s00145-016-9251-7
[3]	N. Ferguson, J. Kelsey, S. Lucks, et al., “Improved cryptanalysis of rijndael,” in Proceedings of the 7th International Workshop on Fast Software Encryption, New York, NY, USA, pp. 213–230, 2001.
[4]	P. Derbez and P. A. Fouque, “Exhausting demirci-selçuk meet-in-the-middle attacks against reduced-round AES,” in Proceedings of the 20th International Workshop on Fast Software Encryption, Singapore, Singapore, pp. 541–560, 2014.
[5]	T. R. Shi, B. Hu, J. Guan, et al., “Cryptanalysis of AEGIS-128,” Chinese Journal of Electronics, vol. 31, no. 2, pp. 285–292, 2022. doi: 10.1049/cje.2020.00.231
[6]	B. Sun, M. C. Liu, J. Guo, et al., “New insights on AES-like SPN ciphers,” in Proceedings of the 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, pp. 605–624, 2016.
[7]	L. Grassi, C. Rechberger, and S. Rønjom, “A new structural-differential property of 5-round AES,” in Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, pp. 289–317, 2017.
[8]	L. Grassi, “Mixture differential cryptanalysis: A new approach to distinguishers and attacks on round-reduced AES,” IACR Transactions on Symmetric Cryptology, vol. 2018, no. 2, pp. 133–160, 2018. doi: 10.13154/tosc.v2018.i2.133-160
[9]	L. Grassi, “Probabilistic mixture differential cryptanalysis on round-reduced AES,” in Proceedings of the 26th International Conference on Selected Areas in Cryptography, Waterloo, Canada, pp. 53–84, 2019.
[10]	A. Bar-On, O. Dunkelman, N. Keller, et al., “Improved key recovery attacks on reduced-round AES with practical data and memory complexities,” Journal of Cryptology, vol. 33, no. 3, pp. 1003–1043, 2020. doi: 10.1007/s00145-019-09336-w
[11]	N. G. Bardeh and S. Rønjom, “The exchange attack: How to distinguish six rounds of AES with 2^88.2 chosen plaintexts,” in Proceedings of the 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, pp. 347–370, 2019.
[12]	O. Dunkelman, N. Keller, E. Ronen, et al., “The retracing boomerang attack,” in Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, pp. 280–309, 2020.
[13]	M. Rahman, D. Saha, and G. Paul, “Boomeyong: Embedding yoyo within boomerang and its applications to key recovery attacks on AES and pholkos,” IACR Transactions on Symmetric Cryptology, vol. 2021, no. 3, pp. 137–169, 2021. doi: 10.46586/TOSC.V2021.I3.137-169
[14]	N. G. Bardeh and V. Rijmen, “New key-recovery attack on reduced-round AES,” IACR Transactions on Symmetric Cryptology, vol. 2022, no. 2, pp. 43–62, 2022. doi: 10.46586/tosc.v2022.i2.43-62
[15]	J. Daemen and V. Rijmen, “New criteria for linear maps in AES-like ciphers,” Cryptography and Communications, vol. 1, no. 1, pp. 47–69, 2009. doi: 10.1007/s12095-008-0003-x
[16]	N. Mouha, Q. J. Wang, D. W. Gu, et al., “Differential and linear cryptanalysis using mixed-integer linear programming,” in Proceedings of the 7th International Conference on Information Security and Cryptology, Beijing, China, pp. 57–76, 2012.
[17]	S. W. Sun, L. Hu, P. Wang, et al., “Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers,” in Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security, Taiwan, China, pp. 158–178, 2014.
[18]	Y. Sasaki and Y. Todo, “New impossible differential search tool from design and cryptanalysis aspects: Revealing structural properties of several ciphers,” in Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, pp. 185–215, 2017.
[19]	C. Cid, T. Huang, T. Peyrin, et al., “A security analysis of deoxys and its internal tweakable block ciphers,” IACR Transactions on Symmetric Cryptology, vol. 2017, no. 3, pp. 73–107, 2017. doi: 10.13154/tosc.v2017.i3.73-107
[20]	H. Hadipour, N. Bagheri, and L. Song, “Improved rectangle attacks on skinny and CRAFT,” IACR Transactions on Symmetric Cryptology, vol. 2021, no. 2, pp. 140–198, 2021. doi: 10.46586/TOSC.V2021.I2.140–198
[21]	A. Bariant, and G. Leurent, “Truncated boomerang attacks and application to AES-based ciphers,” in Proceedings of the 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, pp. 3–35, 2023.
[22]	Z. J. Xiang, W. T. Zhang, Z. Z. Bao, et al., “Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers,” in Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, pp. 648–678, 2016.
[23]	Q. J. Wang, Y. L. Hao, Y. Todo, et al., “Improved division property based cube attacks exploiting algebraic properties of superpoly,” in Proceedings of the 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, pp. 275–305, 2018.
[24]	K. Hu, S. W. Sun, M. Q. Wang, et al., “An algebraic formulation of the division property: Revisiting degree evaluations, cube attacks, and key-independent sums,” in Proceedings of the 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, pp. 446–476, 2020.
[25]	D. P. Shi, S. W. Sun, P. Derbez, et al., “Programming the demirci-selçuk meet-in-the-middle attack with constraints,” in Proceedings of the 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, Australia, pp. 3–34, 2018.
[26]	Z. Z. Bao, X. Y. Dong, J. Guo, et al., “Automatic search of meet-in-the-middle preimage attacks on AES-like hashing,” in Proceedings of the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, pp. 771–804, 2021.
[27]	X. Y. Dong, J. L. Hua, S. W. Sun, et al., “Meet-in-the-middle attacks revisited: Key-recovery, collision, and preimage attacks,” in Proceedings of the 41st Annual International Cryptology Conference, Virtual Event, pp. 278–308, 2021.
[28]	X. Y. Dong, J. Guo, S. Li, et al., “Triangulating rebound attack on AES-like hashing,” in Proceedings of the 42nd Annual International Cryptology Conference, Santa Barbara, CA, USA, pp. 94–124, 2022.
[29]	S. Rønjom, N. G. Bardeh, and T. Helleseth, “Yoyo tricks with AES,” in Proceedings of the 23rd International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, China, pp. 217–243, 2017.
[30]	C. Boura and D. Coggia, “Efficient MILP modelings for sboxes and linear layers of SPN ciphers,” IACR Transactions on Symmetric Cryptology, vol. 2020, no. 3, pp. 327–361, 2020. doi: 10.13154/tosc.v2020.i3.327-361