# two closely distanced ECDSA keys

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

• 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? Feb 12, 2022 at 21:02
• 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?
– Sean
Feb 12, 2022 at 22:28
• If you sign a message two times with the two keys using different nonces, then this can give information about the distance of nonces. Feb 13, 2022 at 0:14
• 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?
– Sean
Feb 13, 2022 at 0:42

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

• "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... Feb 13, 2022 at 4:21
• No, Big-Step-Little-Step just involves additions... Feb 13, 2022 at 17:02
• @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. Feb 13, 2022 at 20:44