Follow

It may have passed people by but I think gmax found something very dangerous here:

moderncrypto.org/mail-archive/

Let me condense it so it's more concrete:

(1) your hardware or software has a simple Schnorr style signing algo: take privkey x, message m, output a signature (R, s)

(2) Your nonce k in s = k + ex is generated deterministically (RFC6979, EdDSA). Think of it as k = f(x, m).

(3) Your e-value is a hash with pubkey prefix: e = H(P|R|m), P is pubkey P=xG.

(1/n)

Now, as an optimization, some code may choose to allow the user of the software (who is the signer, owning the privkey x), to pass in the public key P as an argument, instead of calculating it with slow EC multiplication. The reasoning is, if they pass in a wrong P, it's of no consequence, since they'll just create an invalid signature that is useless.

Wrong!
Use a fake P, call it P_1. use the algo to generate a "signature":

s_1 = k(x,m) + H(P_1|R|m)x

here R=kG, if I forgot to mention.

(2/n)

Show thread

Now remember this operation happens on a device or piece of software that knows x, but is constrained to just say generate signatures. So it outputs s_1, knowing x internally. As an attacker you want to steal knowledge of x.

So all you do is repeat the process with another fake P, P_2:

s_2 = k(x,m) + H(P_2|R|m)x

Notice that k didn't change - it's a function of privkey x and message m.

Now we have:
s_1 = k + e_1 x
s_2 = k + e_2 x

.. subtract one from the other, and you can derive x.

(3/n).

Show thread

So what went wrong? Basically we must never allow "nonce reuse" on a single private key. Many bitcoins were lost in the early days because of that mistake. And that attack is fundamental to the Schnorr protocol and all variants including ECDSA that use a "commit, challenge, response" (or 'sigma protocol') design.

Here, the deterministic nonce generation failed in its purpose, which is twofold:
the k value should be unguessably random
the k value must never repeat for different signatures
(4/n)

Show thread

Further into the autopsy: but why did the k value repeat whereas usually it doesn't? Because it's assumed in making k a function of x and m, that the inputs to the signing algo are x and m (the private key and the message), but we have changed the signing algo to take the public key as an input (for speed optimization). So it must be added to what is to be hashed.

By changing to k = f(x, m, P) the problem is solved.

More discussion: github.com/sipa/bips/issues/19

(5/5 maybe)

Show thread

@waxwing re: lost btc due to nonce reuse. Any examples? I vaguely recall that blockchain.info lost user funds due to reused R values many years ago. Are there others that made this mistake as well?

@htimsxela memory is vague but there was more than one incident of nonce bad randomness causing this. One was based on Mersenne twister in a java lib, another was the random.org call failing (lol), there were more. See recent Nadia Henninger paper, there were also cases using short 2^-1 G point, and cases involving truncation of randomness (Ryan X Charles involved in a f up there). There were people running real time scripts to sweep funds from the most obvious case (direct reuse).

Sign in to participate in the conversation
unidentified instance

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!