3
$\begingroup$

Assume that one uses two private keys $x_1$ and $x_2$ to generate two public ECDSA keys $y_1$ and $y_2$ (e.g., used as public key for Bitcoin address). The distance between $x_1$ and $x_2$ is small (e.g., less than ${2^{20}}$). What's bad about it?

I know that if one breaks $x_1$, it certainly leads to the breaking of $x_2$ with a small effort search. But let's assume that except $|x_1 - x_2|$ is a small number all other practices are secure e.g. never reuse randon nonces in signing, are there any other bad outcomes of it (except breaking one coin is like breaking two)?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The main attack on the signature is the forging signatures. There is also a total failure that the attack reveals the key. What else do you want? $\endgroup$
    – kelalaka
    Feb 12, 2022 at 21:02
  • 1
    $\begingroup$ Let's say given an existing signature which is generated using $x_1$. How could the attacker forge another (as generated using $x_2$) if not knowing the random nonce used in the first signature? $\endgroup$
    – Sean
    Feb 12, 2022 at 22:28
  • $\begingroup$ If you sign a message two times with the two keys using different nonces, then this can give information about the distance of nonces. $\endgroup$
    – kelalaka
    Feb 13, 2022 at 0:14
  • $\begingroup$ But if you sign the same message using the same key, wouldn't that be disclosing distance of nonces as well (even worse?) --- So, what if one never signs the same message a second time? $\endgroup$
    – Sean
    Feb 13, 2022 at 0:42

1 Answer 1

Reset to default
1
$\begingroup$

Let $d=x_2-x_1$, and let the public keys be on the well-known base point $G$. Therefore, the key-pairs will be $(x_1, X_1=x_1G)$ and $(x_2, X_2=x_2G)$.

The value $d$ can be brute-forced using the Big-Step-Little-Step method, which will take less than a second on a modern CPU when $n=20$.

If you use a Schnorr signature to sign a message $m$ using $X_1$, you would create the signature pair $(c, r_1)$ by picking a uniformly random nonce $k$, and then calculating $c=H(kG\mathbin\| m)$ and $r_1=k-cx_1$.

The signature is verified by checking $c\overset{?}{=}H(r_1G+cX_1 \mathbin\| m)$.

The attacker, who has brute-forced $d$, can then create a signature on the same message but appearing to be signed by your other private key $x_2$, as follows:

The values of $k$ and $c$ would remain the same. Then calculate $r_2=r_1-cd$. The forged signature is the pair $(c, r_2)$.

The signature will be verified by checking that $c\overset{?}{=}H(r_2G+cX_2 \mathbin\| m)$.

This will successfully verify if $kG==r_2G+cX_2$, which will be true if $k==r_2+cx_2$.

By substituting $r_2==r_1-cd$ and $x_2==d+x_1$, we can see that this will be true thanks to our choice of $r_2$.

This attack only works if the hash or message does not bind the signature to a particular public key. If the protocol required that $c$ was instead calculated as $c=H(kG\mathbin\| X_1\mathbin\| m)$, the attack would not work because the value of $c$ could not be re-used between signatures (because the verifier would verify the signature by concatenating $X_2$ inside the hash instead of $X_1$).

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ "According to the question, this will take no more than $2^{21}$ attempts, which will take less than an hour on a modern CPU."; actually, it can be done with circa $2^{11}$ attempts (say, by using Big-Step-Little-Step); that's more like a second... $\endgroup$
    – poncho
    Feb 13, 2022 at 4:21
  • $\begingroup$ No, Big-Step-Little-Step just involves additions... $\endgroup$
    – poncho
    Feb 13, 2022 at 17:02
  • $\begingroup$ @poncho Thanks, I was confused at first, but now I can see that the insight is that a hashtable lookup is much faster than performing an addition. I've implemented your method to test it, and it works very well. $\endgroup$
    – knaccc
    Feb 13, 2022 at 20:44

Your Answer

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

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