<p>This question was answered by Tim Ruffing on <a href="https://twitter.com/real_or_random/status/1336342555336736768?s=20" rel="nofollow noreferrer">Twitter</a>.</p>
<blockquote>
<p>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 &quot;test&quot; that checks if your numbers
are really random.</p>
<p>Broken random number generators have led to numerous real-world
failures e.g.</p>
<p><a href="https://www.schneier.com/blog/archives/2008/05/random_number_b.html" rel="nofollow noreferrer">https://www.schneier.com/blog/archives/2008/05/random_number_b.html</a></p>
<p>and</p>
<p><a href="https://arstechnica.com/information-technology/2013/08/google-confirms-critical-android-crypto-flaw-used-in-5700-bitcoin-heist/" rel="nofollow noreferrer">https://arstechnica.com/information-technology/2013/08/google-confirms-critical-android-crypto-flaw-used-in-5700-bitcoin-heist/</a></p>
<p>So it's better to simply avoid real random number generators in
practice, and this is well-established best practice for &quot;normal&quot;
single-singer signatures (Schnorr sigs, ECDSA). MuSig-DN makes this
possible for multisignatures, too.</p>
<p>But your point is correct in theory. If you have a working source of
truly random numbers, this will just do the job.</p>
</blockquote>
<p>Pieter Wuille and Jonas Nick added on <a href="https://twitter.com/pwuille/status/1336354130651037697?s=20" rel="nofollow noreferrer">Twitter</a>:</p>
<blockquote>
<p>A working source of random numbers <em>and</em> a place to keep them securely
and tamper-proof between the rounds of the signing process.</p>
<p>Or just a place, to keep a counter securely and tamper-proof between
the signing <em>sessions</em>. Ideally combined with an RNG.</p>
</blockquote>
<p>But that is also true for the generation of the private key and we tolerate that there?</p>
<blockquote>
<p>Perfectly right, yes.  I think the answer here is two-fold:</p>
<ol>
<li><p>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</p>
</li>
<li><p>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.</p>
</li>
</ol>
<p>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)?</p>
</blockquote>
<p>Diego Aranha added on <a href="https://twitter.com/dfaranha/status/1336352607598764036?s=20" rel="nofollow noreferrer">Twitter</a>:</p>
<blockquote>
<p>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</p>
</blockquote>
<p>And Akira Takahashi added on <a href="https://twitter.com/akiratk0355/status/1336419009932259332?s=20" rel="nofollow noreferrer">Twitter</a>:</p>
<blockquote>
<p>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.</p>
<p>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: <a href="https://ia.cr/2016/290" rel="nofollow noreferrer">https://ia.cr/2016/290</a>) and it should thwart the devastating rewinding attack on Schnorr multisig without ZKP.</p>
<p>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.</p>
</blockquote>

CC BY-SA 4.0
2020-12-09T15:39:21.510Z
2020-12-09T15:49:21.223Z
2020-12-09T15:49:21.223Z
Michael Folkson
<p>In <a href="https://youtu.be/n19vDaVrwY4?t=207" rel="nofollow noreferrer">MuSig-DN</a> 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.</p>
<p>This question was asked by emzy on <a href="https://twitter.com/emzy/status/1336341085233192967?s=20" rel="nofollow noreferrer">Twitter</a>.</p>

<schnorr-signatures><random><musig>
In MuSig-DN why not use a truly random number for the nonce instead of a pseudorandom function?
Michael Folkson
# In MuSig-DN why not use a truly random number for the nonce instead of a pseudorandom function?

(Asked by: username_0 on 2020-12-09)

In [MuSig-DN](https://youtu.be/n19vDaVrwY4?t=207) 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](https://twitter.com/emzy/status/1336341085233192967?s=20).

**Tags:** schnorr-signatures, random, musig


---

## 1 answers

### Answer by username_0 on 2020-12-09. Score: 2 | Accepted answer

This question was answered by Tim Ruffing on [Twitter](https://twitter.com/real_or_random/status/1336342555336736768?s=20).

> 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](https://twitter.com/pwuille/status/1336354130651037697?s=20):

> 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](https://twitter.com/dfaranha/status/1336352607598764036?s=20):

> 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](https://twitter.com/akiratk0355/status/1336419009932259332?s=20):

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


---

