Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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:
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 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:
