In this paper, we develop a new attack on Damg°ard-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 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°ard-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 inarguably 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.
%0 Journal Article
%1 noauthororeditor
%A Kelsey, John
%A Kohno, Tadayoshi
%D 2006
%K cryptography hashfunctions
%T Herding Hash Functions and the Nostradamus Attack
%X In this paper, we develop a new attack on Damg°ard-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 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°ard-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 inarguably 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.
@article{noauthororeditor,
abstract = {In this paper, we develop a new attack on Damg°ard-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 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°ard-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 inarguably 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.},
added-at = {2018-09-21T12:08:00.000+0200},
author = {Kelsey, John and Kohno, Tadayoshi},
biburl = {https://www.bibsonomy.org/bibtex/271b1d480594a87c6687961b8843a5ce5/overleaf},
interhash = {342c8327bc04ce45c25cdc3cd504ec95},
intrahash = {71b1d480594a87c6687961b8843a5ce5},
keywords = {cryptography hashfunctions},
language = {English},
timestamp = {2018-09-21T12:08:00.000+0200},
title = {Herding Hash Functions and the Nostradamus Attack},
year = 2006
}