Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
Does the statement allow the attacker to choose $m$ or/and $m'$? With what constraints? –  fgrieu Jul 15 at 9:36
    
Apparantly, m is given and fix, but m' can be chosen. I updated the question. –  CGFoX Jul 15 at 15:46
1  
"Apparantly, I'll have to calculate the private key $x$" -- nope, recovering the private key is not required. –  poncho Jul 15 at 17:23
    
Ok, new approach. I updated the question, please have a look. –  CGFoX Jul 16 at 9:26
    
@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. –  fgrieu Jul 16 at 13:19

1 Answer 1

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?

share|improve this answer
1  
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. –  fgrieu Jul 17 at 5:50
    
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.) –  CGFoX Jul 17 at 7:46
1  
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. –  fgrieu Jul 17 at 9:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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