# 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. – RoraΖ Sep 9 '14 at 19:45
• (2^n)/2 is 2^(n-1), right? – gsingh2011 Sep 9 '14 at 19:47
• Right, it's Tuesday so I guess I can't do math – RoraΖ Sep 9 '14 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. – Stephen Touset Oct 9 '14 at 22:45