# Is the RSA signature attack from Desmedt and Odlyzko practical?

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.

• An interesting article :) This is only my assumption as well. The attack seems practical if the message is much smaller than N. (I will have to try it :D ) The hash is much smaller than N. However - the real world implementation uses (or should use) the OAEP padding to prevent as well this type of issues – gusto2 Sep 21 '17 at 8:51

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:

• Thank you for your answer, but you have not explained why we do not need to compute a preimage or a second preimage (which are hard problems for SHA-256 or 384). What I understand is that by using signatures on smoothed numbers we are able to obtain a signature $(\mathrm{SOMETHING\_NEW})^d \mod N$ thanks to a Gaussian elimination, but (it seems that) we still need to find an input $x$ such that $h(x)=\mathrm{SOMETHING\_NEW}$. – Dingo13 Sep 21 '17 at 13:41
• @Dingo13: I hope that the "Note: .." I just added answers that aspect of the question. In essence, SOMETHING_NEW (in my example, $M_0$) is under control of the adversary to some practical-enough degree. – fgrieu Sep 21 '17 at 15:21
• Thanks for your comment. I think I've understood, maybe you can confirm. You are saying that you generates $l+1$ smoothed hash outputs until the siognature of one of them can be computed as a linear combination of the other signatures? – Dingo13 Sep 21 '17 at 16:12
• @Dingo13: Yes! And in practice it is only needed the signature of a subset (possibly small) of the $l$ messages, as stated without proof in the answer's third bullet. – fgrieu Sep 21 '17 at 18:48
• Thank you. In fact I was thinking that the $l+1$-th element was constructed by linear combination of the first $l$. Now I understand why you say there are a lot of effort in computing hashes. – Dingo13 Sep 21 '17 at 19:43