2

In MuSig-DN why not use a truly random number for the nonce instead of a pseudorandom function (PRF)? If the nonce space is big enough it would never be reused.

This question was asked by emzy on Twitter.

2

This question was answered by Tim Ruffing on Twitter.

The answer is simply that it's not easy to get truly random numbers right in practice. For example, you need to collect entropy in your system, and it's hard to write a "test" that checks if your numbers are really random.

Broken random number generators have led to numerous real-world failures e.g.

https://www.schneier.com/blog/archives/2008/05/random_number_b.html

and

https://arstechnica.com/information-technology/2013/08/google-confirms-critical-android-crypto-flaw-used-in-5700-bitcoin-heist/

So it's better to simply avoid real random number generators in practice, and this is well-established best practice for "normal" single-singer signatures (Schnorr sigs, ECDSA). MuSig-DN makes this possible for multisignatures, too.

But your point is correct in theory. If you have a working source of truly random numbers, this will just do the job.

Pieter Wuille and Jonas Nick added on Twitter:

A working source of random numbers and a place to keep them securely and tamper-proof between the rounds of the signing process.

Or just a place, to keep a counter securely and tamper-proof between the signing sessions. Ideally combined with an RNG.

But that is also true for the generation of the private key and we tolerate that there?

Perfectly right, yes. I think the answer here is two-fold:

  1. We can at least try to avoid real numbers as much as possible. Even for key generation, we can derive all keys from a single seed, and then we really rely on randomness only once in the life of a wallet for that seed

  2. It seems that the randomness is particularly brittle when it comes to nonces used in signatures. For example, if you fix a single bit in the nonce, then a few signatures may already be enough to derive the secret key.

And maybe my second point is not even a valid one. I don't know enough about the concrete attacks to tell if signatures become suddenly insecure when we fix a single bit in the secret key (instead of the nonce)?

Diego Aranha added on Twitter:

Your second point is valid when applied to nonces, but a lot more than a few signatures are needed for 1-bit bias (something like 2^60 for an attack of feasible complexity for secp256k1). Fixing bits of the private key should just reduce the key space

And Akira Takahashi added on Twitter:

Indeed, attacking 1-bit nonce bias of Bitcoin ECDSA is currently out of reach, but 2-bit bias is already exploitable given about one million signatures and 3-bit only requires several thousands (or even less if lattice attack works). Not sure how bad a biased private key can be.

A middle-ground solution would be to include some nonce as PRF input. This way, you retain security even if the nonce is not truly random (proof: https://ia.cr/2016/290) and it should thwart the devastating rewinding attack on Schnorr multisig without ZKP.

But just to be clear, this solution still breaks down once the honest signer reuses the nonce. Dealing with such a stateful scheme is annoying and this is why purely non-stateful solutions like MuSig-DN are preferred in practice.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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