Score:6

RSA Signature using SHA-256 is secure?

cn flag

Is following RSA signature scheme secure against forgery and prevents breaking text book RSA?

$$y = \operatorname{SHA-256}(m)$$ $$s = y^d\bmod N$$

where $m$ is message of arbitrary length, $y$ is the 256-bit hash of $m$ computed using SHA-256, $d$ is RSA private key, and $N$ is an RSA modulus with length 2048 or higher?

kelalaka avatar
in flag
There is already [RSA-FDH](https://crypto.stackexchange.com/a/95940/18298) that this answer covers your needs.
fgrieu avatar
ng flag
SHA-256 is not wide enough that the security argument of RSA-FDH applies. On the contrary, the [Desmedt and Odlyzko attack applies](https://crypto.stackexchange.com/q/51680/555) to some degree to break EUF-CMA. With how much work, well, that requires care... See [this](http://www.crypto-uni.lu/jscoron/publications/iso97962joc.pdf#page=4) \[link fixed\]
Score:11
my flag

An obvious way to attack this (and we're shorten $\text{SHA256}(m)$ as $S(m)$ :

  • For a large number of messages $m_i$, compute $S(m_i)$, and factor that. If it is smooth, record the message and the prime factors in a table; if it is not smooth, reject it

  • When you have recorded enough messages (and prime factors) in your table, do elimination on the prime factor table to find a set of messages and factors where all the primes of the selected messages, when multiplied by the factors, all sum to 0.

If we have such a product (and the multiplier corresponding to one of the messages, say, $S(m_0)$, is 1), then we have (where $p_i$ is the multiplier we assigned to message $i$):

$$S(m_1)^{-p_1} \cdot S(m_2)^{-p_2} \cdot ... \cdot S(m_n)^{-p_n} \equiv S(m_0)$$

So, ask for the signatures of $m_1, m_2, ..., m_n$; from that, you can deduce the signature for $m_0$.

So, how feasible is this? Well, the bulk of the logic is reminiscent of what is done in the Quadratic Field Sieve (QFS); the size (256 bits) is about what you get when you apply QFS to a 512 bit modulus. QFS can factor 512 bit modulii feasibly; I conclude that this algorithm would also be feasible.

poncho avatar
my flag
@fgrieu: better???
fgrieu avatar
ng flag
Yes. But even a mod can't upvote twice!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.