Here is the scenario,

I am signing roughly 1000 messages, which consist of 16 byte hashes, with 1024 bit RSA. The private key is only used to sign the hashes, and there is no padding scheme.

The attacker has access to all 1000 messages and the public key. That is all they have to work with (no chosen plaintext ability, etc).

Does access to a large number of signed messages make it easier for the attacker to create a valid signature for a hash of their choosing?

If so, how? And would a padding scheme protect against it?

  • 1
    $\begingroup$ RSA without padding is malleable. If the hash is close to modulus size use Full Domain Hash otherwise stick to RSASSA-PSS $\endgroup$ – kelalaka May 1 '20 at 22:55

I'll ignore the term "encryption" in the title, since it is improper: signature is not encryption. Instead I'll try to answer the question:

Does direct textbook RSA signing of hashes of 1000 messages $M_j$ per the textbook RSA signaing function $\mathcal S$, as $S_j=\mathcal S(H(M_j))=H(M_j)^d\bmod N$, weaken the resistance against signature forgery for other messages under the same scheme, given $(N,e)$ a public key with 1024-bit RSA modulus.

Yes, for too narrow a hash $H$. One attack strategy could be that of Yvo Desmedt and Andrew M. Odlyzko: A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, in proceedings of Crypto 1985.

The basic attack

  1. Factors the $H(M_j)$ and keeps those that are $B$-smooth, forming a (sparse) matrix $A$ with one column per such $j$, one line for each prime $p_i$ that appears in such factorizations, collectively forming the factor base. The multiplicity of prime $p_i$ in $H(M_j)$ is at line $i$ column $j$ of $A$.
  2. Factors many $H(M'_k)$, and for those which factors all are among the factor base, form the vector $V$ of the multiplicities of that $H(M'_k)$, and try to solve for $X$ the system $V=A\cdot X$ where $X$ is a vector with one entry per column in $A$, and operations are in $\Bbb Z_e$.
  3. Once such $M'_k$ is found, computes the signature of $M'_k$ using

    • the multiplicative property: $\mathcal S(H\cdot H'\bmod N)=\mathcal S(H)\cdot\mathcal S(H')\bmod N$,
    • the known signatures $S_j$,
    • the coefficients in $X$, corresponding to powers of the $S_j$,
    • the fact that forall $p_i$, it holds $\mathcal S({p_i}^e\bmod N)=p_i\bmod N$.

It can work, or not, depending on:

  • The width of the hash. The narrower, the more smooths, the easier the attack.
  • The value of $e$. Lower $e$ (e.g. $e=3$) make the attack easier.
  • If the adversaries are able to choose some of the $M_i$; this allows the adversaries to try much more than 1000 messages in step 1, somewhat offsetting the effect of a wider hash.

In an improvement extending the applicability to less signed messages or wider hashes, pairs of $H(M_j)$ having a single prime factor larger than $B$ are kept separately if another $H(M_{j'})$ is in this case and shares the same larger prime factor, with the difference modulo $e$ in the respective multiplicities of the primes in the factor base for $H(M_j)$ and $H(M_{j'})$ used for an additional column in $A$. A further improvement uses two large primes.

It can be predicted about how many messages are required for a given hash width and $e$, and the work necessary. I wish I knew exactly how! There is an analysis in appendix C of the full version of Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann's Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures, in proceedings of Crypto 2009, but it does not account for $e$, nor of the large prime(s) improvement, nor of working under the constraint of relatively few non-chosen signed messages.

would a padding scheme protect against it?

Yes, by making the input of the textbook RSA signature function $\mathcal S$ too large to allow the attack.


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.