1

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?

  • 1
    I'm not quite sure what you're asking. If you could clarify a bit? – RoraΖ Aug 20 '14 at 19:55
  • You are under the impression that PKI is vulnerable at this time? – zedman9991 Aug 20 '14 at 20:38
  • @zedman9991: Not necessarily. I understand that most attacks are not practical. I'm interested in whether using the algorithm in a signing scheme enables any additional classes of attack, theoretical or otherwise. – jl6 Aug 20 '14 at 20:43
  • This (very-common) description of signature as "encrypting with private key" is only half-true of RSA -- the modexp computation is the same, but the padding and formatting schemes are different and using an actual RSA-encrypt function won't produce a valid signature -- and completely false for DSA and ECDSA. But yes, if someone else signs data controllable by an attacker, hash collisions can be a problem as @jimbob describes. – dave_thompson_085 Aug 21 '14 at 9:08
2

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.

1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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