In the context an of hash functions we have three required properties.

  1. Preimage resistance
  2. Second preimage resistance
  3. Collision resistance.

The bounds for Pre image collision is $O(2^{n-1})$, the bounds for collision resistance is $2^{n/2}$, what are the bounds for breaking second preimage resistance?


1 Answer 1


The right terminology is second preimage resistance and preimage resistance.

Edited to reflect comment by otus. Preimage attack takes $O(2^{n})$ hash function calls on average.

Second preimage attack takes just one extra call so the complexity is essentially the same as that of the preimage attack. Given $x$ you want $x'\neq x$ such that $H(x)=H(x').$ So evaluate $H(x)$ for one extra query, and then apply the preimage attack to $y=H(x).$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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