# RSA-FDH Signature Scheme EUF-CMA

I am aware of attacks whereby an attacker is able to forge a message IF the hash of the original message is the same hash as their current message. The question is, is it still possible for RSA-FDH to be EUF-CMA IF the hash function in question is collision-resistant. Lets take the case of $$H(x) = 3x \mod N$$. 3 is a prime number and N is always going to be prime as well. The function, in this case, is collision-resistant but despite this, is it still possible to break the EUF-CMA of RSA-FDH?

• Actually I the RSA-FDH proof asks for a random oracle and not just for a collision-resistant hash. So yes there is an "easy" forgery against this scheme.
– SEJPM
Aug 25 '19 at 16:58
• Interesting... so even if it is a collision resistant hash, one could still forge a message? How is that even possible? Aug 25 '19 at 17:22
• Trivial counter example: $H(x)=x$, suffers from all the weaknesses of textbook RSA signatures. The RSA problem is only hard if $x$ in $c=x^e\bmod n$ is chosen uniformly at random.
– SEJPM
Aug 25 '19 at 17:57
• Welcome to Crypto.SE! By collision resistant you mean in case where we restrict $x$ to $\{0,\ldots, N-1\}$? Aug 26 '19 at 18:24

The function, in this case, is collision-resistant but despite this, is it still possible to break the EUF-CMA of RSA-FDH?

Yes, because the requirement for security is the hash function acting like a random oracle and not it being collision-resistant.

To illustrate this, consider the "hash function" $$H(x)=x$$ which is clearly collision resistant. Yet, RSA-FDH instantiated with this hash is not secure as it literally is textbook RSA, which suffers from the usual small-exponent and homomorphic attacks (which also apply when $$H(x)=3x\bmod N$$).

This could of course raise the question "why, do we need this stronger assumption?". And the main reason is that the "RSA problem" - extracting $$x$$ from $$x^e\bmod N$$ for appropriately chosen $$N$$ and $$e$$ - isn't always hard. It is only hard when $$x$$ is chosen uniformly at random, which is kind of what the hash function is supposed to do here.

Let me note that no particular function is a random oracle. Rather the assumption is that the function can be simulated by a random oracle.

It is indeed important to know which particular hash function might be safely used.

I think the major missing piece is that a cryptographic hash function not only needs to be collision-resistant but also one-way. The given example $$x \mapsto 3x$$ is not one-way.