# RSA 1024 bit forge a new matching signature from a chosen message

I have an RSA signature scheme with 1024-bit key where I know the following:

• Public modulus $N$
• Public exponent $e=3$
• A lot of signatures

Summary:

To compute a signature, an MD5 hash is calculated from a collection of byte and the textbook RSA private key function is applied to that. The verification procedure for a signature $S$ is to check that $S^e\bmod N$ is the MD5 hash of the alleged message.

Our teacher give us more than one signature.

Question:

Can someone give advice to find a practical way to find a new matching signature from a chosen message?

• "one of several working private exponent $d$", what does this mean? – mikeazo Oct 5 '15 at 13:23
• There is no known way to recover $d = 3^{-1} \bmod lcm(P-1, Q-1)$ given access to an oracle that computes $f(x) = x^d \bmod N$. Are you sure that your teacher didn't ask you to compute the signature for another message that you haven't been given the signature to? – poncho Oct 5 '15 at 13:28
• Attempting to recover $d$ is a deadend. Instead, you should attempt to figure out how to deduce a signature without knowing $d$. Hint: the relation $a^d \times b^d = (ab)^d \pmod N$ is useful. – poncho Oct 5 '15 at 14:59
• Check out '4.1 Coppersmith's theorem' in Boneh's Twenty Years of Attacks on the RSA Cryptosystem – CodesInChaos Oct 6 '15 at 9:05
• @Seed3Key: you are right that you will not be able to sign any message that you may choose; but you will be able to sign some message that you choose and is not one of those that you have been given. The later is the meaning of chosen message in cryptography, at least in the context of digital signatures. If the verification procedure checks $\left(S^e\bmod N\right)=\text{MD5}(M)$ that's the best attack I see. – fgrieu Oct 8 '15 at 8:27

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).

• I need to read it many times before understand it fully (hopefully) but is the accepted answer. – Seed3Key Oct 9 '15 at 17:04