I understand that digital signatures are usually implemented by encrypting a mes
ID: 659911 • Letter: I
Question
I understand that digital signatures are usually implemented by encrypting a message digest with a private key, decrypting the resulting signature with a public key, and verifying that the message digest matches the message. This seems to be a normal application of an asymmetric encryption algorithm rather than a different algorithm, but is there anything about the scheme that makes it vulnerable to additional classes of attack over and above those that the underlying asymmetric encryption algorithm might suffer?
For example, does the use of a message digest algorithm, or the presence of the plaintext message, provide any additional information that an attacker can use to defeat the scheme?
To clarify what I'm asking: public-key encryption might be defeated by attacks such as chosen plaintext, or a breakthrough in factoring large numbers. Does using a public-key encryption algorithm in a digital signature scheme enable any additional types of attack?
Explanation / Answer
Yes. Using PKE for a digital signature has additional attacks; e.g., if you are using an RSA signature there are collision attacks on the hash function where if you can construct two messages m and m' that both have the same hash (H(m) = H(m')), if you can legitimately get someone to sign message m, then you can append that signature to message m' (even if you could not legitimately get someone to sign message m').
For example, back in the day MD5 was used as a hash in SSL certificates (X.509 certificates). However, it is possible to carefully construct MD5 collisions in much less than the expected 2^64 work. Therefore, an attacker merely had to construct a collision between a valid certificate they created (for say a website they control) and an intermediate certificate authority (note they should not alter the modulus or exponent to construct the collision as they need the private key). Then when you can get a trusted certificate authority to sign your valid certificate for the website, you can append that signature on to your fake intermediate certificate authority. Voila! You now have a trusted intermediate certificate authority and can sign any certificate you want and get web browsers to trust it.