Linear Propagation in Efficient Guess-and-Determine Attacks

The most successful attacks on cryptographic hash functions are based
on differential cryptanalysis, where the main problem is to find a differential char-
acteristic. Finding a differential characteristic is equivalent to solving a system
of nonlinear equations. Solving these equations is usually done by a guess-and-
determine approach. Recently, automated tools performing a guess-and-determine
approach based on the concept of generalized conditions have been used to attack
many hash functions. The core part of such tools is the propagation of informa-
tion. In this paper, we propose a new approach to propagate information for affine
functions and compare it to the approach used in recent hash function attacks.
We apply our method to the linear functions σi and Σi used in SHA-2 and to the
linear layer of SHA-3. We show that our approach performs much better than the
previously used methods.