0
$\begingroup$

I know that a cryptographically secure hashing algorithm is required for proper message signing (SHA-1, or I think SHA-2 is the current suggested algorithm). However, why does the hashing algorithm necessarily need to be "strong"?

Seeing as the hashing is done before encryption/signature calculation, wouldn't an attacker need to first have the private key of the signer before being able to cause any damage? What sort of vulnerabilities do we open ourselves up to when we use weak hashing algorithms in DSS?

$\endgroup$

1 Answer 1

4
$\begingroup$

Well, if the hash function is weak, then the attacker might be able to take a valid signature for a signed message, and find a second message for which the signature for this first would also validate for the second. For example, if Alice signs the message "I like chocolate", what Bob might do is find a second message "Alice owes Bob $13,106,107.57", and reuse the chocolate signature for the second message.

Here's how it works; when someone verifies the signature, they take the message, hash it, and then uses the underlying signature verification on the computed hash, the signature and the public key. Note that once we have computed the hash, the signature verification logic doesn't pay any more attention to the message. Hence, if Bob can find a second message that hashes to the same value, then the rest of the signature verification logic will proceed as with the valid message. Note that the attacker didn't need the private key to do this; all he needed was to find a second message that hashed to the same value.

The formal term for the property that a hash function doesn't allow someone to do this is "second preimage resistance"; that is, given an image, one cannot find a second image that hashes to the same value.

Now, it is possible that Bob can get Alice to sign an innocuous message that Bob had picked out (and then reuse that signature with a message that isn't quite so innocuous); because of this, we generally also insist that hash functions has a stronger property called "collision resistance"; that is the property that one cannot find two different images that hash to the same value.

$\endgroup$
1
  • $\begingroup$ For an example of the last part: certificate authorities. There's an example of someone who, as a proof-of-concept, exploited the fact that a CA handled requests in a predictable way and used MD5 to create a real SSL certificate for a site they controlled which collided with a CA certificate that they created. They got the real CA to sign the former, which was also a valid signature for the latter. $\endgroup$
    – cpast
    Commented Jan 7, 2015 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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