Entropy handling

[Kixunil]

When it comes to signing, today we have these methods:

• schnorr_sign which currently means "please use fast, perhaps less-secure RNG" and requires std
• schnorr_sign_with_aux_rand (or _with_rng) which supplies specific entropy externally
• chnorr_sign_no_aux_rand which requests no auxiliary entropy to be added

Similarly we have "please use fast, perhaps less-secure RNG" for key generation (!) and MuSig nonce generation (!!).

However, there are other valid cases:

• "I want the RNG to be secure, regardless of speed" - needs to use OsRng and curiously only needs getrandom, not std.
• "I want fast RNG, if available, slow otherwise" - use different RNG based on std availability
• "Use any auxiliary entropy if available, fine to not use it" - std | getrandom -> use any RNG, ignore if unavailable
• "I want some kind of default policy selectable via cfg"
• "I want auxiliary entropy but only if it's fast"
• Probably more

Arguably, there are many combinations and it might be unreasonable to support all of them (people can do it anyway) but it feels like we ought to at least support some variation of getrandom+no_std.

These two seem natural to me:

• new_slower_more_secure (or should this be the default and the other called _fast_less_secure?) - this both supports no_std and asks for a more secure implementation
• sign_schnorr_maybe_slower - asks to use some entropy, acknowledging that it might be slow

Or perhaps security-oriented approach: just use secure entropy for key generation and MuSig nonce generation, and use faster for signing if available, let people deal with the other cases on their own. I think this makes sense since signing/key derivation is slower than OS RNG (which I heard is quite fast these days with specially optimized OS calls). This is a breaking change but likely worth it.

[apoelstra]

I think we should have a non-sealed AuxExtropyProvider trait with a method that yields a [u8; 32]. We would provide several implementations of it (e.g. NoEntropy, FixedEntropy, JitterEntropy, and StrongEntropy (which would require getrandom).

We could also use this in the rerandomness API in #806 -- though if you have time to review that, I'd prefer we get it in with the existing API and then iterate in followups, so that we don't leave that PR open forever since it has difficult synchronization logic in it and we'll struggle to get review on that.

Then we'd just have a single signing method.)

[apoelstra]

For key generation I think we should continue to require a rand::CryptoRng. We can implement that trait for StrongEntropy so people can consistently use that type for all their randomness needs, if they want.

[Kixunil]

Good idea to have a trait for RNGs that are used specifically for entropy that is only used for defense against side channel attacks.

For key generation, yes, CryptoRng, is right but for functions in the form of Foo::new() (without arguments), if we ever want those (currently they take an RNG) it wouldn't be that clear. Maybe just keeping it as-is is best.

And sure, this is non-urgent.

[apoelstra]

for functions in the form of Foo::new() (without arguments)

I guess you mean, like SecretKey::new() or Keypair::new() which would generate a uniformly random key? I think the obvious thing would be for them to use StrongEntropy internally (which we would document in their doccomments of course).

[Kixunil]

What do you mean by "Strong" though? Both thread_rng and OS RNG generate unpredictable unbiased bits but thread RNG has the vulnerability that if you do fork() and then not reseed after fork you'll get same numbers but also this same thing applies if you make a snapshot of running VM and then restore it - and this specifically is deadly for MuSig (but might be fine for keys sometimes - it depends).

[apoelstra]

The StrongEntropy that we provide would use OsRng if it was available, and otherwise thread_rng I think. My view is that we should make an effort to help with fork protection, but we shouldn't bend over backward for it. If a user of this library is writing crypto code that forks, there are a ton of places where they need to be extremely careful. And in general, the Rust language and ecosystem aren't going to help them.

(There are stdlib issues about similar things where the outcome was basically "the user needs to use unsafe code to fork, and we won't/can't design in a way that would notice that, so they are on their own.)

Also, as you observe, if the user is running crypto code in a VM or any other machine whose full state can be cloned, they are vulnerable to attacks like this and there is literally nothing we can do from a software POV to help with it.

Maybe we should always try to mix in a bit of CPU jitter, which has a reasonable chance of being independent even after VM forks. This crate has some measurements that suggest that you can get 4-6 bits of entropy on a commodity PC from a single ~200ns hash function. So we could get 128 after 32 hashes, which would take 6us. For reference -- signing takes around 30us, and rerandomization takes another 30us. During signing and keygen we have already accepted a ~100% perf hit, at least by default, for purposes of rerandomization. I don't think anyone would be upset by another 10%. (We could provide cfg flag and/or an alternate API for people who really care about this. Either one can be done post-1.0 so it's not a priority for me til somebody complains.)

Obviously I wouldn't trust such sketchy analysis if it were my only source of entropy (although for context rerandomization, where we really only need a few bits, I would!). But as a def

[Kixunil]

OsRng if it was available, and otherwise thread_rng I think

As I understand it the availability of thread_rng implies OsRng.

we should make an effort to help with fork protection, but we shouldn't bend over backward for it

To me slowing down the RNG a bit is exactly in line with this idea. We still have the explicit API if someone needs to do it the other way around. (And crypto operations will be slow anyway.)

there is literally nothing we can do from a software POV to help with it

As I understand it the VMs have a way to notify the OS that clone happened and it needs to reseed so just using OsRng gets us protection out of the box on things that support this and if something doesn't we're likely out of luck anyway.

[apoelstra]

As I understand it the availability of thread_rng implies OsRng.

Ok, great, that simplifies things. Then I think we agree that we should always use OsRng.