1
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ 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$ ! " $\endgroup$
    – Edge7
    Jun 12, 2013 at 7:45
  • $\begingroup$ 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. $\endgroup$
    – Edge7
    Jun 12, 2013 at 7:50
  • $\begingroup$ 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 $\endgroup$
    – Edge7
    Jun 12, 2013 at 7:56
  • $\begingroup$ $z$ in less than $n $ ! I missed to write this, sorry. $\endgroup$
    – Edge7
    Jun 12, 2013 at 8:05
  • $\begingroup$ [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. $\endgroup$
    – fgrieu ♦
    Jun 12, 2013 at 8:07

1 Answer 1

Reset to default
1
$\begingroup$

I'm having a hard time parsing your question.

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$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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]$. $\endgroup$
    – fgrieu ♦
    Jun 13, 2013 at 6:06
  • $\begingroup$ u(H(m))^d == u(H(m'))^d $\endgroup$
    – user7236
    Jun 13, 2013 at 12:42
  • $\begingroup$ 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$. $\endgroup$
    – fgrieu ♦
    Jun 13, 2013 at 13:32
  • $\begingroup$ Meh, semantics. $\endgroup$
    – user7236
    Jun 13, 2013 at 23:37

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.