Automatic Search Model for Related-Tweakey Impossible Differential Cryptanalysis

Huiqin Chen; Yongqiang Li; Xichao Hu; Zhengbin Liu; Lin Jiao; Mingsheng Wang

Paper 2023/1353

Automatic Search Model for Related-Tweakey Impossible Differential Cryptanalysis

Huiqin Chen, Institute of Information Engineering, Chinese Academy of Science, Beijing, China

Yongqiang Li, Institute of Information Engineering, Chinese Academy of Science, Beijing, China

Xichao Hu, Institute of Information Engineering, Chinese Academy of Science, Beijing, China

Zhengbin Liu, Science and Technology on Communication Security Laboratory, Chengdu, China

Lin Jiao, State Key Laboratory of Cryptology, Beijing, China

Mingsheng Wang, Institute of Information Engineering, Chinese Academy of Science, Beijing, China

Abstract

The design and analysis of dedicated tweakable block ciphers constitute a dynamic and relatively recent research field in symmetric cryptanalysis. The assessment of security in the related-tweakey model is of utmost importance owing to the existence of a public tweak. This paper proposes an automatic search model for identifying related-tweakey impossible differentials based on the propagation of states under specific constraints, which is inspired by the research of Hu et al. in ASIACRYPT 2020. Our model is universally applicable to block ciphers, but its search efficiency may be limited in some cases. To address this issue, we introduce the Locality Constraint Analysis (LCA) technique to impossible differential cryptanalysis and propose a generalized automatic search model. Technically, we transform our models into Satisfiability Modulo Theories (SMT) problems and solve them using the STP solver. We have applied our tools to several tweakable block ciphers, such as Joltik-BC, SKINNY, QARMA, and CRAFT, to evaluate their effectiveness and practicality. Specifically, we have discovered 7-round related-tweakey impossible differentials for Joltik-BC-192, and 12-round related-tweak impossible differentials, as well as 15-round related-tweakey impossible differentials for CRAFT for the first time. Based on the search results, we demonstrate that the LCA technique can be effectively performed when searching and determining the contradictory positions for the distinguisher with long trails or ciphers with large sizes in impossible differential cryptanalysis.

Note: The full version of the paper which was published in ADSC 2023.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Minor revision. ACNS 2023 Workshops
DOI: https://doi.org/10.1007/978-3-031-41181-6_1
Keywords: Tweakable Block Cipher Related-tweakey Impossible differential cryptanalysis LCA technique SAT method
Contact author(s): chenhuiqin @ iie ac cn
liyongqiang @ iie ac cn
huxichao @ iie ac cn
zhengbinliu @ 126 com
jiaolin_jl @ 126 com
wangmingsheng @ iie ac cn
History: 2023-09-11: approved; 2023-09-11: received; See all versions
Short URL: https://ia.cr/2023/1353
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1353,
      author = {Huiqin Chen and Yongqiang Li and Xichao Hu and Zhengbin Liu and Lin Jiao and Mingsheng Wang},
      title = {Automatic Search Model for Related-Tweakey Impossible Differential Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1353},
      year = {2023},
      doi = {https://doi.org/10.1007/978-3-031-41181-6_1},
      note = {\url{https://eprint.iacr.org/2023/1353}},
      url = {https://eprint.iacr.org/2023/1353}
}