Talk:Preimage attack

Removed CRC

Removed this:

For example, there is a program called CRC Faker that will generate a file of a user-defined size with the CRC requested.

Because CRC is not a cryptographic hash. It's only good for error detection; compromising data integrity is (almost) trivial. This cannot really be called a preimage attack unless you're stupid enough to use CRC for integrity checking—OTOH, many people are indeed stupid enough to do that, so maybe it should be mentioned with qualification... 82.92.119.11 22:04, 11 January 2006 (UTC)

Difficulty of first vs. second preimage attack

I do not agree with the following statement in the article:

Due to the similarity between these two cases a method for attacking one can normally be applied to attacking the other.

RFC 4270, which is given as reference, makes such a claim but gives no explanation for the claim. A well known example for a second preimage attack was an exploit that allowed to change the boot code of the XBOX (see [1]). The attack there based on the fact that TEA is a bad choice for constructing a hash function. I.e., the hash function used for the XBOX has the property that the hash result does not change if certain bits are changed. This allowed a second preimage attack that could be used change the boot code, so that this change was not detected by the XBOX. It does not seem that this attack can be extended to a first preimage attack. 67.84.116.166 02:39, 12 September 2006 (UTC)

Rewording - Update - Reference

I replaced the second paragraph, since the wording of the paragraph can be confusing. It might infer that a hash function to which finding a preimage attack takes in the order of 2n operations is vulnerable and not good. I was especially worried when the page on cryptographic hash functions http://en.wikipedia.org/wiki/Cryptographic_hash_function saying that 'Functions that lack first preimage resistance are vulnerable to first preimage attack'. I wanted to clarify that such complexity applies to even an IDEAL hash function.

I also added some information about the current state of preimage attacks on popular cryptographic hash functions and how they relate to Internet security. I also added a reference on some of these attacks. —Preceding unsigned comment added by 128.237.246.113 (talk) 17:30, 2 September 2009 (UTC)

Random oracle

I added the link to the random oracle in the "see also" section. I am wondering if it should also be mentioned in the text or would it be to confusing to put so much information in the sentence. —Preceding unsigned comment added by 89.75.117.235 (talk) 09:35, 25 May 2010 (UTC)

Does preimage resistance imply collision resistance?

I think the statement "in fact, any hash function which is resistant to first or second preimage attacks is by definition collision-resistant" is not correct or, if it is, it is insufficiently substantiated in text or through reference. The first part of the paragraph also seems to me to contradict this statement: since it is known that MD5 and SHA-1 are not collision resistant, I would expect it to be easy to show how they are also not preimage resistant (because the falsity of the conclusion implies the falsity of the premise). However, the preimage resistance properties of MD5 and SHA-1 are not nearly as badly broken as the collision resistance, therefore it is probably not easy after all to leverage the collision attacks to preimage attacks. 194.203.215.254 (talk) 11:58, 1 October 2010 (UTC)

Thanks! You're right, the Handbook of Applied Cryptography explicitly states "collision resistance does not guarantee preimage resistance". The article was recently changed; It's not clear what the earlier statement meant so I removed it entirely. -- intgr [talk] 18:24, 1 October 2010 (UTC)

Vague

This article is pretty vague about what one would actually do to try an implement this kind of attack. The definition "find a message with a given hash" is basically the statement "break the code" and so doesn't really convey much content. 75.146.224.18 (talk) 17:35, 4 December 2010 (UTC)

It's vague because the "preimage attack" is not a concrete attack, it's basically a classification for hash-function-specific attacks (cryptanalysis) that have the mentioned properties — in contrast to the collision attack. The only "general" way to apply preimage attacks is through brute force. I have changed and hopefully clarified the article. -- intgr [talk] 08:10, 6 December 2010 (UTC)

The claim that brute force is the only general attack against brute force seems a little too strong to me. Couldn't one try a preimage attack using for example a SAT solver? Probably more accurate would be to claim that there is no known generic attack that finds a preimage faster than with $2^{n}$ steps. Stating that none exists seems to imply P != NP. 85.1.150.114 (talk) 20:01, 6 December 2010 (UTC)

Oh that's right, I intended to say that it's the fastest general method (which makes it the only useful method).

This article seems to define "preimage resistance" as "computing preimages for n-bit hash function takes 2ⁿ steps". I always took that definition for granted, but the Handbook of Applied Cryptography merely defines it as "computing preimages is computationally infeasible" (paraphrased). I'll see if I can find any sources for the current (stronger) definition given in the article. -- intgr [talk] 20:37, 7 December 2010 (UTC)

That seems a reasonable approach to me. While an ideal hash function will of course require 2^n steps, in the real world people will attempt to cryptanalyse them. If someone manages to find a way of calculating a preimage of SHA-256 in 2^255 steps, do we declare that SHA-256 is no longer preimage resistant, and that therefore any protocol that relies on preimage resistance must no longer use SHA-256? Of course not, because 2^255 is still large enough to make computing a preimage computationally infeasible. Roy Badami (talk) 12:53, 27 May 2011 (UTC)

This article defines the topic ("preimage attack") as an attempt to "find a message that has a specific hash value." But the article currently does not explain how the ability to find such a message would constitute (or be usable as) an "attack."

The section "Applied preimage attacks" seems by its title to promise just such an explanation, but instead only restates the definition of the term, and does not explain how anything would be attacked, i.e. how an attacker would make use of a practical preimage capability to the detriment of the attacked. The section contains the sentence, "If a practical preimage attack is discovered, it would drastically affect many Internet protocols.", but again, it does not explain how those protocols would be affected. — Preceding unsigned comment added by 140.254.63.5 (talk) 16:28, 24 August 2016 (UTC)

This article needs help

Citations on definitions - Handbook of Applied Cryptography or Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance.

"All currently known practical or almost-practical attacks on MD5 and SHA-1 are collision attacks." - I believe this is wrong, as recently proven by Flame malware signing. Here the attacker started with a h(m) using MD5 (from a Microsoft code signing certificate) and found another message m' such that h(m) = h(m'). The attacker did it via a prefix attack. Flame's attack on the hash were not arbitrary collisions - h(m) was pinned. I believe that makes it second-preimage.

Taking from Rogaway's paper on definitions: "Fact: Collision resistance implies 2nd-preimage resistance of hash functions" and "Note: collision resistance does not guarantee preimage resistance."

Jeffrey Walton 14:57, 19 November 2012 (UTC)

> The attacker did it via a prefix attack

This sounds like wild speculation. "Prefix attack" is probably referring to chosen-prefix collision attack -- which is a form of collision attacks. Although at first glance, it seems a prefix collision attack would be quite complicated to pull off -- harder than simply e.g. stealing or compromising access to the private key.

Extraordinary claims need extraordinary evidence and you haven't presented any. Consider that, so far, the public cryptography community has failed to find practical preimage attacks in *any* cryptographic hash function (see hash function security summary -- though it's possible that this page is missing some attacks). It's simply a lot more likely that some code signing private keys were compromised or leaked from Microsoft. -- intgr [talk] 17:31, 19 November 2012 (UTC)

Brute force time complexity

The article says that "[f]or an n-bit hash, [a brute force] attack has a time complexity 2^n". Wouldn't it be more correct to say it has an average time complexity 2^n? Nothing guarantees that no more than 2^n variations of the input are needed to come up with a hash (though that's the expected average number of variations), except if the hash has an input size of n bits, which as far as I know, none does. I'm asking because I'm not sure if the term "time complexity" implies an average. —pgimeno (talk) 19:25, 24 September 2013 (UTC)

Or maybe what the article means is that the time complexity is O(2^n)? --pgimeno (talk) 19:01, 13 May 2014 (UTC)