Christof Beierle
Ruhr University Bochum

Gregor Leander
Ruhr University Bochum

Yevhen Perehuda
Ruhr University Bochum

Keywords: block ciphers, integral attacks, key recovery, wrong-key randomization, linear structures

Abstract

An integral distinguisher for a block cipher is defined by a nontrivial subset of plaintexts for which the bitwise sum of (parts of) a certain internal state is independent of the secret key. Such a distinguishing property can be turned into a key-recovery procedure by partially decrypting the ciphertexts under all possible keys and then filtering the key candidates using the integral distinguisher. The behavior of this filter has never been analyzed in depth, and we show that the ubiquitous hypothesis about its behavior is incorrect.

Fortunately, the deviation is either limited or can be lifted to improve the underlying attacks. By algorithmically determining the exact subspaces of key candidates to be guessed -- whose dimensions are often lower than expected -- we are able to improve upon the best known integral key-recovery attacks on various ciphers.