TY - JOUR

T1 - Cryptanalysis of an Iterated Halving-based hash function: CRUSH

A1 - Bagheri,Nasour

A1 - Henricksen,Matt

A1 - Knudsen,Lars Ramkilde

A1 - Naderi,M

A1 - Sadeghyian,B

AU - Bagheri,Nasour

AU - Henricksen,Matt

AU - Knudsen,Lars Ramkilde

AU - Naderi,M

AU - Sadeghyian,B

PB - The/Institution of Engineering and Technology

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

U2 - 10.1049/iet-ifs.2009.0055

DO - 10.1049/iet-ifs.2009.0055

JO - I E T Information Security

JF - I E T Information Security

SN - 1751-8709

IS - 4

VL - 3

SP - 129

EP - 138

ER -