ECHO hash function home design security hard soft compare

Taking advantage of the simplicity and clarity of AES-like design techniques, various analyses using truncated differentials [1Truncated and Higher Order Differentials] have recently been conducted. These are particularly relevant to hash functions using AES-like techniques and it is interesting to note that the results can be divided into five distinct types:

The first type was already considered during the design phase of ECHO. The second and third types of analysis, rebound attacks and start-from-the-middle attacks, were applied to ECHO [4Improved Cryptanalysis of the Reduced Grøstl Compression Function, ECHO Permutation and AES]. However, an inconsistency was pointed out with respect to the utilization of this technique for ECHO [12Private communication (June 2010)]. The fourth and fifth types of attacks are probably the most currently effective when analyzing the security of the ECHO compression function.

the hash function

Work by M. Schläffer [9Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function] claimed an attack on a 4-round reduced version of the ECHO hash function with respect to collision resistance. J. Jean and P.-A. Fouque [13Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function] however showed that the method exposed in [9Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function] is flawed in the final merging phase of the attack (with the consequence that the attack only works with probability 2-128).

the compression function

The best semi-free-start collision attacks can not reach more than only 4 rounds. Similarly, distinguishers for the compression function of ECHO-SP-256, ECHO-SP-512, and ECHO-256 are limited to 4 rounds, and distinguishers for ECHO-512 to 6 rounds. As in the case of the hash function, Schläffer's analysis [9Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function] on the ECHO compression function suffers from issues highlighted in [13Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function].

version rounds complexity memory type ref.
compression function
ECHO, 256 bits
4/8 252 216 semi-free-start collision [13Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function]
4.5/8 296 232 distinguisher [5Improved Differential Attacks for ECHO and Grøstl]
compression function
simple pipe, 256 bits
4/8 252 216 semi-free-start collision [13Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function]
4/8 252 216 distinguisher [13Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function]
compression function
ECHO, 512 bits
4/10 252 216 semi-free-start collision [13Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function]
6.5/10 296 232 distinguisher [5Improved Differential Attacks for ECHO and Grøstl]
compression function
simple pipe, 512 bits
4/10 252 216 semi-free-start collision [13Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function]
4.5/10 296 232 distinguisher [5Improved Differential Attacks for ECHO and Grøstl]

the internal permutation

It is interesting to note that the full number of rounds in the internal permutation can be “reached” with the super S-box analysis. However, when designing ECHO the goal was not to build a seemingly-ideal 2048-bit permutation, but rather to build a secure 256-bit or 512-bit hash function. For instance, distinguishers for the internal permutation reduced to 7 rounds were already described in the package submitted to the NIST. The large internal permutation is an important component of the compression function, but so is the final convolution that provides a major contribution to the diffusion in ECHO. As a consequence, it is important to analyse the compression function in its entirety rather than to consider the internal permutation in isolation. Indeed, this is the appropriate position since the attendant proofs of security for the operational mode of a hash function require indistinguishability of the compression function.

version rounds complexity memory type ref.
internal permutation
ECHO
7 2118 238 distinguisher [8Low Complexity Distinguisher for ECHO-Permutation]
8 2182 237 distinguisher [8Low Complexity Distinguisher for ECHO-Permutation]

references