Exploiting Non-Full Key Additions: Full-Fledged Automatic Demirci-Selcuk Meet-in-the-Middle Cryptanalysis of SKINNY

Danping Shi; Siwei Sun; Ling Song; Lei Hu; Qianqian Yang

Paper 2023/255

Exploiting Non-Full Key Additions: Full-Fledged Automatic Demirci-Selcuk Meet-in-the-Middle Cryptanalysis of SKINNY

Danping Shi

, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Siwei Sun

, School of Cryptology, University of Chinese Academy of Sciences, Beijing, China,

Ling Song

, Jinan University, Guangzhou, China

Lei Hu

, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Qianqian Yang

, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Abstract

The Demirci-Sel{\c{c}}uk meet-in-the-middle (DS-MITM) attack is a sophisticated variant of differential attacks. Due to its sophistication, it is hard to efficiently find the best DS-MITM attacks on most ciphers \emph{except} for AES. Moreover, the current automatic tools only capture the most basic version of DS-MITM attacks, and the critical techniques developed for enhancing the attacks (e.g., differential enumeration and key-dependent-sieve) still rely on manual work. In this paper, we develop a full-fledged automatic framework integrating all known techniques (differential enumeration, key-dependent-sieve, and key bridging, etc) for the DS-MITM attack that can produce key-recovery attacks directly rather than only search for distinguishers. Moreover, we develop a new technique that is able to exploit partial key additions to generate more linear relations beneficial to the attacks. We apply the framework to the SKINNY family of block ciphers and significantly improved results are obtained. In particular, all known DS-MITM attacks on the respective versions of SKINNY are improved by at least 2 rounds, and the data, memory, or time complexities of some attacks are reduced even compared to previous best attacks penetrating less rounds.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published by the IACR in EUROCRYPT 2023
Keywords: Demirci-Selcuk MITM Attacks Differential Enumeration Key-dependent Sieve SKINNY
Contact author(s): shidanping @ iie ac cn
sunsiwei @ ucas ac cn
songling qs @ gmail com
hulei @ iie ac cn
yangqianqian @ iie ac cn
History: 2023-02-23: revised; 2023-02-22: received; See all versions
Short URL: https://ia.cr/2023/255
License: CC BY

BibTeX

@misc{cryptoeprint:2023/255,
      author = {Danping Shi and Siwei Sun and Ling Song and Lei Hu and Qianqian Yang},
      title = {Exploiting Non-Full Key Additions: Full-Fledged Automatic Demirci-Selcuk Meet-in-the-Middle Cryptanalysis of {SKINNY}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/255},
      year = {2023},
      url = {https://eprint.iacr.org/2023/255}
}