What to Guess in Key-Recovery Attacks?

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.

Joint work with Tim Beyne, Gregor Leander, Yevhen Perehuda, Michiel Verbauwhede

ePrint