Collision Attacks against the Knudsen-Preneel Compression Functions

Knudsen and Preneel (Asiacrypt'96 and Crypto'97) introduced a hash function design in which a linear error-correcting code is used to build a wide-pipe compression function from underlying blockciphers operating in Davies-Meyer mode. Their main design goal was to deliver compression functions with collision resistance up to, and even beyond, the block size of the underlying blockciphers. In this paper, we present new collision-finding attacks against these compression functions using the ideas of an unpublished work of Watanabe and the preimage attack of Ozen, Shrimpton, and Stain (FSE'10). In brief, our best attack has a time complexity strictly smaller than the block-size for all but two of the parameter sets. Consequently, the time complexity lower bound proven by Knudsen and Preneel is incorrect and the compression functions do not achieve the security level they were designed for.

Published in:
Advances In Cryptology - Asiacrypt 2010, 6477, 76-93
Presented at:
16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, SINGAPORE, Dec 05-09, 2010
Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa

 Record created 2011-12-16, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)