# Why is the brute force search time for hashing algorithms 2^(num_bits / 2)?

I noticed that the brute force times (the time it takes to find a message that hashes to a given hash) of various hashing algorithms seems to be `2^(num_bits / 2)`. For example, people say that brute forcing `SHA1` (without using the vulnerability that reduces the brute force time to `2^69`) is `2^80`. In fact, if you look at this table, the "Security (bits)" column seems to always be half the number of bits, and I believe that's referring to the search time. How are they getting these numbers? I would think that to brute force a 160-bit hash, one would have to at least try `2^160` messages, or maybe `2^159` values on average to find a messages. I don't think the birthday attack is relevant here, as that seems to be about any collision, as opposed to a specific collision.

• The worst case is 2^N, the average time is half that. Sep 9, 2014 at 19:45
• (2^n)/2 is 2^(n-1), right?
– gsgx
Sep 9, 2014 at 19:47
• Right, it's Tuesday so I guess I can't do math Sep 9, 2014 at 19:49
• Birthday paradox. It's (2^n)/2 = 2^(n-1) to find a collision for a specific output in the average case, but it's (2^n)^(1/2) = 2^(n/2) operations on average to find some collision. By the time you've generated 2^(n/2) outputs, odds are better than even that some pair of them are identical. Oct 9, 2014 at 22:45