2
$\begingroup$

Are there any successful preimage attacks on any serious cryptographic hash algorithm or at least on serious-looking non-cryptographic hashes (like MurmurHash)?

$\endgroup$
  • 1
    $\begingroup$ I believe that generating preimages for MurmurHash is actually pretty trivial... $\endgroup$ – poncho Jan 20 '16 at 22:43
  • 1
    $\begingroup$ Maraca had a pretty catastrophic preimage attack. On the more theoretical side, MD2, MD4, and Snefru have known preimage attacks. $\endgroup$ – Samuel Neves Jan 21 '16 at 10:23
5
$\begingroup$

MD4 is Not One-Way. The attack described in the 2008 paper is a theoretical attack with complexity $2^{102}$, which is better than the brute force complexity of $2^{128}$. In later theoretical results reported here the complexity dropped to $2^{94.98}$ and here it dropped even further to $2^{69.4}$ for secondary pre-image attacks.

Similarly, The MD2 Hash Function is not One-Way as reported in a 2004 paper, where the complexity of finding pre-images was reported to be $2^{104}$, compared to the brute force complexity of $2^{128}$. The attack was improved in 2008 to a complexity of $2^{73}$.

Other examples include draft algorithms that are broken during the initial design phase or peer-review phase, such as the SHA-3 submission Maraca.

Non-cryptographic hashes, such as MurmurHash, are usually not designed to be one-way. In order for something to qualify as a proper "attack", it has to do better than anticipated given the security claims. If there are no security claims, there can't really be any attacks either. And of course, if there are no security claims, the algorithm should obviously not be used for cryptographic purposes.

A helpful hint might be to only use algorithms that are published, have security claims, and always search for papers that mention the algorithm name here https://eprint.iacr.org/search.html before using it for production purposes. Practical attacks are almost always preceded by theoretical attacks, and theoretical attacks are often (almost always?) published somewhere. This doesn't, however, apply to every proprietary algorithm on the Internet, and also not to algorithms that are not designed for cryptographic purposes to begin with.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.