Create a new signature from existing DSA signatures

anand

11/14/23, 1:26 AM

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

224

1 + 3

DannyNiu

11/14/23, 2:48 AM

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

anand

11/14/23, 3:09 AM

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

Marc Ilunga

11/14/23, 7:11 AM

@anand, is the question also for when the message-signature pair remains valid for a new adversary generated key pair?

Score:4

Crypto

fgrieu

11/14/23, 6:46 AM

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

+ 1

anand

11/14/23, 6:35 PM

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?"

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Create a new signature from existing DSA signatures

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.