Talk:Collision resistance

Cryptography: Computer science High‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
High	This article has been rated as High-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as High-importance).

Untitled[edit]

It should also be mentioned that hard problems in the context of Cryptography are distinct from NP-complete hard problems in Analysis. The latter is only difficult in the worst case, while the former needs to be hard in the average or best case. I don't think either problem has been shown to be NP-Complete, and this would be surprising if it was true. — Preceding unsigned comment added by 167.24.104.150 (talk) 14:57, 1 July 2013 (UTC)[reply]

Rewrote to be a bit more accurate. Could use a writeup (with examples) of why collision resistance is desirable. -- Victor Lighthill 07:13, 1 May 2006 (UTC)[reply]

Collision resistance vs pre-image attack resistance[edit]

Most arguments for the desirability of collision resistance in this article are actually arguments for pre-image attack resistance. Just because a collision can be manufactured doesn't mean a pre-image attack is feasible. Right? ~~Jae — Preceding unsigned comment added by 50.0.248.163 (talk) 01:22, 6 September 2013 (UTC)[reply]

While a pre-image attack can be more severe than a collision attack, all examples given on the page require collision resistance in some cases: (1) If a digital signature does not use a collision resistant hash function then an attacker would find two messages, one which the signer is willing to sign, ask for the signature of this message and claim it is a signature for the second message. (2) The first step in a proof-of-work system typically is to hash the message for which the sender wants to generate a proof of work. If this hash allows collisions then an attacker can cut his cost for the proof by first generating multiple messages with the same hash. Not sure if there are other places where these schemes rely on collision resistance. (3) If a file system is based on a hash that is not pre-image resistant then an attacker can replace a existing files with new ones. If the hash is pre-image resistant but not collision resistant then this attack does indeed not work and the attack becomes more difficult. However, the attacker can still try to generate two files with the same hash, one which passes reviews and can be checked in, and another one with malicious content, which can then be replaced for the first one. Hence file systems that depend on hashes for integrity checking require collision resistance. 2A02:1205:C6BB:6880:C929:B6B8:1D82:A1F7 (talk) 11:52, 7 September 2013 (UTC)[reply]