Add constant-time secp256k1_point_multiply for ECDH
Designed with clear separation of the wNAF conversion, precomputation and exponentiation (since the precomp at least we will probably want to separate in the API for users who reuse points a lot).
Future work:
“/** Do an ellitic curve scalar multiplication in constant time.”
spelling.
Added endomorphism optimization.
On my laptop (Lenovo T440p i7-4700MQ 2.4Ghz) I see 85.6us without endomorphism, 107us with. I will need to investigate this..
Edit: Oh, I needed to shrink the wNAF input size from 256 bits to 128 when the endomorphism is enabled. When this is done I see 64.4us, a 25% improvement :)
Pushed; had to do some algebraic changes to get the endomorphism stuff to work. The pre-endomorphism commits have been changed in some minor ways (the unit tests are a bit cleaner, secp256k1_scalar_wnaf_force_odd is replaced by secp256k1_scalar_wnaf_cond_negate and secp256k1_scalar_is_even, and the return type of secp256k1_ecdh_wnaf is now void since it used to return a fixed value, which was confusing. This value is now computed by a macro.)
As for the endomorphism stuff, the wNAF conversion is actually a bit different. We require all wNAF digits to be odd, so to represent even 256-bit numbers, we (a) negate the number, making it odd since our modulus is odd; (b) convert this to wNAF; (c) negate the individual digits, un-negating the number while keeping all digits odd. In this way all 256-bit numbers can be represented. However, with the endomorphism optimization, we find ourselves converting 128-bit numbers to wNAF, which cannot be negated this way. (They can, but their negations are 256 bits, so we lose the optimization.) We therefore use a different strategy for handling even numbers when endomorphism optimization is enabled. Specifically, we add 1 to even numbers, add 2 to odd ones, and compensate after the multiplication by subtracting either P or 2P from the result. This is suggested in the Okeya/Tagaki paper.
With this strategy, the perf numbers are less impressive: with endomorphism optimization on my laptop can do a multiplication in 68.9us.
When I add a test against secp256k1_ec_pubkey_create that runs 100 times with a random_scalar_order scalar it fails usually when the endomorphism optimization is enabled. Investigating.
Edit: So this occurs specifically with scalars whose lambda-decomposition consists of a positive and a negative number (where “negative” means high bit set). Two positives or two negatives are OK, which seems inexplicable … those numbers are treated totally independently by the point-multiply code, so it is weird that there’d be a problem with their relative sign and not their absolute ones.
I doubt this has anything to do with the basepoint being the generator or not; it happens that the existing test code always uses the same hardcoded scalar whose lambda-decomposition consists of two positive values, hence our not seeing this bug with the existing tests.
240+ if (overflow) {
241+ ret = -2;
242+ } else {
243+ secp256k1_ecdh_point_multiply(&res, &pt, &s);
244+ secp256k1_ge_set_gej(&pt, &res);
245+ ret = secp256k1_eckey_pubkey_serialize(&pt, point, pointlen, *pointlen <= 33);
A couple of issues with the documentation for secp256k1_point_multiply:
221+/** Do an elliptic curve scalar multiplication in constant time.
222+ * Returns: 1: exponentiation was successful
223+ * -1: scalar was zero (cannot serialize output point)
224+ * -2: scalar overflow
225+ * -3: invalid input point
226+ * In: scalar: a 32-byte scalar with which to multiple the point
I’ve pushed a new version which fixes the timing leak. I’ve changed the API to output the hash of the computed point rather than the point itself. @gmaxwell had suggested early on that giving the user a curvepoint was “too low level” and not consistent with our policy of not exposing raw cryptographic objects.
The concern was that a user who has access to a “ECDH secret” which is a curvepoint might try to build his or her own cryptosystem in a fragile or broken way. I think this timing leak is an example of me getting burned by this – I didn’t think to look for this timing leak because I was thinking in terms of “points” rather than “secrets”.
35+static void bench_multiply(void* arg) {
36+ int i;
37+ bench_multiply_t *data = (bench_multiply_t*)arg;
38+
39+ for (i = 0; i < 20000; i++) {
40+ CHECK(secp256k1_ecdh_point_multiply(data->point, &data->pointlen, data->scalar) == 1);
-Werror in Travis to prevent this oversight in future?
216@@ -217,6 +217,24 @@ SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_recover_compact(
217 int recid
218 ) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4) SECP256K1_ARG_NONNULL(5);
219
220+/** Compute an EC Diffie-Hellman secret in constant time
221+ * Returns: 1: exponentiation was successful
222+ * 0: scalar was zero (cannot serialize output point)
223+ * -1: scalar overflow
224+ * -2: invalid input point
1391+ ecdh_chain_multiply();
1392+}
1393+
1394+void run_ecdh_api_tests(void) {
1395+ ecdh_generator_basepoint();
1396+}
@peterdettman, @gmaxwell and I had a private conversation on May 15 with the lines
013:18:19 <gmaxwell> One thing I wonder about is that we've tried to avoid offering users APIs that were raw EC operations... both becaues the users won't use them safely, and because they'll construct less efficient implementations of crypto algorithims (e.g. if we expose add and double they can go write a non-constant time, slow as heck ecdh.). I wonder if there are any api affordances we can make to make that multiply s
113:23:47 <andytoshi> there thave been a lot of comments on -dev and -wizards from people who are pretty jacked to have ECDH but who IMHO are probably gonna do something unsafe with it
This was right before I started working on this PR. Then a few days ago in #secp256k1 on IRC:
010:51:09 <andytoshi> in https://github.com/bitcoin/secp256k1/pull/252#discussion_r33412268 peter dettman notes that pubkey_serialize uses fe_normalize_var which is a timing leak for ECDH
110:51:23 <andytoshi> what do we do about this? do we need to split serialize into serialize and serialize_var?
211:02:55 <sipa> i suppose
311:03:00 <sipa> wait
411:03:08 <sipa> right
511:03:28 <sipa> ecdh is weird because it has an EC point which is secret information
613:12:02 <gmaxwell> well I slightly protested before that returning a point was maybe too low level.
713:31:22 <andytoshi> i recall that ... this might be a concrete reason to -not- do it
813:31:50 <andytoshi> i mean, this feels like we got cut by our own sharp corner here..
914:36:30 <sipa> we could hash it before returning
1016:31:30 <gmaxwell> that was my suggestion.
To the best of my knowledge this was the entirety of our discussion.
231+ secp256k1_gej_t res;
232+ secp256k1_ge_t pt;
233+ secp256k1_scalar_t s;
234+ DEBUG_CHECK(point != NULL);
235+ DEBUG_CHECK(pointlen != NULL);
236+ DEBUG_CHECK(scalar != NULL);
170+ VERIFY_CHECK(n != 0);
171+ secp256k1_gej_add_ge(r, r, &tmpa);
172+#else
173+ n = wnaf[i];
174+ VERIFY_CHECK(n != 0);
175+ ECMULT_TABLE_GET_GE(&tmpa, pre_a, n, WINDOW_A);
177+#endif
178+ }
179+
180+ if (!r->infinity) {
181+ secp256k1_fe_mul(&r->z, &r->z, &Z);
182+ }
Fixed all of @peterdettman’s minor comments. Added a new commit to fix the timing leak in GET_GE. The perf hit I measure, using bench_ecdh, is 10%, both with and without endomorphism. :/
Edit: Actually I can get this down to 3% without much trouble, updating the PR with that. I can do even better with a multi-cmov but that will be a bit more work..
- Add zero/one sanity check tests for ecmult
- Add unit test for secp256k1_scalar_split_lambda_var
- Typo fix in `ge_equals_ge`; was comparing b->y to itself, should
have been comparing a->y to b->y
- Normalize y-coordinate in `random_group_element_test`; this is
needed to pass random group elements as the first argument to
`ge_equals_ge`, which I will do in a future commit.I’ve added a commit which moves the ECDH code into its own module but leaves the constant-time multiply code in the main library. It also renames the const-multiply functions, so the result is kinda a mess of renaming and moving.
I’ll go back and rebase the original changeset as though this had been the layout from the start, but first I’d like an ACK that this is how we want to organize things.
44+}
45+
46+int main(void) {
47+ bench_multiply_t data;
48+
49+ run_benchmark("ecdh_mult", bench_multiply, bench_multiply_setup, NULL, &data, 10, 20000);
43+
44+/** Convert a number to WNAF notation. The number becomes represented by sum(2^{wi} * wnaf[i], i=0..return_val)
45+ * with the following guarantees:
46+ * - each wnaf[i] an odd integer between -(1 << w) and (1 << w)
47+ * - each wnaf[i] is nonzero
48+ * - the number of words set is returned; this is always (256 + w - 1) / w
180+ for (j = 0; j < WINDOW_A - 1; ++j) {
181+ /* This is a variable-time doubling, but it is actually constant-time for
182+ * nonzero points. We know on the first iteration that `r` will be zero
183+ * and know (by uniqueness of wNAF) that `r` will never be zero after
184+ * that iteration, so this does not result in a timing leak. */
185+ secp256k1_gej_double_var(r, r, NULL);
ACK design, with a few more nits.
Please squash and I’ll merge.
EDIT: no need to squash everything, but some logical steps are nice… ecmult_const then ecmult_const + endo then optimizations then ECDH module… or whatever you like.
Designed with clear separation of the wNAF conversion, precomputation
and exponentiation (since the precomp at least we will probably want
to separate in the API for users who reuse points a lot.
Future work:
- actually separate precomp in the API
- do multiexp rather than single exponentiation
This has the effect of making `secp256k1_scalar_mul_shift_var` constant
time in both input scalars. Keep the _var name because it is NOT constant
time in the shift amount.
As used in `secp256k1_scalar_split_lambda_var`, the shift is always
the constant 272, so this function becomes constant time, and it
loses the `_var` suffix.
It’s a bit unfortunate that secp256k1 always hash the derived secret, because it means I can’t use it for existing protocols like Bitmessage.
Any ideas how can I get Px with secp256k1? Only by implementing my own version of secp256k1_ecdh? (Note that Bitmessage uses SHA512(Px), so it’s not unsafe.)
@Kagami As you say, ECIES actually only needs a hash of Px, though it’s not our hash. Can you open an issue requesting we extend the ECDH API to support a custom hash function (like the signing functions support custom nonce functions)?
This is something we’ve considered but haven’t had any concrete usecases and I guess it forgot to get written down..