CryptoDB
Herding Hash Functions and the Nostradamus Attack
| Authors: | |
|---|---|
| Download: | |
| Abstract: | In this paper, we develop a new attack on Damg{\aa}rd-Merkle hash functions, called the \emph{herding attack}, in which an attacker who can find many collisions on the hash function by brute force can first provide the hash of a message, and later ``herd'' any given starting part of a message to that hash value by the choice of an appropriate suffix. We introduce a new property which hash functions should have--Chosen Target Forced Prefix (CTFP) preimage resistance--and show the distinction between Damg{\aa}rd-Merkle construction hashes and random oracles with respect to this property. We describe a number of ways that violation of this property can be used in arguably practical attacks on real-world applications of hash functions. An important lesson from these results is that hash functions susceptible to collision-finding attacks, especially brute-force collision-finding attacks, cannot in general be used to prove knowledge of a secret value |
BibTeX
@misc{eprint-2005-12615,
title={Herding Hash Functions and the Nostradamus Attack},
booktitle={IACR Eprint archive},
keywords={secret-key cryptography / hash functions, digital timestamping, collision resistance, Damgaard-Merkle},
url={http://eprint.iacr.org/2005/281},
note={ john.kelsey@nist.gov 13197 received 22 Aug 2005, last revised 18 Feb 2006},
author={John Kelsey and Tadayoshi Kohno},
year=2005
}