Random isomorphism blinding for ecmult

peterdettman commented at 12:52 pm on October 28, 2018: contributor

Precomputed basepoint multiples are mapped to random iso
Per-scalar-mult extra cost of 1 field mult.
Per-blinding extra cost of 2000 field mults.

The idea is to choose a random non-zero field element ‘iso’ (u) and scale all the precomputed points so that (x, y) => (x.u^2, y.u^3). The (Jacobian) result point of each scalar multiplication is then mapped back via (x, y, z) => (x, y, z.u). Correctness depends on the group operations not involving the curve’s ‘B’ parameter, which would have to be B.u^6 if it was being used.

Currently the static precomp. gets a randomised table but not the iso, so doesn’t work.

Note that this PR modifies _ecmult_gen_blind so that (repeated) calls with a NULL seed no longer reset the blinding each time. There was a test that exercised that reset, which I disabled, but it makes me wonder if there was some purpose to this.

EDIT: Fixed mapping equation

Random isomorphism blinding for ecmult_gen

- Precomputed basepoint multiples are mapped to random iso
- Per-scalar-mult extra cost of 1 field mult.
- Per-blinding extra cost of 2000 field mults.

4303b2715d

peterdettman commented at 5:38 pm on October 29, 2018: contributor

An initial random isomorphism can actually be almost free by tweaking the batch inversion in _ge_set_all_gej_var, I might rework that a bit. It would be nicer though if there was the possibility of a seed being available to _ecmult_gen_context_build. Is there any reason why we couldn’t have a ‘seed32’ parameter to that method?

gmaxwell commented at 9:05 pm on May 29, 2019: contributor

The reason for the rest behaviour is so that tests can get back to an exactly deterministic state, e.g. so that we can have a bunch of test cases that were selected to hit arithmetic corner cases and not have them get broken by reordering tests.

There is no reason that this reset operation needs to be exposed in the API however, it could just be something only available in the tests, so I’m fine with the interface change here. It’s also the case that right now we don’t have many (really any) vectors testing the whole system like that– we should eventually but for now all the field and group corner case tests are low level and aren’t interrupted by blinding. (Part of the reason I haven’t gone and built higher level corner case tests is because I thought it would be better to wait until after our blinding approaches were more settled.)

[And why test field/group corner cases redundantly? sometimes interesting corner cases crop up in the whole system that a unit test misses– e.g. zeros or infinities breaking algorithms. Both high and low level testing are complementary and will catch different issues]

peterdettman cross-referenced this on Jul 31, 2020 from issue Signed-digit multi-comb for ecmult_gen (by peterdettman) by sipa

real-or-random commented at 11:42 am on December 26, 2021: contributor

Hm, is this dead now that we have only static tables (#988)? I mean… it’s still possible to apply the isomorphism once when creating the context but I have no idea if that’s useful.

peterdettman commented at 12:15 pm on December 26, 2021: contributor

Well that change certainly makes this semi-pointless as it stands. It’s a bit disappointing since I consider this a useful blinding option, especially since the SDMC PR will make the signing tables much smaller generally, and particularly so on the small devices which I expect to be more interested in extra side-channel protection.

sipa commented at 3:09 pm on December 26, 2021: contributor

It’s still possible to randomize the Z coordinate of the initial/first-fetched table entry (and then multiply with its inverse before returning). That won’t blind the table values and table lookups, but does provide additional entropy to all intermediary results. I don’t know if it adds anything useful if we already have a random offset applied to the scalar and subtracted off again, though.

peterdettman commented at 3:29 pm on December 26, 2021: contributor

Just to be clear, you mean projective blinding, right? Of course I prefer the isomorphism blinding, but projective blinding is cheap and still useful here (and everywhere really) IMO.

sipa commented at 3:35 pm on December 26, 2021: contributor

@peterdettman If by projective blinding you mean transforming a point (X,Y,Z) to (a^2*X,a^3*Y,a*Z) with a random a - that’s possible too, but not exactly what I mean. I’m thinking of transforming (X,Y,Z) to (X,Y,a*Z), and then at the end dividing the Z coordinate by a again.

real-or-random commented at 3:38 pm on December 26, 2021: contributor

See https://github.com/bitcoin-core/secp256k1/issues/881

real-or-random commented at 6:11 pm on December 26, 2021: contributor

Well that change certainly makes this semi-pointless as it stands. It’s a bit disappointing since I consider this a useful blinding option, especially since the SDMC PR will make the signing tables much smaller generally, and particularly so on the small devices which I expect to be more interested in extra side-channel protection.

Yeah, to be honest, I wasn’t really aware of this idea when I worked on the static tables. But I don’t think it’s an absurd idea to have precomputed non-const tables and apply the blinding at context creation time. Or am I missing something?

peterdettman commented at 6:22 pm on December 26, 2021: contributor

Well IIUC the global tables can’t be non-const because we don’t fool around with global locks. However the option is still there to allow individual signing contexts to choose to have an isomorphism-blinded copy. Admittedly I am not overly familiar with the prevailing assumptions around the precomputed tables and the contexts.

peterdettman commented at 6:25 pm on December 26, 2021: contributor

@peterdettman If by projective blinding you mean transforming a point (X,Y,Z) to (a^2*X,a^3*Y,a*Z) with a random a - that’s possible too, but not exactly what I mean. I’m thinking of transforming (X,Y,Z) to (X,Y,a*Z), and then at the end dividing the Z coordinate by a again.

Well without the tables per this PR wouldn’t you then need a per-addition field mul the same way the strauss ladder does?

sipa commented at 6:27 pm on December 26, 2021: contributor

We just moved to a model where all tables are computed at compile-time (#988). We could reintroduce optional runtime ones, but it would undo a decent amount of benefits of the current approach.

With SDMC I also don’t think there is space for blinding in the tables to begin with: because table entries are used either in positive or negated form, you can’t have persistent offsets in them. And the table entries are ge (_storage), so there is no space for a Z coordinate either.

sipa commented at 6:27 pm on December 26, 2021: contributor

Well without the tables per this PR wouldn’t you then need a per-addition field mul the same way the strauss ladder does?

Oh, of course. Nevermind.

peterdettman commented at 6:38 pm on December 26, 2021: contributor

With SDMC I also don’t think there is space for blinding in the tables to begin with: because table entries are used either in positive or negated form, you can’t have persistent offsets in them. And the table entries are ge (_storage), so there is no space for a Z coordinate either.

Isomorphism blinding doesn’t need space in the tables, it scales each table entry’s X,Y according to a global random Z (“the blind”) - OK you need space to store that one value. Then you just account for the global Z at the end of the signing. All of that is what this PR does. It’s the blinding you were just describing, except it updates the tables to avoid the extra _fe_mul.

sipa commented at 6:43 pm on December 26, 2021: contributor

Sorry it seems I got dragged into this discussion while missing the context of how it started.

Right, isomorphism blinding is still possible with SDMC, but it’s pointless when combined with checked-in precomputed tables (as we now have since #988). I guess it’d be possible to pick a new blinding factor for every release, but the benefit of that seems very small.

real-or-random commented at 6:48 pm on December 26, 2021: contributor

Well IIUC the global tables can’t be non-const because we don’t fool around with global locks.

Oh sure. Sorry, the rate in which I spit out ideas that I haven’t thought through seems to be pretty high these days… (Well maybe it’s just proportional to the activity in the repo.)

edit: I guess then #881 is still a reasonable candidate…

Random isomorphism blinding for ecmult_gen #570