# Preimage resistance hash in digital signature

I'm studying about preimage resistance property of the hash functions. In particularly I'm reading as the missing of this property can be fatal in digital signatures that use RSA.

Further details:

Let $e$ be the public exponent, $d$ the private exponent and $n$ the modulus.

Let be C the attacker.

C could compute:

$y= z^e \mod n$ with $z$ random number, then he could find a $m'$ for the which $h(m') = y$ and finally to state that Bob has sent {$m'$, $z$} where $m'$ is the message and $z$ is the digital signature.

Here my doubts:

C could choose $m'$ if he could compute: $h(m') = y$ (the compute is easy, suppose that h is public) and resolve this equation; $\log_x y = e$ (there is also $\mod n$ in this equation). This problem seems similar to discrete logarithm but it is different. In this case the unknown is the logarithm base.

I think that this problem is computationally intractable, do you confirm?

• Hi,thanks for your answer. I'm a student, I started to study Security a week ago, so I don't think to be able to find attack. However, Can you say what is wrong in my argument? Attacker would like to state that Bob has signed $m'$, so compute $y = z^e \mod n$ ($z$ random ),then he finds a $m'$ such that $h(m') = y$. C states "BOB you have sent ${ m', z }$ , you have signed $m'$ with $z$ ! " – Edge7 Jun 12 '13 at 7:45
• Let's see if C is right: Since the digital signature,for a generic message $k$ is in the form: $H(k)^d \mod n$ where $d$ is the exponent of BOB we will have in our case: $H(m') ^d \mod n = y ^d \mod n = (z^e \mod n) ^d \mod n = z$ . So we can conclude that because hash function $h()$ is not preimage resistance Bob was screwed. – Edge7 Jun 12 '13 at 7:50
• C to make the attack is started from computing $y = z^e \mod n$ and then finds $m'$ such that.. My question is C can start from $m'$ and compute $z$ such that $y = z^e \mod n$ fixed $y = h(m')$ ? Thanks and sorry for my bad explaining and my bad English – Edge7 Jun 12 '13 at 7:56
• $z$ in less than $n$ ! I missed to write this, sorry. – Edge7 Jun 12 '13 at 8:05
• [revised, earlier comment was seriously bad] Not a perfect answer. Hint: how is the message $m$ to sign transformed into $y$, then the signature $z$? If the hash function is not collision resistant, what does that imply the adversary can do? How does that help in her goal: exhibiting the signature of some message, and that message, different from messages for which she has legitimately obtained signature? Bonus points if you can find an (elaborate) attack working for SHA-1 or RIPEMD-160 as the hash, even though they are collision-resistant in practice. – fgrieu Jun 12 '13 at 8:07

If C can compute pre-images on $H$, then he can forge digital signatures from Bob. All C needs is one signature from Bob.
Bob signs message $m$, the signature is $S={H(m)}^d\bmod n$. All C needs to do is find an $m'$ where $H(m)=H(m')$. The forged message and signature will be $m'$ and the original $S$.
• Yes; but notice that the signature scheme $S={H(m)}^d\bmod n$ succumbs to multiplicative forgery under chosen-message attack even for some $H$ that are collision-resistant, e.g. when $H$ is SHA-1 or RIPEMD-160! A proper signature scheme with appendix is more like $S={\mu(H(m))}^d\bmod n$ where the padding function $\mu$ somewhat spreads its input over the full domain $[0\dots n-1]$. – fgrieu Jun 13 '13 at 6:06
• Yes, a collision-resistant $H$ is required even with a proper scheme using a padding function $μ$. My remark was that $S={H(m)}^d\bmod n$ is an inadequate scheme for some collision-resistant $H$. – fgrieu Jun 13 '13 at 13:32