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

John Black, 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.

Note: This version fixes an error in the main proof of the paper published in Eurocrypt '05. That version incorrectly assumed that MD-strengthening does not affect the attack when more than one blockcipher key is used.

Available format(s)
Publication info
Published elsewhere. Previously appeared in the proceedings of Eurocrypt '05
Keywords
blockciphershash functions
Contact author(s)
History
Short URL
https://ia.cr/2007/223

CC BY

BibTeX

@misc{cryptoeprint:2007/223,
author = {John Black and Martin Cochran and Thomas Shrimpton},
title = {On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions},
howpublished = {Cryptology ePrint Archive, Paper 2007/223},
year = {2007},
note = {\url{https://eprint.iacr.org/2007/223}},
url = {https://eprint.iacr.org/2007/223}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.