2
$\begingroup$

Is it possible to generate a new valid signature for some arbitrary message using DSA if we know existing signatures for the same message? We are an adversary, therefore we do not hold the private key, but we have access to a couple of signatures for the same message, say $(r_1, s_1)$, $(r_2, s_2)$.

$\endgroup$
3
  • 3
    $\begingroup$ @MaartenBodewes They said "for the same message". For ECDSA, you can output $(r, -s)$ as a valid second signature; I'm not sure if the same "feature" is present with finite field DSA. $\endgroup$
    – DannyNiu
    Nov 14, 2022 at 2:48
  • $\begingroup$ @DannyNiu That's exactly what I meant, an alternate signature for the same message. It is not a security breach either, given that the owner of the key has already signed the message. $\endgroup$
    – anand
    Nov 14, 2022 at 3:09
  • $\begingroup$ @anand, is the question also for when the message-signature pair remains valid for a new adversary generated key pair? $\endgroup$ Nov 14, 2022 at 7:11

1 Answer 1

4
$\begingroup$

As far as we know, no, it's not possible to generate a new valid DSA signature from existing ones (for given public key), even for an already signed (known) message (assuming secure choice of parameter and hash). DSA is believed secure under sEF-CMA. But I don't know a proof of that.

ECDSA is EF-CMA, but not sEF-CMA: we can turn a signature $(r,s)$ into $(r,n-s)$ which is a different signature valid for the same message. When that's an issue, it can be fixed by forcing $s$ to be in $[1,n/2)$, or forcing $s$ to be even in $[1,n)$.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer. I now understand that a better phrasing for my question could have been - "Is DSA secure under sEF-CMA/Does DSA satisfy sUF-CMA?" $\endgroup$
    – anand
    Nov 14, 2022 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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