# Complexity of preimage resistance

Why is the complexity of pre-image resistance $2$ raised to the power of $n$? I have been looking in everything lecture about pre-image resistance, but I still didn't know the answer.

• What is "2 square by n"? $\;$ – user991 Nov 3 '14 at 9:04
• I would say $2^n$. – ddddavidee Nov 3 '14 at 9:24

When the output of the hash function is $n$ bits, then there are $2^n$ possible outputs.
For a preimage attack you are given a hash $h$ and you need to find a message $m$ where $h = H(m)$.
Since there are $2^n$ possible outputs, the probability of guessing an input that that maps to the given output is $\dfrac{1}{2^n}$. So on average you need to try $2^n$ preimages. That is where the $2^n$ complexity comes from.