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?
$\begingroup$
$\endgroup$
4
-
$\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$– SEJPMAug 25, 2019 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 MohamedillahyAug 25, 2019 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$– SEJPMAug 25, 2019 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 IlungaAug 26, 2019 at 18:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
