3
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2015 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, 2015 at 20:57

1 Answer 1

4
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ Any idea on the run-time of this attack? $\endgroup$
    – SEJPM
    Jul 11, 2015 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, 2015 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$ Jul 12, 2015 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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