Attacking the Knudsen-Preneel Compression Functions

Onur Özen, T. Shrimpton, M Stam

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

4 Citations (Scopus)


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. In this paper, we (re)analyse the preimage resistance of the Knudsen-Preneel compression functions in the setting of public random functions. We give a new non-adaptive preimage attack, beating the one given by Knudsen and Preneel, that is optimal in terms of query complexity. Moreover, our new attack falsifies their (conjectured) preimage resistance security bound and shows that intuitive bounds based on the number of ‘active’ components can be treacherous. Complementing our attack is a formal analysis of the query complexity (both lower and upper bounds) of preimage-finding attacks. This analysis shows that for many concrete codes the time complexity of our attack is optimal.
Translated title of the contributionAttacking the Knudsen-Preneel Compression Functions
Original languageEnglish
Title of host publicationFast Software Encryption - FSE 2010
PublisherSpringer Berlin Heidelberg
Pages94 - 115
Publication statusPublished - 2010

Bibliographical note

Conference Organiser: FSE 2010

Fingerprint Dive into the research topics of 'Attacking the Knudsen-Preneel Compression Functions'. Together they form a unique fingerprint.

Cite this