Cost of attacking textbook RSA signature of $b$-bit hash of the message

Question

A signature system applies textbook RSA to a $b$-bit hash of the message. What's the cost (preferably, as CPU time on common hardware) of existential forgery assuming known signature of $r$ random messages? How much is that reduced if public exponent is very small ($e\le7$)?

We assume

• Safe RSA public key $(n,e)$ and matching secret private key $(n,d)$ with $n$ of $\ell$ bits and $2048\le\ell\le8192$.
• Ideal hash $H:\{0,1\}^*\to[0,2^b)$ with $b\in[128,512]$ large enough that $H$ is preimage-resistant.
• Signature $s$ of message $m$ is computed as $s=H(m)^d\bmod n$.
• Message/signature pair $(m,s)$ is accepted iff $H(m)=s^e\bmod n$.
• The adversary has obtained $r$ valid $(m_i,s_i)$ pairs for some $r\in[2^{16},2^{64}]$ and random $m_i$. $r\ll2^{b/2}$ thus the $s_i$ are assumed distinct.
• The adversary succeeds by exhibiting an acceptable $(m,s)$ pair with $s$ not among the $s_i$. The adversary would additionally succeed by exhibiting an acceptable $(m,s_i)$ pair with $m\ne m_i$; but since the hash is preimage-resistant and RSA is a bijection, we can discount that possibility; and that reduces the interest of the $m_i$ for the attacker to a mere alternative method to compute ${s_i}^e\bmod n$.

---

This is grounds for the Desmedt and Odlyzko attack. In it's basic form independent of $e$, that attack computes and factors $h_i={s_i}^e\bmod n$, then repeatedly hashes incremental $m$ such that $H(m)$ has all it's factors appearing in the factorizations of the $s_i$, and further such that $H(m)=\prod{h_i}^{z_i}$ with $z_i\in\mathbb Z$ has a solution. This reduces to a linear system of equations, and yields the signature of $m$ as $s=(\prod{s_i}^{z_i}\bmod n)\bmod n$. However, contrary to some of the literature in this answer, it's not assumed signature of chosen messages, thus $r$ is a hard limit; and I'd want some quantitative cost as a function of parameters $b$, $r$, and $e$ inasmuch that matters.

Motivation: an attack with $b=256$ would allow signing an unconstrained plaintext given $r$ signatures in this proposed signature system. Our message is their $k$, and our $H$ combines AES-GCM of their plaintext under $k$, SHA-256 of their ciphertext, and XOR with $k$.

Answer 1

To run the Desmedt and Odlyzko attack you need a set of signatures whose hashes have prime factorisations are supported on a set of primes with fewer set elements than the number of signatures. For a given $b$, we expect that for $r$ below a certain bound it is not possible to find a set (this is related to the Sharp transitions in making squares paper by Croot, Granville, Pemantle and Tetali). The most likely subset of the signatures will be supported on the smallest set of primes, so the best approach is to look for signatures of hashes that are smooth up to some bound. Taking the probability that a $b$ bit number is $2^\alpha$ smooth as roughly $\rho(b/\alpha)$ where $\rho$ is the Dickman function (which is implemented in sagemath) we want the smallest $\alpha>0$ such that $$r\rho(b/\alpha)>\pi(2^\alpha)$$ (which will not exist for many $r$). For given $b$ we can find the infimum of $$\frac{\pi(2^\alpha)}{\rho(b/\alpha)}$$ and use this to find the minimum $r$ (once past this more signatures don't help much).

For $b=256$ the minimum is around $\alpha=34$ giving $r\approx 5.4\times 10^{20}\approx 2^{68.8}$ which constitutes a weakness but not a very practical attack.

Carl Pomerance gave a useful log-approximation to the required $r$ in terms of $b$, which can be written $\log r\approx \sqrt{(2b\log b)/\log 2}$, which in this case says $r$ should be around 64 bits, this is not far from the more precise estimate above and so should produce answers for other values of $b$ that are not too far wide of the mark.

Varying $e$ will not affect matters greatly, though does allow a few small primes for free. If $p<b^{1/7}$ we can write down a "signature" for $h(m)=p^7$.