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, 2014 at 19:45
-
(2^n)/2 is 2^(n-1), right?– gsgxSep 9, 2014 at 19:47
-
Right, it's Tuesday so I guess I can't do math– RoraΖSep 9, 2014 at 19:49
-
2Birthday 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 TousetOct 9, 2014 at 22:45
2 Answers
When a hash function has an output of size n bits, then:
- The generic algorithm for finding a preimage (or a second preimage) has average cost 2n evaluations of the hash function.
- The generic algorithm for finding a collision has average cost about 2n/2 evaluations of the hash function.
By "generic" we mean "the algorithm that works against every hash function, however perfect that function may be". In the case of preimages and second preimages, the generic algorithm is also known as "luck" (we try input messages until we get lucky). For collisions, there are various smart algorithms that are all facets of the so-called birthday paradox. I wrote "about" because these smart algorithms also incur some RAM cost or some limitations on parallelism, so the actual cost of finding a collision cannot really be expressed as a single number; or, if you prefer, the mathematical cost does not translates exactly to a proportionate number of dollars, if you really want to do the computation.
Various protocols use hash functions for various reasons. It is hard to ascertain whether a given protocol is immune to collisions, or not. In some cases, an actual attack may require a preimage computation; or maybe a collision is enough; or the situation could be more complex. So, just to be safe, we usually assume the worst and thus look at the lowest resistance. Therefore, we rate a hash function with a 160-bit output to be of strength "80 bits" (or 280). We know that we may be overly conservative here; be we cannot be sure.
I don't see anything that indicates that "Security (bits)" is looking for a preimage attack vs a collision, so I think your assumption that the birthday paradox is irrelevant is probably not accurate. Collisions are still a significant security problem, in fact they've been used to forge SSL certificates. A preimage attack (finding another input that matches a particular value) still requires 2^n operations (modulo weaknesses in the hash algorithm).
