New context API

[real-or-random]

edit: This is now more a meta issue to discuss an improved context API, see the discussion below.

I'm arguably late to the party but I believe we should either talk about this now (before we do a release) or never:

Taking a step back, I believe that even given the problems with C, upstream's API is not optimal here. A better API would be to ask the user to provide entropy already in _context_create, or pass NULL explicitly to opt out.

Originally posted by @real-or-random in rust-bitcoin/rust-secp256k1#225 (comment)

Note that this does not need to be a breaking change, we could for example add a new function and deprecate secp256k1_context_create.

[elichai]

Do we want something like secp256k1_context_create_randomized which can accept either a seed or NULL, or should it enforce NULL?
(the cost I think is that users that don't have access to an rng will pass either an array of zeros or a constant random seed, I don't think either will decrease the security, and a constant seed is probably better than nothing)

[gmaxwell]

@real-or-random Randomization should be ideally be updated for each signature not just once for the context, which is why it doesn't make sense to just have it as a context creation argument.

Ideally every signature would advance blinding to a new state, but doing that would write to the context, and the existing interface allows you to use the context from multiple threads.

This made more sense when the signing context had large and expensive to create precomputed tables in it rather than the tables being static. Now the signing context is essentially just the randomness. It would make a lot more sense in my view to now make signing contexts non-shared, and then they could advance their random state on each use, and it would also be reasonable to generate randomness at creation time.

The problem I see with that is that the verify contexts still have huge expensive to create precomputed tables, and one probably doesn't want to have to generate a new one all the time... so it makes sense to share them. This wouldn't be a big deal, except sign & verify contexts exist.

[real-or-random]

@real-or-random Randomization should be ideally be updated for each signature not just once for the context, which is why it doesn't make sense to just have it as a context creation argument.

Well, agreed but I didn't think about removing _randomize. We should keep this for sure, but it may still make sense to expect the randomness at context creation time.

Ideally every signature would advance blinding to a new state, but doing that would write to the context, and the existing interface allows you to use the context from multiple threads.

This made more sense when the signing context had large and expensive to create precomputed tables in it rather than the tables being static. Now the signing context is essentially just the randomness. It would make a lot more sense in my view to now make signing contexts non-shared, and then they could advance their random state on each use, and it would also be reasonable to generate randomness at creation time.

Indeed. Last time we discussed this, we didn't have a good idea how to do this because of the expensive multiplication. Maybe we could have something like what I mentioned here: http://gnusha.org/secp256k1/2020-07-08.log (I think @sipa mentioned this idea earlier somewhere).

The problem I see with that is that the verify contexts still have huge expensive to create precomputed tables, and one probably doesn't want to have to generate a new one all the time... so it makes sense to share them. This wouldn't be a big deal, except sign & verify contexts exist.

I don't think that's a big deal either. You could make combined contexts non-shared too. If the user wants more concurrency, they can just create separate contexts.

[gmaxwell]

For the scalar update even just having two random 256 bit (scalar,point) pairs stored in the context and randomly choosing one to add to the running scalar blinding with each signature would be pretty good (they should be 256 bit so that they tend to change all the words). I think it would be hard to justify anything more elaborate without measurement.

[real-or-random]

For the scalar update even just having two random 256 bit (scalar,point) pairs stored in the context and randomly choosing one to add to the running scalar blinding with each signature would be pretty good (they should be 256 bit so that they tend to change all the words). I think it would be hard to justify anything more elaborate without measurement.

That sounds interesting but somewhat ad-hoc. Just to get the idea: You propose to choose one of two (instead of a constant value) to make sure that the scalar is essentially randomized after enough signatures, which is good enough because a side-channel attacker anyway needs a lot of samples and is then forced to generate enough signatures?

[gmaxwell]

Right. Even a single attacker unknown random increment should break most attacks, but a choice of two can be done for the runtime cost of a single additional CMOV and will leave the whole scalar totally randomized after a number of uses.

Any of these power/emi sidechannel defences are inherently adhoc: nothing the library can do can make it strong against a sufficiently powerful sidechannel attacker.

If instead we assume the attacker can only manage to extract a few bits, then all the attacks that I'm aware of are extremely fragile and are easily broken. E.g. the quaint old bitcoin 'low-s' rule completely obliterates them-- because they depend on you utterly reliably identifying the most significant bit of the scalar. They can't brute force the guess because they need hundreds of signatures with the correct guess.

The fact that these attacks are so fragile opens the door to disrupting them with fairly minimal means...

The main thing that I know to defend against attacker can get learn the power signature of multiplying with specific constants (e.g. which entries of the precomputed table). The random isomorphism makes it so the first multiplication isn't entirely constant at least, but at least two arguments to it are.

So the first defence is randomly blinding the scalar so that learning which table entries were accessed isn't that useful. But randomly blinding is expensive if you need an extra ecmult to update the blinding and that ecmult leaks too... (though that's why the update should increment the blinder, not replace it).

I think if you really can tolerate a blinding that doubled the computational cost, you'd be better off just running two ecmults with the first or the second randomly the real one, and the other a dummy random one (or blinding update), and use cmovs in and out to get the real one output. But that it just extremely expensive and I think hard to justify without measurements that say it helps and that something stupid isn't leaking everything.

The next obvious thing to do is to increase the size of the ladder some so that you compute a (say) 320-bit x * G and set x randomly so that x%N is the target scalar-- at least that isn't an arbitrary doubling.

Dettman had a patch to use random isomorphisms for the table, but to really make use of it the table needs to be writeable, and on just about any embedded device where power/emi sidechannels are an interesting attack will be pushed by memory pressure and init time to keep the table in flash instead of ram. Though it would be reasonable to apply it build time at least-- better than nothing and the attacker might not have access to the build (e.g. gen_context picking the random isomorphism).

Going back on the theme of limited measures being effective against the known attacks which are less powerful than just reading everything (which we're hopeless against)-- Choice of negation and endomorphism gives 2.58 bits of entropy, e.g. randomly scale the scalar by {1, beta, beta^2, -1, -beta, -beta^2} for the low low cost of two scalar multiplies, three scalar cmovs, one scalar conditional negate, two field multiplies, three field cmovs, and one field conditional negate.

I wish the nonce function it was using naturally gave a somewhat larger output. :-/ even just a couple bits to drive a random scaling factor and/or pick one of two random updates to the blinder.

[real-or-random]

Ok, so I still think that having something like secp256k1_context_create_randomized would be a small improvement but in the end then the current API is pretty reasonable then and I don't think we should change it now.

We should really think about automatic rerandomization but as discussed here this will imply that signing contexts can't be used concurrently. This will be a major change, and so it should not be silent, and we would anyway need to break the API and rename functions etc. This deserves some more thoughts:

• Do we want to split signing/verification contexts entirely?
• Is signing/verification the right terminology now that we have other operations (ECDH, tweaking) that require contexts?
• Are the context creation flags the most ergonomic API?
• ...

I think that's nothing that we want to do for the initial release then. I'm renaming the issue then. If there's interest, we could still introduce "cheap" randomization already with the existing API, e.g., by adding a context_randomize_cheap or similar.

Does this make sense?

[sipa]

Whatever approach is used to get automatic rerandomization upon signing will require an API with mutable objects, and the _sign function(s) currently take an immutable context object, for which it would be pretty surprising to see modifications (and the corresponding need for synchronization).

One possibility is separating the signing context entirely as suggested above, and then make (all?) interactions with such a signing context rerandomize it.

A bit less invasive may be to just have equivalent _sign_and_rerandomize() functions that take a non-const context object, and does the equivalent of signing + separate randomize calls (but with a possibly much cheaper/merged operation). As new functions would be required to deal with a separate context type anyway, this may be strictly less work.

[real-or-random]

A bit less invasive may be to just have equivalent _sign_and_rerandomize() functions that take a non-const context object, and does the equivalent of signing + separate randomize calls (but with a possibly much cheaper/merged operation). As new functions would be required to deal with a separate context type anyway, this may be strictly less work.

That sounds pretty reasonable.

[gmaxwell]

Do we want to split signing/verification contexts entirely?

One problem for that is functions which need both kinds of context (I don't think there are in secp256k1, but IIRC there are in secp256k1-zkp).

I think I'd like to see long term the big tables just becoming static everywhere even if it means making the shared library 1.5MB. And then the contexts could become mutable and non-shared.

(doing that would even save memory on systems, even though it'll make the SO bigger on disk).

Randomization and scratch space really have made a case for mutable contexts that didn't exist when these decisions were originally made.

[real-or-random]

I wish the nonce function it was using naturally gave a somewhat larger output. :-/ even just a couple bits to drive a random scaling factor and/or pick one of two random updates to the blinder.

We can use the squareness of the y coordinate of R, we throw that bit away anyway. And @sipa pointed out that any of the tie-breakers (square, even, high) works as a bit of entropy, no matter what we actually use as a tie-breaker in the scheme.

[gmaxwell]

oh that is super nice! one bit is what I really wanted, and one bit is what you provided.

[sipa]

It's also provably does not impact the security of the signature scheme itself: there is no security risk from leaking the bit to an attacker, as it is at worst equivalent to a variant of the scheme that includes the R sign explicitly.

[real-or-random]

oh that is super nice! one bit is what I really wanted, and one bit is what you provided.

I feel a bit relieved that we don't need to change the nonce function.

[gmaxwell]

I realized that the specifics in the suggestion I gave above are a little broken, it shouldn't just add one constant or another constant, it should add one constant or another constant then double. Otherwise different permutations of the same number of each choice would end up in the same state.

[real-or-random]

Another issue with the current context API is that we can't have a user-provided error callback when the context is created. Currently we hack around this by calling the default callback instead (https://github.com/bitcoin-core/secp256k1/blob/master/src/secp256k1.c#L149) and we give the user the ability to override the default callback at compile time.

All of this is not really nice. The runtime callback setting is not very useful because it does not work everywhere and the compile-time callback setting can be cumbersome.

[elichai]

Summarizing a long discussion on this from IRC (The discussion, I edited out anything that wasn't related, I hope I didn't accidentally modified the discussion in any way)
After #988 there will be 2 kinds of contexts left, and we might add another one with #967:

1. illegal arguments and error callbacks
2. Randomizing the signing operations for better side-channel resistance
3. Determining CPU features in runtime for WIP WIP WIP 5x64 field representation #967.

Some ideas raised on how to handle these so we can remove the context argument from most of the public API:

1. These can probably be removed since we have Allow to use external default callbacks #595, but this might complicate the tests that check these callbacks.
2. A. Should we make this context mutable (or add a sign_with_randomize) so that we can add randomization to it with every sign operation (harvest a single bit of entropy each time).
   B. Should this context be thread_local(C11 and can complicate embedded) or implement something using atomics(C11) (We could for example, make a pool of contexts and mark them as currently used/unused and spinlock if they're all used)
   C. Add a flag that says if it can assume thread safety or not, if yes re-randomize it with every operation, if not don't re-randomize it.
3. Note that this will need to be done only once, and also dynamic dispatch might not be proven performant to do at the field operations level (as it will prohibit inlining) so we might need to do it on the EC operations level or even the API level.
   A. We could use a call_once(C11).
   B. We could use compiler extensions like __attribute__((constructor))(link)
   C. We could use binary specific extensions like .init_array in ELF .CRT$XIB in EXE, and __DATA,__mod_init_func in MCH-O.
   D. We could use architecture specific operations, for example in x86 movs to/from regular registers are always atomic, so we can call cpuid from inline assembly and write the result into a static variable from the assembly, that way we don't violate C data race rules.
   E. Compile the library multiple times with different flags and somehow get the linker to use the right one (@gmaxwell said that's how libspeex works on debian/ubuntu)

My own opinions:
2 - we should probably do A and not B because users of this library can probably implement B more easily as they assume more things on their environment (single threaded, an OS etc.),
3 - we should really try to avoid requiring the user to pass a context everywhere just for the cpuid results.

[real-or-random]

Another purpose of the global context is to run the self-tests (which are currently not run for the static no_precomp context...)

[real-or-random]

Shower thought that I don't want to lose: If we'll have a more mutable context, then it might make sense to store a callback to a PRG in the context (instead of asking the user for randomness every time).