Paper 2005/281
Herding Hash Functions and the Nostradamus Attack
John Kelsey and Tadayoshi Kohno
Abstract
In this paper, we develop a new attack on Damgå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å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
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- hash functionsdigital timestampingcollision resistanceDamgaard-Merkle
- Contact author(s)
- john kelsey @ nist gov
- History
- 2006-02-18: revised
- 2005-08-25: received
- See all versions
- Short URL
- https://ia.cr/2005/281
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2005/281,
author = {John Kelsey and Tadayoshi Kohno},
title = {Herding Hash Functions and the Nostradamus Attack},
howpublished = {Cryptology {ePrint} Archive, Paper 2005/281},
year = {2005},
url = {https://eprint.iacr.org/2005/281}
}
