Suppose I have a message $M$ for which I generate an RSA-2048 digital signature as follows:

$H = H(M)$, $H(M)$ being the SHA-256 of the message $M$
$S = H^d \bmod N$

Assume $N = pq$ is properly generated and $d$ is the RSA private key. And I verify the signature as follows:

$S^e \bmod N = H'$

where $H'$ is the SHA-256 of the message to be authenticated. Assume $e$ is the RSA public key.

Since I've not used any padding then are there any flaws with the above approach? What if $e = 3$? What if $e = 2^{16}+1=65537$?

Your guidance is much appreciated.

  • $\begingroup$ I've quickly edited your question. If you don't like the edit you can either edit again (using the "edit" button) or roll-back my edits by clicking on the "edited ... ago". $\endgroup$ – SEJPM Jul 10 '15 at 20:17
  • $\begingroup$ DJB states in this paper that the Rabin digital signature scheme (which is at least similar to RSA) is still unbroken because the message is hashed. This may imply that this scheme is secure. I couldn't find any security issue in the HAC either... $\endgroup$ – SEJPM Jul 10 '15 at 20:57

One property that this unpadded system is that it is homomorphic; if $A^d = X$ and $B^d = Y$, then we know that $(AB)^d = XY$, and it doesn't matter if we don't know what $d$ is. More generally, if we have a collection of $H_1, H_2, H_3, ... H_n$, and a collection of signatures $S_1, S_2, S_3, ..., S_n$, then for any set of integers $e_1, e_2, e_3, ..., e_n$, we have:

$$(S_1^{e_1} S_2^{e_2} S_3^{e_3} ... S_n^{e_n})^d = H_1^{e_1} H_2^{e_2} H_3^{e_3} ... H_n^{e_n} $$

So, if we take a large collection of valid message and signatures pairs, hash the messages, and then factor the hashes. Then, we look for multiplicative combinations of those hashes that yield a hash that we haven't seen (going through a long list of messages to hash); if we find a message that hashes to a value we know a linear combination of, we can immediately deduce the signature.

The attack works for any value of $e$

  • $\begingroup$ Any idea on the run-time of this attack? $\endgroup$ – SEJPM Jul 11 '15 at 13:02
  • $\begingroup$ @SEJPM: not off the top. However, this sort of 'factor a series of 256 bit integers, and look for a linear combination' is somewhat similar to what the Quadratic Field Sieve does when factoring a 512 bit number, and so there's a (very) rough starting point... $\endgroup$ – poncho Jul 11 '15 at 13:14
  • 1
    $\begingroup$ Take a look here: jscoron.fr/publications/isodcc.pdf. On page 8 you have estimates of the cost. It's not easy for SHA256 but it's definitely not impossible and there isn't enough of a security margin. $\endgroup$ – Yehuda Lindell Jul 12 '15 at 18:25

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.