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


Published in:
Fast Software Encryption, 6147, 94-115
Presented at:
17th International Workshop on Fast Software Encryption, Seoul, SOUTH KOREA, Feb 07-10, 2010
Year:
2010
Publisher:
Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa
ISBN:
978-3-642-13857-7
Keywords:
Laboratories:




 Record created 2011-12-16, last modified 2018-01-28


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)