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:
- simple truncated differential attacks2Cryptanalysis of Grindahl ,
- rebound attacks3The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl,4Improved Cryptanalysis of the Reduced Grøstl Compression Function, ECHO Permutation and AES ,
- ‘start from the middle’ attacks4Improved Cryptanalysis of the Reduced Grøstl Compression Function, ECHO Permutation and AES,5Improved Differential Attacks for ECHO and Grøstl ,
- super S-box attacks6Super-Sbox Cryptanalysis: Improved Attacks for AES-like Permutations,7Rebound Distinguishers: Results on the Full Whirlpool Compression Function,5Improved Differential Attacks for ECHO and Grøstl,8Low Complexity Distinguisher for ECHO-Permutation ,
- multiple rebounds attack9Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function,13Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function.
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].
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
- [1] Truncated and Higher Order Differentials, by Knudsen
- [2] Cryptanalysis of Grindahl, by Peyrin
- [3]
The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl,
by Mendel, Rechberger, Schläffer, and Thomsen - [4]
Improved Cryptanalysis of the Reduced Grøstl Compression Function, ECHO Permutation and AES,
by Mendel, Peyrin, Rechberger, and Schläffer - [5] Improved Differential Attacks for ECHO and Grøstl, by Peyrin
- [6] Super-Sbox Cryptanalysis: Improved Attacks for AES-like Permutations, by Gilbert and Peyrin
- [7]
Rebound Distinguishers: Results on the Full Whirlpool Compression Function,
by Lamberger, Mendel, Rechberger, Rijmen, and Schläffer - [8] Low Complexity Distinguisher for ECHO-Permutation, by Sasaki, Li, Wang, Sakiyama, and Ohta
- [9] Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function, by Schläffer
- [10] A Framework for Iterative Hash Functions – HAIFA, by Biham and Dunkelman
- [11] A Framework for Iterative Hash Functions: HAIFA, by Biham and Dunkelman
- [12] Private communication (June 2010), with Ideguchi and Tischhauser
- [13] Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function, by Jean and Fouque