How can a preimage attack on SHA-256 always succeed within 2^256 evaluations when done though brute force?

Question

I was reading the Wikipedia page for SHA-256 (SHA-2) and came across the following statement:

For a hash function for which $L$ is the number of bits in the message digest, finding a message that corresponds to a given message digest can always be done using a brute force search in $2^L$ evaluations.

Why is this true? Is it some property of SHA-256 or am I missing something? I know that there must be a collision within $2^{256} + 1$ unique inputs, but I don't see why this would mean that there must be a specified digest from some list of unique inputs of length $2^{256} + 1$.

Answer 1

This is a lazy expression on the part of the writer. You are correct that if SHA256 is a well-constructed hash function (and we believe that it is) then trying $2^L$ inputs is likely to produce a preimage, but not certain to do so. To be precise if we have $2^L$ distinct inputs, we expect the probability of finding a pre-image to be $$1-\left(1-\frac 1{2^L}\right)^{2^L}\approx 1-\frac1e.$$ More generally the probability distribution $n$, on the number of guesses needed to succeed is given by $$\mathbb P({\rm guesses}\le n)=1-\left(1-\frac 1{2^L}\right)^{n}$$ so that the expected number of guesses is $2^L$.

It is often useful for "back-of-the-envelope" calculations to approximate the distribution with its mean and this habit has led to the writer making a technically incorrect statement.