# How can I tell how many bits of security a secure hash function has?

How can I tell how many bits of security a secure hash function has?

For example, how would I calculate or tell how many bits of security a secure hash function with 160 bits output would have? Assuming there are no known weaknesses…

-

Well, how resistant to attack would depend on what security properties you would need from it.

There are three standard assumptions we can make about a hash function:

• Given a hash value, it is difficult to find an image that hashes to that value; this is known as preimage resistance

• Given a image that hashes to a specific value, it is difficult to find another image that hashes to that same value; this is known as second preimage resistance. This is considered a stronger assumption than preimage resistance, because it may be possible to modify the image and not change the output value.

• It is difficult to find two different images that hash to the same value; this is known as collision resistance.

Sometimes we're interested in collision resistance, sometimes, we're not. One example where we may be interested in it is if we're using the hash as a part of a signature scheme. For example, suppose we find two images that hash to the same value; one says "I like icecream" and the other says "I agree to give Bob a million dollars". We then get Alice to sign the message that denotes that she likes icecream; because what the public key system signs is actually the hash, Bob now hashes a signed message from Alice giving him a million dollars.

Now, there are other times where we don't really care about collision resistance.

So, what's the big deal about collision resistance vs. preimage resistance? Well, it turns out that, if we don't assume any cryptographical weaknesses within the hash function, it is much easier to break collision resistance than it is to break preimage (or second preimage) resistance.

To break collision resistance, one way would be for the attacker to hash a huge number of variants of the message "I like icecream", and hash a huge number of variants of the message "I agree to give Bob a million dollars", and go through the lists and see if there's a value in common. For a 160 bit hash, we need about $2^{80}$ messages in both of the lists (because of the Birthday paradox, that's likely to be sufficient); it turns out that this is about the best we can do (assuming no crypptographical weaknesses within the hash), and hence we have about 80 bits of security against this attack.

On the other hand, to break preimage (or second preimage) resistance, we can't use the Birthday paradox. Instead, about the best we can do (barring a weakness within the hash function) is to hash lots of messages, and hope we get one that hashes to the target value. For a 160 bit hash, we expect to go through about $2^{160}$ messages before we stumble across one, and hence we have about 160 bits of security against these.

-
Thank you for breaking it down so simply!! This was very helpful – Shmoe Dec 6 '13 at 20:58
A bit of clarification for me: For 160 bits we would find a (second) preimage in about $2^{160/2}$ bits, no? Or is it that second-preimage doesn't work that way? – rath Dec 6 '13 at 21:01
@rath: no, a second preimage doesn't work that way. For a hash function without any cryptographical weaknesses, the knowledge of one preimage doesn't really help; we've no better strategy than hashing that one image, and then doing a preimage search on that hash value, looking for a second image. – poncho Dec 6 '13 at 21:04
I'm sorry I'm still a bit confused. If we are guaranteed to find a preimage via brute force in $2^{160}$ operations (or $2^{160}+1$), wouldn't we expect to find the preimage in $2^{80}$ on average? (or is it $2^{160}/2$?) – rath Dec 6 '13 at 21:08
@rath: no. Actually, hashing $2^{160}$ images doesn't guarrantee us to find a preimage; it's just that if we hash that many, we have a good chance to find one. Another way to look at it; if we hash a random image, we have a probability $2^{-160}$ of the hash being the value we're looking for; if we hash $2^{80}$ random images, then the probability that one of the resulting hashes is the one we're looking for is about $2^{80} \times 2^{-160} = 2^{-80}$; rather unlikely. – poncho Dec 6 '13 at 21:13