aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRob Austein <sra@hactrn.net>2015-08-22 22:11:37 -0400
committerRob Austein <sra@hactrn.net>2015-08-22 22:11:37 -0400
commitdbb766ef71b5b31365b92450aba5312e65bd3c77 (patch)
tree673648e5c253de9fdc3c6392cbbdff4ab5bd9530
parent9e4c5edc6ef46b4c182379eab46abb45e5d2022f (diff)
Rework point_scalar_multiply() to avoid a timing leak with small scalars.
-rw-r--r--ecdsa.c37
1 files changed, 19 insertions, 18 deletions
diff --git a/ecdsa.c b/ecdsa.c
index 38a5b31..070c668 100644
--- a/ecdsa.c
+++ b/ecdsa.c
@@ -574,30 +574,31 @@ static hal_error_t point_scalar_multiply(const fp_int * const k,
/*
* Walk down bits of the scalar, performing dummy operations to mask
- * timing while hunting for the most significant bit.
+ * timing while hunting for the most significant bit of the scalar.
+ *
+ * Note that, in order for this timing protection to work, the
+ * number of iterations in the loop has to depend on the order of
+ * the base point rather than on the scalar.
*/
int dummy_mode = 1;
- for (int digit_index = k->used - 1; digit_index >= 0; digit_index--) {
-
- fp_digit digit = k->dp[digit_index];
+ for (int bit_index = fp_count_bits(unconst_fp_int(curve->n)) - 1; bit_index >= 0; bit_index--) {
- for (int bits_left = DIGIT_BIT; bits_left > 0; bits_left--) {
+ const int digit_index = bit_index / DIGIT_BIT;
+ const fp_digit digit = digit_index < k->used ? k->dp[digit_index] : 0;
+ const fp_digit mask = ((fp_digit) 1) << (bit_index % DIGIT_BIT);
+ const int bit = (digit & mask) != 0;
- const int bit = (digit >> (DIGIT_BIT - 1)) & 1;
- digit <<= 1;
-
- if (dummy_mode) {
- point_add (M[0], M[1], M[2], curve);
- point_double (M[1], M[2], curve);
- dummy_mode = !bit; /* Dummy until we find MSB */
- }
+ if (dummy_mode) {
+ point_add (M[0], M[1], M[2], curve);
+ point_double (M[1], M[2], curve);
+ dummy_mode = !bit; /* Dummy until we find MSB */
+ }
- else {
- point_add (M[0], M[1], M[bit^1], curve);
- point_double (M[bit], M[bit], curve);
- }
+ else {
+ point_add (M[0], M[1], M[bit^1], curve);
+ point_double (M[bit], M[bit], curve);
}
}
@@ -605,7 +606,7 @@ static hal_error_t point_scalar_multiply(const fp_int * const k,
* Copy result out, map back to affine if requested, then done.
*/
- *R = *M[0];
+ point_copy(M[0], R);
hal_error_t err = map ? point_to_affine(R, curve) : HAL_OK;
memset(M, 0, sizeof(M));
return err;