[Resource Topic] 2005/281: Herding Hash Functions and the Nostradamus Attack

Welcome to the resource topic for 2005/281

Herding Hash Functions and the Nostradamus Attack

Authors: John Kelsey, Tadayoshi Kohno


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

ePrint: https://eprint.iacr.org/2005/281

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .