# How robust is RSA-FDH against distribution bias?

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.

• Not an answer to your question at all, but have you considered just using Barrett reduction on a $(2\lfloor\log_2 n\rfloor + 1)$-bit SHAKE128 output? That smooths the modulo bias into practically nothing, and the cost should be negligible compared to the modular exponentiation by the secret signing exponent (and it can even be done relatively easily in constant time). – Squeamish Ossifrage Dec 5 '17 at 18:44
• @SqueamishOssifrage indeed I have not, but I asked this question mostly out of curiosity anyways :) – SEJPM Dec 5 '17 at 19:29
• It seems unlikely to me that this will be a problem: tight security can be proven for Rabin–Williams signatures using a hash as you describe, but (a) the various standard papers on RSA-FDH security all assume the image of $H_n$ is all of $\mathbb Z/n\mathbb Z$ and not merely half of it, and (b) the proofs for RSA are all rather painfully complicated and still changing. In any case, it would be rather surprising if this led to key recovery like (EC)DSA. – Squeamish Ossifrage Mar 16 '19 at 4:48
• I would be quite surprised if this made a difference. But even if it did, my suggestion from over a year ago would alleviate any concern anyway at negligible additional cost to signing. – Squeamish Ossifrage Mar 16 '19 at 4:53

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.

• Thanks for the in depth answer! Could you explain a bit more what you mean by "on the output rather than the input, to thwart anglophone statisticians from counting German tanks" ? – phayes Mar 16 '19 at 16:20
• References on anonymous signatures and the German tank problem: crypto.stackexchange.com/a/67918 – Squeamish Ossifrage Mar 16 '19 at 16:21
• For a $t$-bit $F$, you did rejection sampling for $r$ until $F(r) < n$ where $F(r)$ is the input to private key operation $x \mapsto x^{1/e} \pmod n$. To attain anonymous signatures, you can do rejection sampling for $r$ until $F(r)^{1/e} < 2^{t - 1}$ instead where $F(r)^{1/e}$ is the output of the private key operation. I edited to clarify that it's rejection sampling on the hash vs. rejection sampling on the signature. – Squeamish Ossifrage Mar 16 '19 at 16:25
• The appellation ‘German tank problem’ was given by anglophone statisticians during World War II when they actually were trying to count German tanks rather than distinguish RSA moduli by samplings of signatures, and the name stuck. – Squeamish Ossifrage Mar 16 '19 at 16:37

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

• If you're happy with randomized signatures, conceivably one could do this with PSS and save the trouble of transmitting the IV—except the standard security theorems for PSS work just fine if the msb is fixed to zero anyway! – Squeamish Ossifrage Mar 16 '19 at 16:44
• Thanks Squeamish Ossifrage. To make this deterministic, I think we could just always initialize the iv to zero, and increment it to find a digest where digest < n. Then we don't need to pass around the IV at all. Thoughts? – phayes Mar 16 '19 at 17:05
• Well, then the verifier has to try up to, say, 128 verifications before they can confidently conclude a forgery. With $e = 3$, maybe that's not so bad—still cheaper than a private key operation—but PSS fits the hash and randomization into $\mathbb Z/n\mathbb Z$ at zero additional cost to the verifier. – Squeamish Ossifrage Mar 16 '19 at 19:59