Score:1

Crypto

Can a quantum attacker prove that incomplete ECDSA signatures were produced with the same key?

ostrich

2/12/24, 7:19 PM

Assume a 256-bit ECDSA private key used with Secp256k1 and SHA-256. This key signs multiple different messages in a fully deterministic manner as described in RFC-6979, so signing the same message always produces the same signature.

A quantum attacker obtains the first 32 bytes of each signature. However, the rest of each signature, the messages, the private key and the public key remain concealed from them.

Can the attacker prove that the signatures were produced with the same private key?

(This is a modification of my previous question: "Given multiple ECDSA signatures with the same key, what can a quantum attacker learn?")

1 + 0

elliptic-curves

quantum-cryptanalysis

secp256k1

Score:2

Crypto

poncho

2/12/24, 9:50 PM

Can the attacker prove that the signatures were produced with the same private key?

The first 32 bytes are the $r$ value; that's the x-coordinate of the value $kG$, where $k$ is a random value, selected independently of the key.

Because the keys in a partial signature are independent of the key, they don't leak any information about the key. This includes whether two different partial signatures were generated with the same key.

+ 8

DannyNiu

2/13/24, 4:30 AM

However, if it's a fully deterministic ECDSA, it allows us to infer which message(s) (whose contents're unknown) were being signed.

poncho

2/13/24, 4:32 AM

@DannyNiu: actually, unless they also had the private key, no, it wouldn't - deterministic ECDSA stirs in the private key with the message to generate $k$ (otherwise, just knowing the message would allow anyone to recompute $k$, which would be *bad*)

DannyNiu

2/13/24, 5:02 AM

But that allows observing $R=kG$, since in [RFC-6979](https://www.rfc-editor.org/rfc/rfc6979.html#section-3.3), only message hash and the private key are mixed in (and private key is static). Unless they've implemented the [newer IETF draft](https://www.ietf.org/archive/id/draft-irtf-cfrg-det-sigs-with-noise-00.html), where there's additional randomness

ostrich

2/13/24, 5:42 AM

@DannyNiu , Poncho, I apologize, I forgot to mention we are talking about fully deterministic ECDSA. I will update the question to reflect that.

poncho

2/13/24, 2:57 PM

@DannyNiu: since a quantum attacker was posited, they could already observe $k$ directly. In any case, I'm not sure what you mean; just because the attacker knows that there's a mapping from message to $k$ doesn't mean he knows what that is (and since he doesn't know the private key, he doesn't). And, this mapping is believed to be quantum-safe, and so a Quantum Computer doesn't help him there.

DannyNiu

2/13/24, 11:58 PM

@poncho To put it in simple (abbreviation) terms: deterministic ECDSA is Non-IND-CMA.

ostrich

2/14/24, 2:50 PM

@poncho Following DannyNiu's advice, I merged all questions into the first one as four related threat models. Can I ask you to edit your answer there (since now it doesn't exactly match the threat models outlined in the updated question) and merge this answer into it? Sorry about this. Once done, I will delete this question and my third one.

ostrich

2/20/24, 9:45 PM

I decided to keep this question. The conversation may be relevant to someone later.

Elon Musk

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

EN: Can a quantum attacker prove that incomplete ECDSA signatures were produced with the same key?

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.