Paper 2025/158

Optimizing Key Recovery in Impossible Cryptanalysis and Its Automated Tool

Jianing Zhang, Shanghai Jiao Tong University
Haoyang Wang, Shanghai Jiao Tong University
Abstract

Impossible differential (ID) cryptanalysis and impossible boomerang (IB) cryptanalysis are two methods of impossible cryptanalysis against block ciphers. Since the seminal work introduced by Boura et al. in 2014, there have been no substantial advancements in the key recovery process for impossible cryptanalysis, particularly for the IB attack.In this paper, we propose a generic key recovery framework for impossible cryptanalysis that supports arbitrary key-guessing strategies, enabling optimal key recovery attacks. Within the framework, we provide a formal analysis of probabilistic extensions in impossible cryptanalysis for the first time. Besides, for the construction of IB distinguishers, we propose a new method for finding contradictions in multiple rounds. By incorporating these techniques, we propose an Mixed-Integer Linear Programming (MILP)-based tool for finding full ID and IB attacks. To demonstrate the power of our methods, we applied it to several block ciphers, including SKINNY, SKINNYee, Midori, and Deoxys-BC. Our approach yields a series of optimal results in impossible cryptanalysis, achieving significant improvements in time and memory complexities. Notably, our IB attack on SKINNYee is the first 30-round attack.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Impossible differential cryptanalysisImpossible boomerang cryptanalysisKey recoverySKINNYSKINNYeeMidoriDeoxys-BC
Contact author(s)
zhangjn @ sjtu edu cn
haoyang wang @ sjtu edu cn
History
2025-02-11: revised
2025-02-02: received
See all versions
Short URL
https://ia.cr/2025/158
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/158,
      author = {Jianing Zhang and Haoyang Wang},
      title = {Optimizing Key Recovery in Impossible Cryptanalysis and Its Automated Tool},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/158},
      year = {2025},
      url = {https://eprint.iacr.org/2025/158}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.