What to Guess in Key-Recovery Attacks?

Tim Beyne; Gregor Leander; Patrick Neumann; Yevhen Perehuda; Michiel Verbauwhede

Paper 2026/1897

What to Guess in Key-Recovery Attacks?

Tim Beyne

, KU Leuven

Gregor Leander

, Ruhr University Bochum

Patrick Neumann

, Inria Paris

Yevhen Perehuda, Ruhr University Bochum

Michiel Verbauwhede

, KU Leuven

Abstract

Determining the precise parts of the key that need to be guessed in a key-recovery attack is fundamental for judging its cost: if the same attack can be executed by guessing less key material, then the cipher's resistance against this attack is overestimated. Although a multitude of prior works provide upper bounds on the key material required, and although these bounds might be tight in some special cases, a precise evaluation of the required key material and the tightness of these bounds is still missing. We remedy this by enumerating linear trails to iteratively compute the affine hull of the support of the Fourier transform of the key-recovery map. This leads to a generic and practical algorithm that identifies the smallest subspace of key material to be guessed. This algorithm is ready to be used in many different attacks and for a large variety of cipher structures. We demonstrate its impact by showcasing improvements on several published integral, linear, differential-linear, and zero-correlation attacks on the block ciphers PRESENT, SIMON, SKINNY, and GIFT.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Keywords: symmetric key key dependencies linear trails PRESENT SIMON SKINNY GIFT
Contact author(s): tim beyne @ esat kuleuven be
gregor leander @ rub de
patrick neumann @ inria fr
yevhen perehuda @ rub de
michiel verbauwhede @ kuleuven be
History: 2026-09-10: approved; 2026-09-05: received; See all versions
Short URL: https://ia.cr/2026/1897
License: CC BY

BibTeX

@misc{cryptoeprint:2026/1897,
      author = {Tim Beyne and Gregor Leander and Patrick Neumann and Yevhen Perehuda and Michiel Verbauwhede},
      title = {What to Guess in Key-Recovery Attacks?},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1897},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1897}
}