Join Log in
Score:3
ostrich avatar Crypto

Given multiple incomplete ECDSA signatures, what can a quantum attacker learn in the following scenarios?

US flag
ostrich

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.

Let's analyze four threat models involving a quantum attacker:

  1. They obtain 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. Also, they don't know that the signatures were produced with the same private key.

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

    1.2. What can the attacker compute (message, public key, private key)?

  2. The same model as in the first question, but they know that the same private key was used for all incomplete signatures. What can the attacker compute?

  3. The same model as in the first question, but they know all the messages and know which incomplete signature corresponds to which message.

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

    3.2. What can the attacker compute?

  4. The same model as in the third question, but they know that the same private key was used for all incomplete signatures. What can the attacker compute?

Edit1: Added the detail about the signing being fully deterministic.

Edit2: Following @DannyNiu's advice, I merged my other similar questions 104193 and 104194 into this one. The original question was the second one, with the difference that the attacker obtained the full signatures.

113
2 + 0
Score:4
poncho avatar Crypto
my flag
poncho

They obtain the first 32 bytes of each signature.

All your scenarios make this assumption, and so lets dig into it.

For ECDSA with RFC-6979, it gets the message and the private key, and generates the first 32 bytes are $F( message, privatekey ) $, where $F$ is a public and noninvertible function; that is, by knowing the output, you cannot reconstruct the message (or even the hash of the message) or the private key; this holds true even for your hypothetical quantum attacker. You cannot even, two outputs of $F$, determine how the inputs were related (unless, of course, on an exact duplicate).

With that, we can make short work of your questions:

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

If two of the signed messages happened to be the same and they were signed by the same key, then that will be obvious (as the two signatures will, of course, share the same 32 bytes). Otherwise, no; $F$ doesn't allow such testing.

1.2. What can the attacker compute (message, public key, private key)?

No; $F$ doesn't leak anything

  1. The attacker knows the same private key was used. What can the attacker compute?

Same answer; nothing.

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

No; $F$ doesn't leak that.

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

No, $F$ doesn't leak that

  1. They know that the same private key was used for all incomplete signatures. What can the attacker compute?

Nothing; $F$ doesn't leak any information.

Now, all this assumes that the attacker doesn't somehow guess the private key - if he does, then he can test guesses of the messages.

+ 5
ostrich avatar
md
ostrich
thank you! I'll mark this as the solution if it doesn't receive refutations for a while.
0
Reply
ostrich avatar
md
ostrich
Does this using deterministic ECDSA change this? I forgot to mention that my question is in that context (now edited).
0
Reply
poncho avatar
my flag
poncho
@ostrich: no, it does not change the answer (with the obvious exception that if the same message is signed twice , that fact will be obvious). The mapping between message to $k$ is indistinguishable from random by someone who doesn't know the private key.
1
Reply
ostrich avatar
md
ostrich
Thank you for updating your answer and giving a solution to all the questions!
0
Reply
ostrich avatar
md
ostrich
I'd like to ask for some follow-up questions. 1. Using common sense, I suppose you use F to denote the hash function, in our case, SHA-256. However, RFC-6979 uses H for the same, which is confusing because you also use H later. Can you clarify this? 2. Can I ask you to make the grammar in your second sentence less ambiguous? 3. Is my intuition correct that the reason there are no leaks is that a quantum attacker can't gain an orders-of-magnitude speedup in trying to break the preimage-resistance of the hash function?
0
Reply
Score:1
DannyNiu avatar Crypto
vu flag
DannyNiu

Sorry, I missed the premise that message is unknown.

Can they compute either the messages, the private key or the public key?

While they can't compute the message (because it's behind the pre-image of a hash function), with ECDSA in particular, it's indeed possible to compute the private key (and to sign more messages).

ECDSA supports an operation known as "public key recovery". It's specified in section 4.1.6. of SEC #1 ver2.

After the public key is recovered, the quantum computer can then recover the private key using the Shor's algorithm.

+ 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

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.