Point addition formulas for short Weierstrass curves are often
incomplete and do not work for P + P. EC implementations usually rely on
constant-time operations never hitting this case, or at least it being
rare[0].
However, the condition checks several values. Our C functions use && and
||, and the P-256 assembly also branches. This can leak intermediate
values via a small side channel. Thanks to David Schrammel and Samuel
Weiser for reporting this.
nistz256 base point multiplication (keygen, ECDSA signing) is unaffected
due to ecp_nistz256_point_add_affine lacking a doubling case. nistp224
and nistp256 base point multiplication, on some compilers, are saved by
quirks of the "mixed" path. The generic code's base point multiplication
and all methods' arbitrary point multiplication (ECDH; ephemeral keys
makes this less interesting) are affected.
Fix the branches in the nistz256 assembly, and use bit operations in C.
Note the C versions are all different because P-224 believes true is 1,
P-256 believes true is any non-zero value, and the generic code believes
true is 0xf...f. This should be double-checked when reviewing.
Aside: The nistz256 assembly also special-cases nontrivial P + (-P) in
arbitrary point multiplication. Fortunately, the formulas in util.c hold
there and I believe one can show P + (-P) is unreachable for all curves.
Still, it would be nice to omit the branch if we can verify the assembly
works anyway.
[0] https://github.com/openssl/openssl/blob/03da376ff7504c63a1d00d57cf41bd7b7e93ff65/crypto/ec/ecp_nistp521.c#L1259
Change-Id: I8958624cd6b5272e5076c6c1605ab089e85f4cb7
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/36465
Reviewed-by: Adam Langley <agl@google.com>
Commit-Queue: Adam Langley <agl@google.com>
David Benjamin
12d9ed670d