Are digital signature algorithms subject to the same types of attack as public-key encryption algorithms?

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?

Answer 1

Does using a public-key encryption algorithm in a digital signature scheme enable any additional types of attack?

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.

This attack was successfully done in 2008.

Answer 2

I think it is fair to consider the message digest to be a random string because it's a hash of something that you don't choose (the person sending you the message chooses it). So you have a random, known plain text (the digest), and it's encrypted version with a private key (the signature).

Note that assuming that the signature is authentic, having the known plain text is useless, because you can recover it from the signature by applying the public key.

Now, because of the properties of RSA (finite field exponentiation which is a bijection), applying a private key to a random string, gives you another random string. So in fact, there is no more information from having a message digest, than from picking yourself a random string and saying "it is a message digest", because indeed, it is the digest of some message...

So in conclusion, you have nothing more than a random string (the signature), and the public key. Arguably a random string is of no use to guessing the private key, and what you have is the public key which you already have.

So no, it doesn't enable you to do anything more than what you could have done knowing the public key only.