3
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\begingroup$ Does the statement allow the attacker to choose $m$ or/and $m'$? With what constraints? $\endgroup$
    – fgrieu ♦
    Jul 15, 2014 at 9:36
  • $\begingroup$ Apparantly, m is given and fix, but m' can be chosen. I updated the question. $\endgroup$
    – stefanbschneider
    Jul 15, 2014 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, 2014 at 17:23
  • $\begingroup$ Ok, new approach. I updated the question, please have a look. $\endgroup$
    – stefanbschneider
    Jul 16, 2014 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, 2014 at 13:19

1 Answer 1

Reset to default
1
$\begingroup$

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?

Improve this answer
$\endgroup$
3
  • 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, 2014 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$
    – stefanbschneider
    Jul 17, 2014 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, 2014 at 9:34

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.