Signing MD5 hashes with RSA? [duplicate]

Question

Lets say I need to update a project and allow anyone to distribute the updates, however I need it to be secure, so I hash the data and sign the hash, this project uses MD5.

How likely would it be that a person could obtain the signing key or falsely sign files that could be distributed using the following information? If so would switching to MD6 fix this issue or is it deeper. Do I need to pad my messages?

Signing: $ \textrm{MD5}(M)^D \bmod(N) = S$

Retrieving hash: $ \textrm{MD5}(M) = S ^ E \bmod (N)$

Variables:

• $M$ = File contents (public)
• $\textrm{MD5}(M)$ = Hashed file contents (public)
• $S$ = Signed hash (public)
• $D$ = Decryption key (private)
• $N$ = Modulus (public)
• $E$ = Exponent (public)

Answer 1

Summing up and fleshing out the comments: Generally, signing software updates is good practise and should definitely be done. However, you ask about the security of an unpadded RSA signature on an MD5 hash. There are at least two issues with this:

MD5 security

MD5 is no longer considered safe, and hasn't been for quite a while (we're already phasing out its successor, SHA-1, in favor of SHA-2 and eventually SHA-3). MD5 has been broken for a while, and in ways that make it unsuited for signatures. Edit: My old explanation was wrong. See the comments by @Gilles and the answer by @fgrieu for the details of why MD5 is bad. The conclusion of "don't use it" still stands.

Solution: Use SHA-256 or another up-to-date hash algorithm instead of MD5.

Unpadded RSA signatures

If you sign the hash with a primitive RSA signature without any padding, you can attack the scheme as described in this question and answer. This would, again, allow an attacker to forge a message with a valid signature. Even when using SHA-256 instead of MD5, the security margin is too low for comfort.

Solution: Use a proper padding like PKCS#1 v1.5 or, even better, PSS.

General remarks

Please consider using an established method and (ideally) implementation for this purpose. Take a look at how other systems do this. Even though the potential attacks mentioned here may seem like they would not apply to your use case, it is bad practise to use methods you know to be insecure, just because you think the insecurities may not apply to your specific system. Using good algorithms and padding has almost no additional cost, but gains you the peace of mind that your system is secure, instead of "probably secure because the attacks probably do not apply to it, I hope".

Finally, the standard caveats about "don't implement the crypto yourself, use an established library" apply, and this question has a large number of good answers concerning best practises for cryptography and can serve as a good starting point for further research.

Answer 2

As pointed by Henno Brandsma and SEJPM in comments, two things can go bad:

1. Because no signature padding is used, there is a risk of multiplicative forgery. After you have signed plausibly many times, and disclosed the signatures, an adversary will be able to deduce a valid signature for some message that he chooses almost entirely. See Jean-Sébastien Coron, Yvo Desmedt, David Naccache, Andrew Odlyzko, and Julien P. Stern, Index Calculation Attacks on RSA Signature and Encryption.

2. Because you use MD5, which collision-resistance is broken including with chosen prefix, some adversary might craft part of your project to be nefariously changeable without changing the MD5 hash, thus the signature. For example if your project is delivered as a an executable starting with code maliciously written by some compiler vendor, that code can be crafted so that it performs normally (that's what you'll believe it always does) or, by changing a few bits of that code, it becomes a keylogger. That can be done in such a way that whatever your own code is, that few bit change does not alter the MD5 hash. It's also feasible to cryptographically hide what the nefarious code is/does to one who does not know the few bits to change.

To prevent these attacks, use RSA signature padding like RSASSA-PSS of PKCS#1; and a better hash, like SHA-256.