You are looking at a specific version 20050301:211730 of this paper. See the latest version.

Paper 2004/062

On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions

John Black and Martin Cochran and Thomas Shrimpton

Abstract

Fix a small, non-empty set of blockcipher keys K. We say a blockcipher-based hash function is "highly-efficient" if it makes exactly one blockcipher call for each message block hashed, and all blockcipher calls use a key from K. Although a few highly-efficient constructions have been proposed, no one has been able to prove their security. In this paper we prove, in the ideal-cipher model, that it is impossible to construct a highly-efficient iterated blockcipher-based hash function that is provably secure. Our result implies, in particular, that the Tweakable Chain Hash (TCH) construction suggested by Liskov, Rivest, and Wagner is not correct under an instantiation suggested for this construction, nor can TCH be correctly instantiated by any other efficient means.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
hash functionstweakable block ciphers
Contact author(s)
jrblack @ cs colorado edu
History
2005-03-01: last of 5 revisions
2004-02-26: received
See all versions
Short URL
https://ia.cr/2004/062
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.