Given a (bad) modification of DSA where the hash function is the identity ($H(m)=m$), I am now supposed to design an attack. So $(m, (r,s))$ are given and I should be able to create a legit signature $(r',s')$ for a chosen $m'$ (of course $m'\neq m$).

Since retrieving the private key $x$ doesn't work. My new approach is to choose $m'$ as a modification of $m$ such that $m'=t \cdot m$. Then I want to calculate $(r',s')$ to be a legit signature of $m'$. So I was doing the verification step with $m'$ in order to see how to modify $r'$:

$v'=g^{m' \cdot w} y^{r \cdot w}=g^{m' \cdot w + xrw} \mod q$ now $v'$ is supposed to equal $r'$. This means $g^{m' \cdot w + xrw}=g^k$ so $m'w+xrw=k$. But I can't just choose k, can I (because it's already $k=mw+xrw$ ? And I don't know to modify $r$ in order to make this work...

  • $\begingroup$ Does the statement allow the attacker to choose $m$ or/and $m'$? With what constraints? $\endgroup$ – fgrieu Jul 15 '14 at 9:36
  • $\begingroup$ Apparantly, m is given and fix, but m' can be chosen. I updated the question. $\endgroup$ – CGFoX Jul 15 '14 at 15:46
  • 1
    $\begingroup$ "Apparantly, I'll have to calculate the private key $x$" -- nope, recovering the private key is not required. $\endgroup$ – poncho Jul 15 '14 at 17:23
  • $\begingroup$ Ok, new approach. I updated the question, please have a look. $\endgroup$ – CGFoX Jul 16 '14 at 9:26
  • $\begingroup$ @CGFoX: If for any $t$ you could forge the signature for $m'=t\cdot m\bmod q$ in the weakened system, that would also break the real DSA [by choosing $t=H(m')\cdot H(m)^{-1}\bmod q$ and using the same attack]. You want to exhibit a narrower class of transformations $m'=f_t(m,r,s,p,q,g,y)$ for which an acceptable signature $(r',s')$ can be forged. $\endgroup$ – fgrieu Jul 16 '14 at 13:19

With my new idea I seem to solve the problem and answer my question, so I'll go ahead and post it as the answer. I choose the new $m'$ as $m'=t+m$ with $t>0$. Now the verification works like this:

$v'=g^{m'w} y^{rw}=g^{m'w+xrw}=g^{tw+mw+xrw}=g^{tw} \cdot g^k=r' \mod q$

So my new $r'=g^{tw}r=g^{ts^{-1}}r$

This means I can create a legit signature to any $m'=t+m$ which is $(r',s')=(g^{ts^{-1}}r, s)$. Correct?

  • 1
    $\begingroup$ Again, if for any $t$ you could forge the signature for $m′=t+m\bmod q$ in the weakened system, that would also break the real DSA [by choosing $t=H(m′)-H(m)\bmod q$ and using the same attack]. So no this does not cut it, and you need a narrower choice of $m$, of the form $m'=f(m,r,s,p,q,g,y,t)$ for some $f$; and it won't be possible to find $t$ to obtain a chosen $m'$. The mistake in the argument given is that it is assumed $s$ does not change, rather than proven that with $s$ unchanged the verification procedure will pass with the $r'$ that you propose; indeed the verification will fail. $\endgroup$ – fgrieu Jul 17 '14 at 5:50
  • $\begingroup$ Thanks for your comment, but I'm afraid I don't know what to do now. How am I supposed to find a $m'=f(m,r,s,p,q,y,t)$? Also I will have to hand this in in a few hours, so I would be extra thankful for some quick help. (I will still appreciate it later, too.) $\endgroup$ – CGFoX Jul 17 '14 at 7:46
  • 1
    $\begingroup$ Write down the main equation used by the verifier for testing that $(m,r,s)$ is an acceptable signature in the weak system. The valid signature gives known values satisfying that equation. Your goal is finding $(m',r',s')$ with $m'\not\equiv m\pmod q$ which keeps the equation satisfied. What's $g^q\bmod p$? $y^q\bmod p$? What kind of changes does that allow while maintaining the equation satisfied? Perhaps replacing $s$ with $w=s^{-1}\bmod q$ in the equation (and $s'$ with $w'=s'^{-1}\bmod q$) will help you finding the appropriate changes. $\endgroup$ – fgrieu Jul 17 '14 at 9:34

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.