Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Herding Hash Functions and the Nostradamus Attack

Published

Author(s)

John M. Kelsey, Tadayoshi Kohno

Abstract

In this paper, we develop a new attack on Damgaard-Merkle hash functions, called the herding attack, in which an attacker who can find many collisions on the hash function by brute force can first provide the hash of message, and later ''herd'' any given starting part of a message to that hash value by the choice of an appropriate suffix. We focus on a property which hash functions should have--Chosen Target Forced Prefix (CTFP) preimage resistance--and show the distinction between Damgaard-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.
Conference Location
, USA
Conference Title
Eurocrypt 2006

Keywords

collision, cryptanalysis, Damgard-Merkle, hash function, SHA

Citation

Kelsey, J. and Kohno, T. (2006), Herding Hash Functions and the Nostradamus Attack, Eurocrypt 2006, , USA, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=150629 (Accessed May 23, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created May 27, 2006, Updated October 12, 2021