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

[Brian Smith]

Andy Polyakov <appro at openssl.org> wrote:
> It appears to me that with multiplication, squaring, subtraction,
> negation, halving *preserving* property of being fully reduced (i.e. if
> inputs are fully reduced, then output is too), we only have to watch out
> for mul_by_[23], i.e. ensure that their outputs are fully reduced. This
> would ensure that output will always be fully reduced.

Let me state thing in a different way, and see if this is what you
meant: Every function will have as a prerequisite that its inputs are
fully reduced and will have a postcondition that its output is fully
reduced. We know that ecp_nistz256_add doesn't fully reduce its output
even if the input is fully reduced, and we know that
ecp_nistz256_mul_by_[23] are implemented in terms of ecp_nistz256_add
(or equivalent logic, in the case of some of the ASM stuff).
Accordingly, the plan of action is:

* Fix ecp_nistz256_mul_by_2 and ecp_nistz256_mul_by_3 to fully reduce
their outputs.

* Fix ecp_nistz256_add to fully reduce its output.

* Ensure in ecp_nistz256_points_mul that all the input coordinates are
fully reduced.

After all of this, we won't have to worry about the handling of
partially-reduced values anywhere.

Is that correct? In particular, you said "we only have to watch out
for mul_by_[23]" but you didn't mention ecp_nistz256_add, which *is*
used directly in ecp_nistz256_point_double, according to the reference
C implementation.

I think that is a reasonable course of action.

I'd like to suggest the following additional steps:

* Verify with Vlad that he agrees with our assessment of the current
state of the code and the plan. In particular, I still worry that what
we agreed on here doesn't match what Vlad told me before. Maybe Vlad
was thinking about some other code he wrote that uses the Almost
Montgomery math instead of regular Montgomery math. But maybe he knows
something we are overlooking. In particular, we should ask him and
Shay whether they intentionally made ecp_nistz256_add (et al.) return
partially-reduced results because they'd proven that full reduction
isn't necessary given the subsequent statements.

* Document in the top of ecp_nistz256.c the input and output bounds
are [0, P256) for all field operations.

* Test some interesting edge cases of all the functions to verify that
they generate the correct output. (This series of bug reports started
by me doing this, starting with ecp_nistz256_add.)

* Because we can't easily test it, audit the inlined code inside the
assembly langauge implementations of ecp_nistz256_{double, add,
add_affine} to ensure that it matches the logic within the standalone
functions that we can write tests for. (As you noted, in many cases,
the standalone field arithmetic functions and the inline variants
actually share code; in some cases, however, they don't.)

> In this and RT#4621 combined context one can conclude that *as long as*
> inputs to ecp_nistz256_point_add are fully reduced, is_equal calls work
> correctly, because there are no non-full-reduction-preserving calls
> prior them. Would you agree?

If all functions have the postcondition that they always fully reduce
their outputs then I agree that the is_equal calls are correct, and
also that the ecp_nistz256_neg function seems to be correct since it
gives the expected results when given fully reduced inputs.

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