Context randomization tracking issue

[apoelstra]

Consolidating discussion from #385 #386 #387. Tobin is proposing to re-randomize contexts, not just the global one, when they are created -- though naturally only if the rand feature is enabled. Our current situation is kinda weird -- for users of global contexts, we require they "opt out" of rerandomization by choosing the global-context-less-secure feature vs the global-context flag, while ordinary users must "opt in" by creating a context then explicitly calling randomize() on it.

A bit of context (hah):

• re-randomization is not free: it takes about as long as a signing operation (around 50us on a desktop computer)
• on the other hand, context generation is extremely expensive (multiple milliseconds on a desktop computer) so this is fine during context creation; but on the third hand, now that we are moving toward pre-computing all the tables, context creation will be nearly free, so the re-randomization would then be the bulk of the "create context" operation
• re-randomization of verification contexts is a no-op. This discussion is only about signing contexts

Here is my proposal:

1. We remove the global-context-less-secure feature; global-context enables the global context, and we rerandomize it on first use if rand is also enabled.
2. Similarly we randomize all signing contexts on creation, if rand is enabled
3. We also change sign() and sign_schnorr to rerandomize the context after each signing operation. We add a sign_no_rerandomize method to opt out of this
   1. This would nearly double signing time, although sipa points out that there is a theoretical way, with help from upstream, we could make the rerandomization 99%+ faster, by essentially only doing one bit of re-randomization per signature
   2. This would also force the signing API to take a &mut pointer to the context object, which really sucks.
4. We leave the rerandomize() methods in place but document that users have basically no reason to call them manually.

Alternate proposals:

• Leave the sign methods alone but add sign_randomize ones which also do the re-randomization
• Embed a mutex in our Context objects so that re-randomization can be done with normal non-mutable references. (May be OK with "fast re-randomization", almost certainly not with full re-randomization, which would basically cause parallel signing operations to be force-serialized.)

cc @TheBlueMatt @tcharding

See also bitcoin-core/secp256k1#881 (which is not the "one-bit rerandomization" idea, but is similar and has a similar effect).

See also bitcoin-core/secp256k1#1058 which will affect upstream's blinding logic.

[TheBlueMatt]

We remove the global-context-less-secure feature; global-context enables the global context, and we rerandomize it on first use if rand is also enabled.

SGTM, so global-context would then build with no-std + no-rand?

Similarly we randomize all signing contexts on creation, if rand is enabled

ACK

We also change sign() and sign_schnorr to rerandomize the context after each signing operation. We add a sign_no_rerandomize method to opt out of this

Maybe lets see what upstream does on this before we move?

We leave the rerandomize() methods in place but document that users have basically no reason to call them manually.

One general issue here is that users who build with no-std support will want to randomize regularly, but then if a downstream user turns on rand somehow, we'll end up randomizing twice. Maybe that's okay, but it feels quite wasteful.

[tcharding]

SGTM, so global-context would then build with no-std + no-rand?

I think this is going to end up requiring std. Can we put off sorting out the no-std thing until #359 is done? Does build with no rand.

Perhaps I'll push up a PR that does parts 1 and 2 since they are simple changes. Then we can nut out the rest along with the Once/std stuff?

EDIT: First two parts done in #385

[tcharding]

Also relevant is the original issue that brought this up: #225

[real-or-random]

* re-randomization of verification contexts is a no-op. This discussion is only about signing contexts

That's not true. All contexts except the no_precomp context are now effectively signing contexts. The no_precomp context is effectively a verification context, and name is misleading as no context uses dynamic precompuation now (see bitcoin-core/secp256k1#1065). You can sign with a "verification" or even "none" context (except no_precomp) now in upstream. That is, re-randomization of "verification" contexts is not a no-op. It's the same as re-randomization of signing contexts. The reason why no_precomp is different is that it's impossible to re-randomize it.

Note that this means that also the creation of "verification" contexts is expensive now. This is a regression introduced by the recent changes to make tables static (sorry!) but the actual problem is that we perform the entire (re-)randomization routine on context creation on constant input data (because context_create does not even have a randomness argument). In other we compute an expensive pure function on constant inputs every time a context is created. This was stupid for signing contexts and now it's stupid for signing and verification contexts. We should just initialize the blinding data with constants on context creation (again, see bitcoin-core/secp256k1#1065).

Similarly we randomize all signing contexts on creation, if rand is enabled

There's the idea to add a convenience function that randomizes on creation: bitcoin-core/secp256k1#780. If you're interested, it would be nice to PR to upstream and then we can call it here. (I admit that this is strictly more work that simply fixing it here.)

I somehow feel upstream can't provide the necessary bandwidth currently to match the bandwidth of changes here.

edit: I saw this issue very late because I unsubscribed from the repo. Please just @mention me when there are discussions relevant to upstream. I'm sure this is where I can help best.

[TheBlueMatt]

I think this is going to end up requiring std. Can we put off sorting out the no-std thing until #359 is done? Does build with no rand.

Fair, it is the case that it already doesn't work. The only thing they separate features accomplish today is lack of rand dependency, which it sounds like we'll keep.

[tcharding]

Optional runtime blinding which attempts to frustrate differential power analysis.

Is this what the re-randomization buys us? (quote from the readme of bitcoin-core/secp256k1)

[apoelstra]

Thanks for your input @real-or-random! I'm happy to PR to upstream to try to clean this up -- though I'd like to hold off until bitcoin-core/secp256k1#1058 is in so that I won't have a bunch of rebasing work to do.

Regarding upstream not keeping up with the pace of development here, I think the opposite is true :) but in any case I'm happy to propose changes upstream to simplify my life here.

Specifically, I will contribute upstream to

• Clean up the static context creation to not "rerandomize" constant data
• Add some sort of rerandomize_cheap function, using a suggested scheme from sipa

Then here (in rust-secp) I'd like to add a sign-then-rerandomize function. After discussion on IRC I'm not sure that I'd be able to get this into upstream, since they already have too many variants of signing functions :)

[tcharding]

Mad, I'll step back from this a bit then. I had a look at secp256k1 and its a bit above me without spending a whole bunch of time to come up to speed (I don't write C++).

[real-or-random]

Optional runtime blinding which attempts to frustrate differential power analysis.

Is this what the re-randomization buys us? (quote from the readme of bitcoin-core/secp256k1)

Yes!

Mad, I'll step back from this a bit then. I had a look at secp256k1 and its a bit above me without spending a whole bunch of time to come up to speed (I don't write C++).

No worries, it's just C. Just kidding.

Specifically, I will contribute upstream to

* Clean up the static context creation to not "rerandomize" constant data
* Add some sort of `rerandomize_cheap` function, using a suggested scheme from sipa

Sounds great.

Anyway, sorry for interrupting, I certainly don't want to stop any efforts here.

[tcharding]

No worries, it's just C. Just kidding.

I didn't get what 'Just kidding' meant here so I had to check and it is C huh. Well now I do feel like a goose, yesterday the code looked like such gobledy-gook that I assumed it was C++, turns out I've just been staring at Rust for too long. C89 too if I'm not mistaken, again.

[apoelstra]

@tcharding I think Tim's "just kidding" was about the implication that C would be simpler than C++, so no need to be worried about it. (This is true, in some senses, but that does not mean that C is a sane or friendly language!)

[tcharding]

C was my first true love, that's why I was so surprised that I mistook it for C++. Friendly languages are boring :)

[Kixunil]

This would also force the signing API to take a &mut pointer to the context object, which really sucks.

Sounds really bad TBH. Would like to figure out a better way.

One thing I don't understand: is rerandomizing the context on each signing truly required for security or is it just a way to procrastinate expensive rerandomization? If the latter does it matter that each context is rerandomized or one randomized context per application is fine?

[real-or-random]

One thing I don't understand: is rerandomizing the context on each signing truly required for security

No. It helps blinding which improves resistance against certain side-channel attacks. So it's good to use and it does not hurt but signing will be secure without it.

or is it just a way to procrastinate expensive rerandomization?

I don't understand this sentence, sorry.

If the latter does it matter that each context is rerandomized or one randomized context per application is fine?

Well, blinding works best if you don't reuse it. That's why it's a good idea to rerandomize the blinding after signing operation. If you have multiple signing contexts and they use the same blinding, this also means you'll reuse the same blinding values.

[Kixunil]

I meant is re-randomization required to achieve the desired resistance?

I don't understand this sentence

Your explanation at the bottom actually answers everything.

Thinking about it &mut is probably really the best.

@apoelstra

if rand is enabled

Does it mean it requires std? If yes can we get rid of the requirement?

[apoelstra]

@Kixunil naively yes, we would need std so we could get ThreadRng. I don't think a non-std rand can actually generate random data. I would like to be wrong.

Having said this, the rerandomize-after-sign logic can be done without rand or std, by using a bit of secret data to do the rerandomization. This would work best with upstream's help, where the natural choice would be the bit indicating whether or not the secret nonce needed to be negated. This bit is not publicly visibile and is otherwise unused.

[Kixunil]

As I understand it non-std can still impl its own RNG and we could support setting it. I suspect re-randomizing in no_std is even more important than std - HW wallets and such.

[apoelstra]

You mean, having a global resettable RNG? That feels kinda scary and overengineered to me.

[Kixunil]

No, just optionally pass RNG when creating secp context.

[apoelstra]

This wouldn't be much easier than just calling context_randomize after context_create IMHO

[Kixunil]

We could use it to force no_std users to call context_randomize but I didn't get the impression it's that important.

[apoelstra]

Yeah, it's not really that important. We should encourage it though -- TBH I have never used context_randomize because I always forget that it exists. It will become even less important once we have a sign_then_randomize API ... especially if we make that the default "sign" function, since this will give us most of the extra sidechannel protection without making the user have a rng.

I think all we should do is add a doccomment on Context::new saying we recommend to call Context::rerandomize afterward.

[Kixunil]

If sign_then_randomize is supposed to be default sign function shouldn't it be called sign and the other sign_no_randomize?

[apoelstra]

Yeah. That's what I'd like. But we should open a PR and have a separate discussion about that specific API change.

[tcharding]

Another related issue: #346

[real-or-random]

Specifically, I will contribute upstream to

• Clean up the static context creation to not "rerandomize" constant data

see bitcoin-core/secp256k1#1120

[Kixunil]

I'm trying to figure out if it's a good idea to rely on signing/pubkey-deriving APIs to be available after this change. I can not imagine how they can be available on no_std without losing re-randomization. There either has to be thread local or a lock (spin lock on no_std 🤮 )

Am I missing something?

[real-or-random]

I'm trying to figure out if it's a good idea to rely on signing/pubkey-deriving APIs to be available after this change

Sorry I can't follow this sentence. Which change are you referring to? The change proposed by Andrew in the initial comment here? And for whom is it not a good idea to rely on who making APIs available?

[Kixunil]

Oh, while writing the reply I noticed I previously missed std feature gate for global context. That is actually an answer to my question, but I think it may be good for other to understand the limitations, so here's what I mean.

As an example, this library currently provides function global::GlobalContext::sign_ecdsa(&self /*... */)

These things can not happen all at the same time:

• the library stays sound
• the method stays there as-is
• re-randomization on each signing is implemented
• no_std is supported
• no_std doesn't use horrible hacks like spin locks
• no_std doesn't require the consumer to provide a global lock implementation through some questionable API

Because:

• Two threads must not write into same memory at the same time (extremely simplified; the reality is much more complicated)
• The method has &self and it points to global memory - IOW, all &self point to the same memory
• re-randomization has to write data to memory
• Soundly writing data to memory behind static shared reference implies either thread-local data or synchronization; no_std doesn't support thread locals
• spin locks are usable on no_std but eat shitton of CPU time and energy, Rust-provided locks are in std
• Implementation of locking would have to be unsafe and global, so the signature would be probably unsafe fn set_global_lock(lock: &dyn Lock) falling back to panic or spin lock if you don't call it. (or probably better safe fn but unsafe trait) The act of locking would involve one more atomic than in usual cases, at least when there's contention

I was asking whether removing the function (at least from no_std) is being considered but it seems it doesn't have to be.

Side note: I prefer thread local to mutexes on std because of performance but if someone has benchmarks proving otherwise LMK.

[real-or-random]

Ok yes, this makes sense.

So my thinking is:

• For things like "re-randomization on each signing", we should first have a look at this in upstream. And this involves taking a step back first. I think re-randomization on each signing is not necessary, and there are better ways. But re-randomization on other operations may be useful. I have some thoughts about and I'll open an issue upstream (hopefully today).
• Independently of this, anytime we want re-randomization, a thread local context will be ideal. It's simple, it just avoids all concurrency issues, and I don't see any drawbacks.