Simpler and faster ecdh skew fixup #1029

peterdettman commented at 2:26 PM on December 3, 2021: contributor

This PR adds a _gej_cmov method, with accompanying tests, and uses it to simplify the skew fixup at the end of _ecmult_const.

In the existing code, _wnaf_const chooses a skew of either 1 or 2, and _ecmult_const needs a call to _ge_set_gej (which does an expensive field inversion internally) and some overly-complicated conversions to/from _ge_storage so that _ge_storage_cmov can be used to select what value to add for the fixup.

This PR uses a simpler scheme where _wnaf_const chooses a skew of 0 or 1 and no longer needs special handling for scalars with value negative one. A new _gej_cmov method is used at the end of _ecmult_const for const-time optional addition to adjust the final result for the skew. Finally, the skew fixup is moved to before the global-Z adjustment, and the precomputed table entries (for 1P, λ(1P)) are used for the skew fixup, saving a field multiply and ensuring the fixup is done on the same isomorphism as the ladder.

The resulting _wnaf_const and _ecmult_const are shorter and simpler, and the ECDH benchmark is around 5% faster (64bit, i7).

Edit: Updated description once the final scope was clear.

peterdettman commented at 4:58 PM on December 3, 2021: contributor

Added another commit that changes the skew to be either 0 or 1. Total performance gain is maybe 5% now (less for 32bit).

peterdettman force-pushed on Dec 21, 2021

apoelstra approved

apoelstra commented at 12:21 AM on December 23, 2021: contributor

ACK 6498a6c939f967de0ffe8d0475e9921a967080c9

These are great cleanups! LOL at the first commit -- I don't know why I didn't think to add a gej_cmov, instead adding 10+ lines of conversion logic so that I could use ge_storage_cmov.

apoelstra commented at 12:23 AM on December 23, 2021: contributor

I can't recall exactly why my original code added 1 or 2, rather than 1 or 0. I remember thinking that "adding zero or non-zero can't be done in a constant-time way" but then I wound up needing to use a cmov anyway.

I think that it simply didn't occur to me to use your "always do a corrective addition, then use cmov to undo it if necessary" logic.

peterdettman commented at 4:48 AM on December 23, 2021: contributor

I can't recall exactly why my original code added 1 or 2, rather than 1 or 0

My somewhat foggy recollection is that much of the earliest EC side-channel literature was focused only on performing a constant number of point operations, and didn't initially care about memory timings, so they would even just use if/else to choose which of P or 2P to add. If it weren't for the endomorphism complicating things, we could probably modify the scalar instead (by adding N when it's even) and/or use a signed-digit encoding, which I would consider the "modern style".

peterdettman force-pushed on Dec 23, 2021

in src/group_impl.h:645 in da099be933 outdated

 641 | @@ -642,6 +642,14 @@ static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storag
 642 |      r->infinity = 0;
 643 |  }
 644 |  
 645 | +static SECP256K1_INLINE void secp256k1_gej_cmov(secp256k1_gej *r, const secp256k1_gej *a, int flag) {

real-or-random commented at 9:31 PM on December 23, 2021:

I think it's not strictly necessary but can you add a test for this?

peterdettman commented at 9:51 AM on December 24, 2021:

Done.

real-or-random commented at 9:41 PM on December 23, 2021: contributor

Concept ACK

I read this code a few times and I always wondered about the 1, 2 thing.

apoelstra commented at 2:41 PM on December 24, 2021: contributor

ACK 1120790139baee6726ddf6eeb2d29a92bc174d4f

Simpler and faster ecdh skew fixup 1515099433

ECDH skews by 0 or 1 8c13a9bfe1

Add tests for _gej_cmov 40b624c90b

Fixup skew before global Z fixup e82144edfb

peterdettman force-pushed on Dec 26, 2021

peterdettman commented at 8:20 AM on December 26, 2021: contributor

Moved the skew fixup to before the global Z fixup by using the table entries. Saves an _fe_mul and is just a bit nicer to have all the operations on the same isomorphism. Also rebased.

apoelstra commented at 4:15 PM on December 26, 2021: contributor

ACK e82144ed

Nifty! Agreed, it is easier to follow now with fewer temp variables.

real-or-random approved

real-or-random commented at 7:22 PM on December 26, 2021: contributor

ACK e82144edfb7673d9a5eeb2b556d08be5223835ac

peterdettman commented at 7:25 PM on December 26, 2021: contributor

I've no more changes in mind.

sipa commented at 7:28 PM on December 26, 2021: contributor

The PR description seems outdated now.

peterdettman commented at 4:33 AM on December 27, 2021: contributor

The PR description seems outdated now.

I've updated the description to match the full PR.

sipa commented at 4:46 PM on December 31, 2021: contributor

ACK e82144edfb7673d9a5eeb2b556d08be5223835ac

sipa merged this on Dec 31, 2021

sipa closed this on Dec 31, 2021

jonasnick cross-referenced this on Jan 2, 2022 from issue Sync Upstream by jonasnick

real-or-random referenced this in commit 21e2d65b79 on Jan 5, 2022

dhruv referenced this in commit 6f7e395acc on Jan 26, 2022

hebasto referenced this in commit 065b6dbf9d on Jan 30, 2022

dhruv referenced this in commit 139d4b881e on Feb 1, 2022

fanquake referenced this in commit 8f8631d826 on Mar 17, 2022

fanquake referenced this in commit 4bb1d7e62a on Mar 17, 2022

fanquake referenced this in commit 465d05253a on Mar 30, 2022

stratospher referenced this in commit 4d5afc9767 on Apr 3, 2022

stratospher referenced this in commit 5b18493cfa on Apr 3, 2022

fanquake referenced this in commit afb7a6fe06 on Apr 6, 2022

gwillen referenced this in commit 35d6112a72 on May 25, 2022

patricklodder referenced this in commit 21badcf9d2 on Jul 25, 2022

patricklodder referenced this in commit 03002a9013 on Jul 28, 2022

janus referenced this in commit 3a0652a777 on Aug 4, 2022

str4d referenced this in commit 522190d5c3 on Apr 21, 2023

vmta referenced this in commit e1120c94a1 on Jun 4, 2023

vmta referenced this in commit 8f03457eed on Jul 1, 2023