[openssl-dev] Partially- vs. full- reduced inputs to ecp_nistz256_neg

[Brian Smith]

I was curious about the function ecp_nistz256_neg. This function seems
to work exactly how I expect for reduced inputs; i.e. inputs in the
range [0, P). And, it also seems to work how I expect for P:
ecp_nistz256_neg(P) == ecp_nistz256_neg(0) == 0. So, everything seems
fine for inputs in the range [0, P].

But, I don't understand how it works for the value P + 1. I expect
that one of the following is true:

    ecp_nistz256_neg(P + 1) == ecp_nistz256_neg(1)
    ecp_nistz256_neg(P + 1) == ecp_nistz256_neg(1) + P.

But, instead, ecp_nistz256_neg(P + 1) returns a result of 2**256 - 1. That is:

input = ffffffff00000001000000000000000000000001000000000000000000000000
expected = ffffffff00000001000000000000000000000000fffffffffffffffffffffffe
actual: ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

Similarly, I decided to test ecp_nistz256_neg(2**256 - 1). I expected
that one of the following would be true:

    ecp_nistz256_neg(2**256 - 1) = ecp_nistz256_neg(2**256 - 1 - P)
    ecp_nistz256_neg(2**256 - 1) == ecp_nistz256_neg(2**256 - 1 - P) + P.

But, instead, ecp_nistz256_neg(2**256 - 1) == 1. That is:

input = ffffffff00000001000000000000000000000000fffffffffffffffffffffffe
expected = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
actual: 01

Based on these two results, then, it seems that when the input is in
the range [P + 1, 2**256 - 1], the result is actually the negation
taken modulo 2**256, instead of the negation modulo p256 (perhaps not
fully reduced).

I don't know if this is actually problematic, but it was surprising to me.

It seems to me that it would be a good idea for ecp_nistz256_neg to
first reduce its input modulo P (i.e. do a conditional subtraction of
P) before it does its calculation. At least, this would make it clear
that it is correct.

Note in particular that, IIUC, ecp_nistz256_neg will never get an
unreduced input when applied to the the based point multiples, because
those are already fully reduced. But, when it is used in
ecp_nistz256_windowed_mul, it isn't clear whether or how the input Y
coordinate is fully reduced mod P before passed to ecp_nistz256_neg.

More generally, I'm think it might be a good idea to unit test all of
the primitive operations in ecp_nistz256, with particular emphasis
placed on whether unreduced inputs are supposed to be accepted for
certain functions and, if so, whether unreduced inputs are handled
correctly.

And also, since many of the ecp_nistz256 field arithmetic functions
are inlined into the ecp_nistz256_point functions, I think it would be
worthwhile to review that the inlined versions of those functions
actually are operating in the same way as the analogous standalone
(C-callable) ecp_nistz256_* functions.

Sorry if I'm overlooking something fundamental, which I admit is
likely. Any help is appreciated.

Cheers,
Brian
--
https://briansmith.org/