3
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ thank you! I'll mark this as the solution if it doesn't receive refutations for a while. $\endgroup$
    – ostrich
    Commented Feb 12, 2023 at 18:51
  • $\begingroup$ Does this using deterministic ECDSA change this? I forgot to mention that my question is in that context (now edited). $\endgroup$
    – ostrich
    Commented Feb 13, 2023 at 6:24
  • 1
    $\begingroup$ @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. $\endgroup$
    – poncho
    Commented Feb 13, 2023 at 14:10
  • $\begingroup$ Thank you for updating your answer and giving a solution to all the questions! $\endgroup$
    – ostrich
    Commented Feb 20, 2023 at 21:42
  • $\begingroup$ 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? $\endgroup$
    – ostrich
    Commented Feb 25, 2023 at 3:58
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0

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.