Collision Attacks against the Knudsen-Preneel Compression Functions

详细信息    查看全文

• 作者：Onur ?zen ; Martijn Stam
• 关键词：Collision attack ; coding theory ; compression function
• 刊名：Lecture Notes in Computer Science
• 出版年：2010
• 出版时间：2010
• 年：2010
• 卷：6477
• 期：1
• 页码：76-93
• 全文大小：338.1 KB

文摘

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 ?zen, Shrimpton, and Stam (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.