Paper 2025/158
Optimizing Key Recovery in Impossible Cryptanalysis and Its Automated Tool
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
-
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} }