We assume an RSA signature scheme with appendix where the signature of message $M$ is $S=\left(\operatorname{MD5}(M)\right)^d\bmod N$, and the verification procedure checks that $0\le S<N$ and $\left(S^e\bmod N\right)=\operatorname{MD5}(M)$, with $e=3$ (or other relatively small odd $e\ge3$). Eve somewhat got $k$ rightful signatures $S_i$ and perhaps the corresponding messages $M_i$ (which Eve could not influence). Eve wants to construct another $M$, and matching signature $S$.
Eve will make a multiplicative forgery: she'll find a message $M$ and a matching set of $k$ non-negative integers $e_i$, such that $\operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i}$ is an $e$th power, then compute the signature of $M$ as
$$S=\left(\sqrt[e]{\operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i}}\right)\cdot\left(\prod S_i^{e_i}\right)^{-1}\bmod N$$
which verifies $\left(S^e\bmod N\right)=\operatorname{MD5}(M)$.
Define $m_{i,j}$ as the multiplicity of prime $p_j$ in the factorization of $\operatorname{MD5}(M_i)$, and define $m_j$ as the multiplicity of prime $p_j$ in the factorization of $\operatorname{MD5}(M)$. The goal of Alice is that $\forall j,\; m_j+\sum_i m_{i,j}\cdot e_i\equiv0\pmod e$. That linear system of equation with unknowns $e_i$ is equivalent to $\operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i}$ being an $e$th power.
Eve computes the hashes $H_i=\operatorname{MD5}(M_i)$, directly or as $S_i^e\bmod N$. She factors the $H_i$ at least partially (with $H_i<2^{128}$, even complete factorization is feasible). She can ignore any $H_i$ with a prime factor $p_j$ not appearing in the other $H_i$ [and $m_{i,j}\not\equiv0\pmod e$, but that is likely for $k$ large enough to carry the attack]; in particular she can without loosing much ignore those $H_i$ with a prime factor larger than about $k^3/\log(k)$, which are unlikely to be of any help.
Outline of the rest: Eve repeatedly
- selects a message $M$ of her choice [that she did not previously select, and distinct from the $M_i$ if these are given]
- computes $\operatorname{MD5}(M)$ and factors it at least partially
- if that factorization consists entirely of primes occurring in the factorization of at least one of the $H_i$ kept [in that screening Eve could exclude primes with multiplicity $m_j\equiv0\pmod e$ in the factorization of $\operatorname{MD5}(M)$, and occurrences with multiplicity $m_{i,j}\equiv0\pmod e$ in the $H_i$, but that won't make much of a difference for $k$ large enough to carry the attack]
- attempts to solve the linear system, and if that works
- computes $S$, noting that the $e$th root extraction reduces to dividing the exponents by $e$ in the known factorization of $\operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i}$
- outputs $M$ and $S$.
It will help to have preprocessed the system of linear equations. For larger $k$, solving the linear system will succeed for a large proportion of $M$ having passed the screening; or/and it will be possible to put an upper bound of the $p_j$ early on, making the factorization easier and the linear system smaller, thus easier to manage.
A small $e$ helps the attack, but with a large-enough $k$ it can be carried for any $e$. The size of the public modulus $N$ of the RSA key is essentially immaterial; what matters most is the width of the hash, which at 128-bit is grossly insufficient.
A slightly simpler variant of the problem (where all the messages are chosen, which is moot for a hash without collision resistance as $\operatorname{MD5}$ is nowadays) is discussed by Jean-Sébastien Coron, David Naccache and Julien P. Stern in section 2 of: On the Security of RSA Padding (in proceedings of Crypto 1999); or, when we set $\mu$ to $\operatorname{MD5}$, by Don Coppersmith, Jean-Sébastien Coron, François Grieu, Shai Halevi, Charanjit Jutla, David Naccache, and Julien P. Stern in section 3 of: Cryptanalysis of ISO/IEC 9796-1 (in Journal of Cryptology, 2008). The idea of a building coefficients by solving a linear system based on prime multiplicity was introduced by Yvo Desmedt and Andrew M. Odlyzko in A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes (in proceedings of Crypto 1985).
