1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SEJPM Aug 25 at 16:58
  • $\begingroup$ Interesting... so even if it is a collision resistant hash, one could still forge a message? How is that even possible? $\endgroup$ – Yusuf Mohamedillahy Aug 25 at 17:22
  • $\begingroup$ 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. $\endgroup$ – SEJPM Aug 25 at 17:57
  • $\begingroup$ Welcome to Crypto.SE! By collision resistant you mean in case where we restrict $x$ to $\{0,\ldots, N-1\}$? $\endgroup$ – Marc Ilunga Aug 26 at 18:24
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.