Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

For storing passwords, it seems that the use of intentionally slow hash functions (like PBKDF2 and bcrypt) is now recommended. This is because most hashes are designed to be fast, which also makes certain attacks on them parallelizable on GPUs.

Now I'm wondering if it would make sense to use slow hash functions for digital signatures. Are collision attacks slower when the hash function is slower? And are collision attacks the only kind of attacks you need to guard against?

(If it matters, the context involves authors that publish messages to the general public, at a rate that may vary from hourly publications to a handful of messages in a month, and the general public needs to be able to tell those messages originate from those authors.)

share|improve this question
add comment

1 Answer 1

up vote 6 down vote accepted

No it's not useful to use slow hashing in such a situation.

The relevant attacks against the hash in a digital signature are second pre-images and sometimes collisions. Assuming the hash-function is secure, then there is no way to find collisions with less work than $2^{n/2}$, and second pre-images with less work than $2^{n}$. There is no weak part the attacker can abuse in his attack, so he needs to face the full strength of the cryptographic hash.

As long as the algorithm remains unbroken, we can make the problem exponentially difficult for the attacker, while increasing the cost only linearly(or something similarly low) for the defender. In short we don't fear high computational power, we only fear crypto-analysis.


With password hashing, the relevant attack is a first pre-image. The problem here is that typical passwords have a low entropy, i.e. they're easy to guess. When guessing the original password the attacker doesn't care how strong the hash-function is, he simply executes it with many different inputs. We use slow hashes here, to increase the effective strength of the password by perhaps 20 or 30 bits.

There is no way to slow down the attacker exponentially while slowing down the defender only by a little bit. That's because the attacker has the same knowledge as the password verifier, and does exactly the same thing as the verifier. Any slowdown hits the defender just as much as the attacker.

The only thing we can try is to minimize the advantage an attacker gets from specialized hardware, and make the hashing as slow as the defender can afford. This is a desperate measure that's only used because no good defense is available.

share|improve this answer
    
The extra work for password hashing affects the defender once, but affects the attacker for each password attempt, so there is an asymmetry to exploit when defending. –  orip Jun 25 '12 at 17:37
    
@orip: Yes, but it is still a linear relation: To double the work for the attacker, you have to double the work for the defender. (Also, it is not only once, but for every login attempt or similar use of the password.) –  Paŭlo Ebermann Jun 26 '12 at 19:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.