International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
John Black
Martin Cochran
Thomas Shrimpton
Download:
URL: http://eprint.iacr.org/2004/062
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2004-12036,
  title={On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions},
  booktitle={IACR Eprint archive},
  keywords={foundations / hash functions, tweakable block ciphers},
  url={http://eprint.iacr.org/2004/062},
  note={ jrblack@cs.colorado.edu 12843 received 24 Feb 2004, last revised 1 Mar 2005},
  author={John Black and Martin Cochran and Thomas Shrimpton},
  year=2004
}