Is the RSA signature attack from Desmedt and Odlyzko practical?

Question

I would like to understand how the attack from the Desmedt and Odlyzko on RSA signatures (and subsequents works) can be made practical. This attack describes a way to forge the signature on a new message using Gauss elimination. The problem is that a message is hashed before the private exponent is applied, so maybe I have missed something... Why is this attack practical?

Thank you.

Answer 1

TL;DR: Yes, on narrow or some ad-hoc deterministic RSA padding, which must not be used.

---

The Desmedt and Odlyzko attack on RSA signatures [DO1985] assumes a deterministic RSA signature scheme with appendix that, for RSA key $(N,e,d)$, signs messages $M$ with signature $S=(H(M))^d\bmod N$ for some public function $H$ with $H(M)<2^k$ and $k\ll\log_2(N)$, and verifies alleged signature $S$ by checking that $S^e\bmod N$ matches $H(M)$. The attack is computationally feasible for $H$ a $k$-bit cryptographic hash, up to at least $k=200$ [CNST2016], and I believe $k=256$, perhaps more. The size of $N$ and $e$ are almost immaterial.

The attack computes the signature of a message $M_0$ chosen by the adversary from the signature of many other messages $M_i$ chosen by the adversary, and the public key $(N,e)$. All theses messages must obey one constraint: be smooth; that is, have all their prime factors below a "smoothness" bound (except perhaps for one of two larger prime factors shared with other $M_{i'}$, $i'\ne i$ (these large prime and two large primes variants of the attack parallel similar variants in MPQS, see [LM1990] as used in the landmark [AGLL1994] ).

---

The basic attack combs many messages $M$ to find these such that $H(M)$ has all its primes factors below bound $B$, and forms a large sparse matrix with one line for each such $M_i$, one column for each prime $p_j$ below $B$, the multiplicity of prime $p_j$ in $H(M_i)$ at the intersection $c_{i,j}$, and significantly more lines than columns.

By Gaussian elimination or a method to the same effect, it is found coefficients $u_i\in\mathbb Z$ for each line, such that $\forall j,\;0=\displaystyle\sum_{i\ge0}u_i\,c_{i,j}$, and $u_0=-1$. It follows that $\displaystyle\prod_{u_i<0}H(M_i)^{-u_i}\;=\;\prod_{u_i>0}H(M_i)^{u_i}$, and thus $H(M_0)\equiv\displaystyle\prod_{u_i\ne0,\,i>0}H(M_i)^{u_i}\pmod N$.

By raising the later to the power $d$, it comes that the signature $S_0$ of $M_0$ can be obtained from the signatures $S_i$ of some of the other $M_i$, as $$S_0\equiv\prod_{(u_i\bmod e)\ne0,\,i>0}S_i^{u_i}\;\;\prod_{(u_i\bmod e)=0,\,u_i\ne0}H(M_i)^{u_i/e}\pmod N$$

The Gaussian elimination can be directed to reduce the number of $S_i$ needed at the expense of needing more smooths; and that's easier for small $e$.

---

The attack is an existential forgery, but could be entirely practical if narrow deterministic RSA signature padding was used (contrary to all serious security guidelines). Consider an hypothetical automatic file timestamping server that upon receiving a file hashes it using SHA-384, then produces and signs using $S=(\operatorname{SHA-256}(M))^d\bmod N$ a message $M$ of the form:

At 2017-09-21 09:12Z I received a file which SHA-384 hash in base64 is RpzByokphjFifbPgFhR2vFnqbHvqA283Ud8sN0ic61fxd5hyQdXo3VofgkrSb0fz

The adversary wants a certain file backward time-stamped. S/he:

• Searches suitable past dates and/or equally useful variations of that file such that the message $M_0$ that the server would have generated for that (variation of that) file has smooth SHA-256.
• Generates many small files / future dates pairs such that the resulting $M_i$ have smooth SHA-256.
• Conducts the Gaussian-elimination-on-steroids part of the Desmedt and Odlyzko attack, which yields a subset of the original $M_i$ she needs signed.
• Obtains their signature by asking for a time-stamp of the appropriate small files at the beginning of the appropriate minute.
• Succeeds! The signature for $M_0$ can be computed from the signatures obtained at the previous step, and authenticates $M_0$ as a backward time-stamp that the server has not and would not have produced.

Note: The attack does not require computing any hash preimage or finding any collision: all the $M_i$ including $M_0$ are determined from the file and date they are related to, then hashed using SHA-256, then this hash is tested for smoothness.

The attack requires relatively few computations of SHA-384, but many computations of SHA-256 and fast ways to test if they are smooth (smooths are rare). Most of the computational effort is there, I believe.

---

The attack is thwarted if either:

• The hash is wide, ideally as wide as $N$ is; this is the exact strategy of RSA-FDH, is also used by RSASSA-PSS, and (in a bastardized and occasionally failing way) by ad-hoc RSA signature schemes.
• The signer inserts something unpredictable into what it sign; this is the strategy of probabilistic signature schemes like RSASSA-PSS and ISO/IEC 9796-2 scheme 2, and their de-randomized variants. This is also used by some responsible Certification Authorities, which generate a random or otherwise unpredictable certificate serial number when using ad-hoc RSA padding like RSASSA-PKCS1-v1_5, or less than ideal hashes like SHA-1.

---

The Desmedt and Odlyzko attack [DO1985] is a sub-component of other attacks on wide deterministic RSA signature padding, including the first break [CHJ1999] of the (withdrawn) ISO/IEC 9796:1991, and the break [CNST2016] of ISO/IEC 9796-2 scheme 1 (aka 1997).

---

References:

• [DO1985]: Yvo Desmedt and Andrew M. Odlyzko; A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, in proceedings of Crypto 1985.
• [LM1990]: Arjen K. Lenstra, Mark S. Manasse; Factoring with two large primes, in proceedings of EuroCrypt 1990.
• [AGLL1994]: Derek Atkins, Michael Graff, Arjen K. Lenstra, Paul C. Leyland; The magic words are squeamish ossifrage, in proceedings of AsiaCrypt 1994.
• [CHJ1999]: Don Coppersmith, Shai Halevi, Charanjit Jutla; ISO 9796-1 and the new forgery strategy, circulated as an IEEE P1363 Research Contribution, 1999.
• [CNST2016]: Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi, Ralf-Philipp Weinmann: Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures in Journal of Cryptology, 2016 (first version in proceedings of Crypto 2009); section 3 makes a modern exposition of the Desmedt and Odlyzko attack applied to RSA signature.