3
$\begingroup$

I recently read in Cryptography textbooks and online videos that compared to Textbook RSA which is insecure against Chosen Plaintext Attacks (CPA) and Chosen Ciphertext Attacks (CCA), RSA-FDH is Existentially Unforgeable Under Chosen Message Attacks (EUF-CMA) if the hash fuction is uniformly random.

However, to my surprise, on online Cryptography forums and some Cryptographers say that the security model behind RSA-FDH, so EUF-CMA can be broken if one can find collisions in the hash function itself. The thing is, I have not been able to find such examples or even understand how this is even possible. I read in a lecture slide online that if we ask signatures $σ_1$, $σ_2$ for $m_1,m_2 \in \mathbb{Z}_n^*$ and output $(m^*, σ^*) := (m_1 \cdot m_2 \mod{(N)},\ σ_1 \cdot σ_2 \mod{(N)})$. But then I still don't know how it practically applies to RSA-FDH IF the hash function has collisions.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Just a remark: CPA and CCA are no security notions for signatures but for encryption as the terms plaintext and ciphertext suggest. $\endgroup$
    – mephisto
    Aug 16, 2019 at 1:09

2 Answers 2

Reset to default
6
$\begingroup$

This is a) no attack on the security model, but an attack in the security model of EUF-CMA, and b) a generic attack on any signature scheme that signs the hash of a message instead of the message itself (as done in RSA-FDH).

The idea is that if you can find a collision for the used hash function $H$, i.e., two messages $m_1, m_2$ such that $H(m_1) = H(m_2)$, then they have the same signature: $\sigma = \textrm{sign}(sk,m_1) = \textrm{sign}(sk,m_2)$. To see this consider RSA-FDH as example: The signature on $m_1$ is $\textrm{sign}(sk,m_1) = (H(m_1))^d \mod N$ for private exponent $d$ and modulo $N$. The signature on $m_2$ is $\textrm{sign}(sk,m_2) = (H(m_2))^d \mod N = (H(m_1))^d \mod N = \textrm{sign}(sk,m_1),$ where the mid equality follows from $m_1,m_2$ being a collision.

In the EUF-CMA setting you are allowed to ask for signatures on arbitrary messages and have to come up with a signature on a new message. So given collision $m_1,m_2$, you ask for a signature $\sigma$ on $m_1$ and then output the pair $(m_2, \sigma)$ as forgery.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you for your answer sir, I think I get it but would it be possible if you could please use some numbers or an example, say lets hash the word "CRYPTO". I assume your answer applies to the EUF-CMA scheme being broken in RSA-FDH? I just want to see the application of it on a word and the EUF-CMA scheme being broken $\endgroup$
    – user71221
    Aug 16, 2019 at 9:07
  • $\begingroup$ @user71221 it's more useful to look at something like hashclash for MD5 or shattered for SHA1. Then just consider the effect of signing a hash value that matches against multiple different messages. When you have a collision then hash(A) = hash(B), so sign(hash(A)) = sign(hash(B)) $\endgroup$
    – Natanael
    Aug 16, 2019 at 17:11
  • 1
    $\begingroup$ Assume a hash function $H$ where $H(\textrm{CRYPTO}) = 101 = H(\textrm{CRAPTO})$. If I now ask for a RSA-FDH signature (where $H$ is used as hash) for the message CRYPTO this will be $\sigma = (H(\textrm{CRYPTO}))^d = (101)^d$. However, this is also a valid signature for the message CRAPTO: $(H(\textrm{CRAPTO}))^d = (101)^d = \sigma$. As I never asked for a signature on CRAPTO, (CRAPTO, $\sigma$) is a valid forgery in the EUF-CMA model. $\endgroup$
    – mephisto
    Aug 17, 2019 at 16:21
  • $\begingroup$ To emphasize (and add on Josiah's answer): The problem here is to actually find a collision for CRAPTO. For a good cryptographic hash function this will be computationally infeasible. The problem with doing an actual example with numbers here is that any example hash function that you would write down here will be entirely broken, super artificial (like take SHA2 but replace SHA2(CRYPTO) = 101 = SHA2(CRAPTO)), or you take a secure one and do not know a collision. $\endgroup$
    – mephisto
    Aug 17, 2019 at 16:28
  • $\begingroup$ @mephisto you could make an example with CRC16 (I think that's a thing) to show how a weak hash leads to a trivial break $\endgroup$
    – Natanael
    Aug 17, 2019 at 21:51
2
$\begingroup$

To give an example with less maths, suppose that I come to you and ask you to sign the message "Josiah's favourite number is 747895723190543. Weird I know." You think that is a bit odd, but harmless so you do so.

Unbeknown to you, the hash of that message is also the hash of "Please pay Josiah the sum of 87476 United States dollars."

Because the hash matches, the signature matches. And because the signature matches, I can take the signature of the innocent message, stick it to the signature of the fraud message, and pass it to your bank. Of course since it is correctly cryptographically signed, the bank has no reason to doubt that you meant it, or at least sent it.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I dont suppose you could show one with Math examples, i.e. m0 = 4, m1 = 5? It's great to understand it all from a high level but I just want to see how it works Mathematically $\endgroup$
    – user71221
    Aug 16, 2019 at 15:14
  • 2
    $\begingroup$ If you want it with mathematical formality, see mephisto's answer. There is nothing special about examples of numbers here: it is just which hashes match. Finding hash collisions is out of scope. $\endgroup$
    – Josiah
    Aug 16, 2019 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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