How robust is RSA-FDH against distribution bias?

Question

Suppose we want to use the RSA-Full Domain Hash (-FDH) signature scheme. This essentially works precisely like textbook RSA but instead of signing $m$ directly, we sign $H(m)$ with $H:\{0,1\}^*\to\mathbb Z_n^*$ being reasonable model-able as a random oracle (we need the ROM for the security reduction).

Now my question:
Are there any known attacks when $H$ exhibits a minimal (1-bit) bias?

In particular consider $H$ where $m$ is mapped to the first $\lfloor \log_2(n)\rfloor$ of SHAKE128(m), ie where we generate a hash output as long as $n$ but always zero the MSBit out.

Motivation: If we had such a bias for the generation of $k$ in (EC)DSA, this would probably allow for an attack and I talked in the past about how RSA-FDH is one of the applications of XOFs.

Answer 1

Fix a number of bits $t$, e.g. $t = 2048$; consider RSA-FDH with $t$-bit modulus $n$, so that $2^{t - 1} < n < t$. Fix a hash $H\colon \{0,1\}^* \to \{0,1\}^{t - 1}$. Can we use $H$ for RSA-FDH, even though the literature on RSA-FDH typically posits a hash $G_n\colon \{0,1\}^* \to \mathbb Z/n\mathbb Z$?

It is not hard to define a hash $G_n\colon \{0,1\}^* \to \mathbb Z/n\mathbb Z$ with near uniform distribution using a double-length hash $H_0\colon \{0,1\}^* \to \{0,1\}^{2t}$ by $G_n(x) = H_0(x) \bmod n$; the modulo bias at this scale is negligible, just like in EdDSA's use of SHA-512 to select $k$ from $\ell \approx 2^{252}$ possibilities.

If our signature scheme were randomized, we could do rejection sampling, as phayes suggests in another answer, and attain an exactly uniform distribution—indeed, if we wanted anonymous signatures so that signatures under two keys are indistinguishable without the keys, we would have to do rejection sampling, though on the signature rather than the hash, to thwart anglophone statisticians from counting German tanks. But this question is about the deterministic RSA-FDH.

As far as I can tell, this specific question—where $H$ covers only about half of $\mathbb Z/n\mathbb Z$—has not been addressed in the literature. But very similar questions have been:

• Tight security can be proven for deterministic Rabin–Williams signatures using $H$[1]. Although there are barriers to applying the same proof to RSA, it seems unlikely that the space covered by $H$ is one of them: they rather have to do with differences between squaring and (e.g.) cubing. (Questions like this are part of why [1] used a single $H$ with $t$-bit codomain instead of a key-dependent $G_n$.)

• Tight security can be proven for PSS signatures using a randomized hash whose most significant bit is always zero[2]. Here the randomized hash is $$P_r(m) = 0 \mathbin\| w \mathbin\| (r \oplus H_2(w)) \mathbin\| H_3(w),$$ where $w = H_1(r \mathbin\| m)$, and $H_1$, $H_2$, and $H_3$ have the right widths to make it all work out. The proof given by Bellare and Rogaway requires $|r| \geq 128$ to provide meaningful security.

• Tight security can be proven for a randomized version of FDH[3] where the randomization is appended to, rather than embedded in, the signature, like in phayes' system: a signature $(r, s)$ on $m$ under $n$ satisfies $$s^e \equiv G_n(r \mathbin\| m) \pmod n.$$ Bizarrely, this tight security works even if $|r| = 1$, even though it can be proved that deterministic RSA-FDH cannot admit such tight security[4], although that proof works only for large exponents which leaves open the possibility of tight security for $e = 3$[5] (paywall-free). This state of affairs raises all sorts of questions about the significance of these reductions[6].

The Bellare–Rogaway 1996 proof[2] that a $q$-query forger for a trapdoor permutation signature scheme $f(s) = G_n(m)$ can be converted into an algorithm for inverting $f$ on a point $y$ works by running the forger with a derived random oracle $G'_n$ that returns $y$ on a randomly chosen one of the $q$ queries, and otherwise defers to $G_n$. If the forger succeeds in finding a forgery $(m, s)$, there's about a $1/q$ chance that it found the preimage $s$ for our chosen point $y$ rather than for the $q - 1$ options we sent to $G_n$, and thus that $s = f^{-1}(y)$ is the desired preimage.

If we replace the equation by $f(s) = H(m)$, the reduction simply doesn't work to compute $f^{-1}(y)$ for $y \geq 2^{t - 1}$, which happens with probability less than 1/2 if $y$ is uniformly distributed in $\mathbb Z/n\mathbb Z$, so the same inversion algorithm has about a $1/(2q)$ chance of success instead. Formally this would suggest you need to add another bit to the modulus to attain the same security—but in practical terms that bit is likely inconsequential (some practical key generation algorithms vary with a slop of a bit anyway[7]), and it remains unclear what the significance of the tightness gap is at all here when adding a single bit of randomization enables proving a theorem that eliminates the gap.

In brief, it is hard to imagine that using a hash covering only up to $t - 1$ bits, where $2^{t - 1} < n < 2^t$, could meaningfully hurt the security of RSA-FDH. Certainly there are no known attacks like there are against biases is per-message secrets in Schnorr- and DSA-type signatures.

Answer 2

This isn't answering your question directly, but is instead proposing a different solution that side-steps the question entirely.

Instead of zeroing out the most-significant bit, you could instead append a random initialization vector (IV) to the message before putting it through SHAKE128. If the resulting digest (interpreted as an integer) is larger than modulus n, then just generate a new IV and try again. You'll have to pass around the IV in addition to the signature, but this shouldn't be a big deal.

In Pseudocode:

iv = random_iv()
digest = shake128(message + iv)
while modulus_n < digest.as_int():
    iv++
    digest = shake128(message + iv)

I've implemented this in rust here: https://github.com/phayes/rsa-fdh