Iterated Halving has been suggested as a replacement to the Merkle–Damgård (MD) construction in 2004 anticipating the attacks on the MDx family of hash functions. The CRUSH hash function provides a specific instantiation of the block cipher for Iterated Halving. The authors identify structural problems with the scheme and show that they can trivially identify collisions and second preimages on many equal-length messages of length ten blocks or more. The cost is ten decryptions of the block cipher, this being less than the generation of a single digest. In addition, these attacks can be used to differentiate CRUSH from a random oracle in O(1). The authors show that the complexity of finding a preimage in the unpadded CRUSH with the length encoding is negligible and extend this attack on CRUSH with the length encoding in cost O(232). This attack is a multi-preimage attack, since the attacker can produce a large number of messages for a given message digest for the cost of O(232). Hence, this attack can be used as a multi-collision and a multi-second-preimage as well. They show that if the attacker knows the last 64-bits of the message digest in advance, he can do the time-consuming part of the attack off-line. The authors show that even if Iterated Halving is repaired, the construction has practical issues that means it is not suitable for general deployment.

This paper considers iterated hash functions. It proposes new constructions of fast and secure compression functions with nl-bit outputs for integers n>1 based on error-correcting codes and secure compression functions with l-bit outputs. This leads to simple and practical hash function constructions based on block ciphers such as the Data Encryption Standard (DES), where the key size is slightly smaller than the block size; IDEA, where the key size is twice the block size; Advanced Encryption Standard (AES), with a variable key size; and to MD4-like hash functions. Under reasonable assumptions about the underlying compression function and/or block cipher, it is proved that the new hash functions are collision resistant. More precisely, a lower bound is shown on the number of operations to find a collision as a function of the strength of the underlying compression function. Moreover, some new attacks are presented that essentially match the presented lower bounds. The constructions allow for a large degree of internal parallelism. The limits of this approach are studied in relation to bounds derived in coding theory.

Key recovery systems suitable for application among multiple domains, such as those operating within international communication networks, are investigated. A general framework for analysis of key recovery systems is introduced and a set of parameter