Linear Propagation in Efficient Guess-and-Determine Attacks
Maria Eichlseder, Florian Mendel, Tomislav Nad, Vincent Rijmen, Martin Schlaeffer · 2013
The most successful attacks on cryptographic hash functions are based on differential cryptanalysis, where the main problem is to find a differential characteristic. Finding a differential characteristic is equivalent to solving a system of nonlinear equations. Solving these equations is usually done by a guess-anddetermine 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 information. 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.