Make fe magnitude implied statically #1001

See the discussion starting here: #943 (comment)

To be clear, all the instances of magnitude are currently statically implied because all those "variables" that are dynamic are currently only ever passed integer literal values.

@roconnor-blockstream Surely not, e.g. what about _fe_cmov?

I wasn't aware of that one. (I'm less familiar with the non-verification related code.)

Make sense to patch that case by always setting the magnitude to the max of the two values?

Yes, which was already done, then patched out, so this time with more comments I think!

@peterdettman Can you elaborate a little bit more on the reasoning behind this suggestion?

I fully agree it's conceptually nicer. But as long as we don't have automated checks that prove that the magnitude is always low enough, does it really matter?

The whole point of the magnitude field is to have a check that the tested code paths would not overflow even if different values were used. It is a poor man's abstract interpretation.

But when we, say, set the magnitude of the output of cmov, based on the flag value, and the value of that flag value is dependent on the specific initial value we are testing, then our "abstract interpretation" ends up being limited to only those value that would produce the same flag value at that call site.

I respect that our poor man's abstract interpretation is imperfect. There are places were we explicitly branch on data (especially in the _var functions). But we can at least strive to make our abstraction as abstract as reasonably possible.

(For illustration: the opposite course of action would be to make the magnitude based more and more on concrete values, but there is no point in doing that. We already have a prefect measure of the a concrete magnitude: using the actual value itself!).

I thought of the magnitude verification AS the automated checks. It's inherently worst-case, basically a static bounds check. That plus code coverage of all branches (and careful analysis of the very few loops) means there's no overflows in the field arithmetic. Without that property you need to be sure you have test cases that exercise every code path at the maximum possible magnitude, which is just a harder-to-prove/understand version of the same thing.

We already have a prefect measure of the a concrete magnitude: using the actual value itself!

Bingo.

I thought of the magnitude verification AS the automated checks. It's inherently worst-case, basically a static bounds check.

Oh sure, I missed this part!

(My thinking was: "it's only dynamic analysis anyway". But if the values are statically determined, then that's indeed all we need...)

It sure would be nice to have a way of restricting a function argument to be a literal. Both to allow the obvious implementation for _mul_int, but also to restrict _fe_negate to specifying a literal for its 'm' (magnitude) argument.

I'm moderately sure there is some horrible way to enforce this with macros. The specific solution I came across uses compound literals, but I suspect there are C89 ways too.

But I'm not sure that we really want to go down the horrible-macro route.

Edit: Maybe just casting through a one dimensional array somehow I'm not sure.

#define foo(i) foo_do_not_call_directly((int[1+0*i])(int)(i)[0])

@roconnor-blockstream What about just appending u in the macro? That's valid only for literals, and magnitude is anyway not negative.

appending u also works for the expression i + 1.

Oh indeed.

What about this?

#define foo(i) foo_do_not_call_directly(sizeof(char[i]))?

edit: that doesn't give an error in GCC. It just gives a warning, and you need -pedantic to trigger the warning (variable-length arrays are a GCC extension)

Here's a better one:

#define foo(i) do { switch (i) {  case i: foo_do_not_call(i) }} while (0)

(suggested by @roconnor-blockstream again)

Another way of doing it is to define a force_const macro like:

#define force_const(i) (sizeof(struct{int a:i;}), i)

That only works up to the bitwidth of int, which is at least 16, so that's enough for this particular purpose...

https://port70.net/~nsz/c/c89/c89-draft.html#45 is pretty useful here.

There's also in https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fconstant_005fp in gcc.

An entirely different way to do this is the approach in #833.

An entirely different way to do this is the approach in #833.

Does that allow something generic like requiring that for any function parameter named literal_* (just for example), at all call sites the argument must be an actual literal (after pre-processor stage, say)?

(Maybe the restriction is really to compile-time constant or something else more complicated, but we could just look at literals for the moment.)

An entirely different way to do this is the approach in #833.

Does that allow something generic like requiring that for any function parameter named literal_* (just for example), at all call sites the argument must be an actual literal (after pre-processor stage, say)?

I haven't tried but I'm pretty sure that this is possible. Coupling it to the parameter name is a pretty nice idea!

So I think #1066 makes it very clear in what ways norm/mag are not compile-time known, as it puts all propagation logic for these fields together. I find:

• fe_cmov (easily fixed: take the max)
• set_b32 (which only produces a normalized result if the input is < p). If we want to fix this, I think we should split it into 2 functions:
  • One that always sets normalized=0.
  • One that always sets normalized=1, but in case the input is >= p, it returns an error value and resets the field value to 0 or so.
• fe_mul_int's integer argument (fixed by forcing it to be a constant)
• fe_negate's magnitude (fixed by forcing it to be a constant)
• All the ways in which the code flow depends on values, in vartime algorithms, of course.

The secp256k1_fe_set_f32 runtime dependency has been addressed through #1207.

See #1317 for the secp256k1_fe_cmov runtime dependency.

One instance we have overlooked is fe_set_int. I missed that in #1345, but I think it should just set the magnitude to 1 always. We have fe_clear for setting to 0. (That one should probably be split in clear for nuking the memory, and fe_set_zero if you really want 0 with magnitude 0.)

With #1922 merged, the field module should be covered entirely.

This leaves us "only" with all the vartime functions. One way to deal with them is to "join" the magnitudes after every branch, i.e., take the maximum value of all branches. But doing this consistently throught the codebase will be a PITA.

My alternative plan to address these is as follows:

Most fe manipulations outside the field module happen to fe fields of a ge/gej. We could cover all of these without dealing with branches in any kind by exploiting the existing SECP256K1_GE_VERIFY macros (see also #1923 and possible follow-ups). My idea is to change the macro on ge/gej outputs into SECP256K1_GE_VERIFY_AND_RELAX (or similar name). This macro will check the magnitudes against the SECP256K1_GE(J)_*_MAGNITUDE_MAX bounds but also set the tracked magnitude values to exactly these bounds. That means whenever a function outputs a ge/gej, the magnitude values will be fixed. This will ensure that no functions accepting ge/gej as input will rely on them being lower (and we can change SECP256K1_GE_VERIFY to check for == instead of <=). Crucially, this will also get us rid of the need for any special magnitude handling in branches. In theory, this may require us to add a few normalize calls (though I couldn't spot any places in my preliminary testing) but the performance penalty should be negligible compared to the simplicity we gain from this.

For the remaining few cases where fes are passed around without a wrapping ge, we could wrap them in a fe_boxed (with a better name) type that has essentially the same guarantees as ge/gej, i.e., there's a SECP256K1_FE_BOXED_MAGNITUDE_MAX guarantee; 8 is probably a good value. Raw fe would then be allowed only inside ge, gej and fe_boxed.

With these changes done, and under the assumption that our API tests hit every internal branch, a successful run should prove that we never exceed the magnitude limits.

@real-or-random: Nice idea, Concept ACK (assuming the performance penalty is negligible indeed). Probably the two macros could simply be called SECP256K1_GE_VERIFY_{INPUT,OUTPUT}.

Crucially, this will also get us rid of the need for any special magnitude handling in branches.

I need to make this more precise. What fixing the magnitude values at function outputs gives us is that it eliminates any need to do interprocedural reasoning (i.e., the need to reason over all reachable sequences of function calls where one function creates a fe/ge, passes it to another which modifies it etc). Branches inside a function remain as they are, but those will matter only until the end of the function. This means that intraprocedural analysis is sufficient. As a result, if we hit every branch in testing, which can be seen for "proper" branches (i.e., not cmov and tricks) from branch coverage, then we know that magnitude is fine.