Editing Preimage attack (section)

{{short description|Attack model against cryptographic hash functions}}
In [[cryptography]], a '''preimage attack'''  on [[cryptographic hash function]]s tries to find a [[Message#In computer science|message]] that has a specific hash value. A cryptographic hash function should resist attacks on its [[Preimage#Inverse image|preimage]] (set of possible inputs).

In the context of attack, there are two types of preimage resistance:

* ''preimage resistance'': for essentially all pre-specified outputs, it is computationally infeasible to find any input that hashes to that output; i.e., given {{math|{{var|y}}}}, it is difficult to find an {{math|{{var|x}}}} such that {{math|1={{var|h}}({{var|x}}) = {{var|y}}}}.<ref name="crypto-hash-def">{{cite book
| last1= Rogaway
| first1= P.
| last2= Shrimpton
| first2= T.
| title= Fast Software Encryption
| chapter= Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance
| series= Lecture Notes in Computer Science
| year=2004
| volume= 3017
| pages= 371–388
| publisher= Springer-Verlag
| doi= 10.1007/978-3-540-25937-4_24
| isbn= 978-3-540-22171-5
| chapter-url= https://web.cs.ucdavis.edu/~rogaway/papers/relates.pdf
| access-date=17 November 2012}}</ref>
* ''second-preimage resistance'': for a specified input, it is computationally infeasible to find another input which produces the same output; i.e., given {{math|{{var|x}}}}, it is difficult to find a second input {{math|{{var|x}}′ ≠ {{var|x}}}} such that {{math|1={{var|h}}({{var|x}}) = {{var|h}}({{var|x}}′)}}.<ref name="crypto-hash-def" />

These can be compared with a [[collision resistance]], in which it is computationally infeasible to find any two distinct inputs {{math|{{var|x}}}}, {{math|{{var|x}}′}} that hash to the same output; i.e., such that {{math|1={{var|h}}({{var|x}}) = {{var|h}}({{var|x}}′)}}.<ref name="crypto-hash-def" />

Collision resistance implies second-preimage resistance. Second-preimage resistance implies preimage resistance only if the size of the hash function's inputs can be substantially (e.g., factor 2) larger than the size of the hash function's outputs.<ref name="crypto-hash-def" /> Conversely, a second-preimage attack implies a collision attack (trivially, since, in addition to {{math|{{var|x}}′}}, {{math|{{var|x}}}} is already known right from the start).