Herding Hash Functions and the Nostradamus Attack

Published

May 28, 2006

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

Pub Type

Conferences

Download Paper

Local Download

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 December 11, 2024)