Score:3

two closely distanced ECDSA keys

yt flag

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

kelalaka avatar
in flag
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?
Sean avatar
yt flag
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?
kelalaka avatar
in flag
If you sign a message two times with the two keys using different nonces, then this can give information about the distance of nonces.
Sean avatar
yt flag
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?
Score:1
es flag

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

poncho avatar
my flag
"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...
poncho avatar
my flag
No, Big-Step-Little-Step just involves additions...
knaccc avatar
es flag
@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.
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.