Preimage attack

In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its 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 y, it is difficult to find an x such that h(x) = y.[1]
  • second-preimage resistance: for a specified input, it is computationally infeasible to find another input which produces the same output; i.e., given x, it is difficult to find a second input x′ ≠ x such that h(x) = h(x′).[1]

These can be compared with a collision resistance, in which it is computationally infeasible to find any two distinct inputs x, x′ that hash to the same output; i.e., such that h(x) = h(x′).[1]

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.[1] Conversely, a second-preimage attack implies a collision attack (trivially, since, in addition to x′, x is already known right from the start).

  1. ^ a b c d Rogaway, P.; Shrimpton, T. (2004). "Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance" (PDF). Fast Software Encryption. Lecture Notes in Computer Science. Vol. 3017. Springer-Verlag. pp. 371–388. doi:10.1007/978-3-540-25937-4_24. ISBN 978-3-540-22171-5. Retrieved 17 November 2012.