Implement constant time EC scalar multiplication.

Replace simplistic non-constant time scalar multiplication with a constant
time version. This is actually faster since we compute multiples of the
point, then double four times and add once. The multiple to add is selected
conditionally, ensuring that the access patterns remain the same regardless
of value.

Inspired by Go's scalar multiplication code.

ok tb@

1 files changed, 103 insertions, 16 deletions

diff --git a/src/lib/libcrypto/ec/ecp_hp_methods.c b/src/lib/libcrypto/ec/ecp_hp_methods.c
index bd414f49aa..0b34a55b9d 100644
--- a/src/lib/libcrypto/ec/ecp_hp_methods.c
+++ b/src/lib/libcrypto/ec/ecp_hp_methods.c
@@ -1,4 +1,4 @@
-/*      $OpenBSD: ecp_hp_methods.c,v 1.4 2025/08/03 15:08:28 jsing Exp $        */
+/*      $OpenBSD: ecp_hp_methods.c,v 1.5 2025/08/03 15:44:00 jsing Exp $        */
 /*
  * Copyright (c) 2024-2025 Joel Sing <jsing@openbsd.org>
  *
@@ -22,15 +22,11 @@
 #include <openssl/err.h>
 
 #include "bn_internal.h"
+#include "crypto_internal.h"
 #include "ec_local.h"
 #include "ec_internal.h"
 #include "err_local.h"
 
-/*
- * TODO:
- *  - Constant time and blinding for scalar multiplication
- */
-
 static int
 ec_group_set_curve(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a,
     const BIGNUM *b, BN_CTX *ctx)
@@ -781,38 +777,129 @@ ec_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[],
 }
 #endif
 
+static void
+ec_point_select(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
+    const EC_POINT *b, int conditional)
+{
+        ec_field_element_select(&group->fm, &r->fe_x, &a->fe_x, &b->fe_x, conditional);
+        ec_field_element_select(&group->fm, &r->fe_y, &a->fe_y, &b->fe_y, conditional);
+        ec_field_element_select(&group->fm, &r->fe_z, &a->fe_z, &b->fe_z, conditional);
+}
+
 static int
 ec_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, const EC_POINT *point,
     BN_CTX *ctx)
 {
-        EC_POINT *rr;
-        int bits, i;
+        BIGNUM *cardinality;
+        EC_POINT *multiples[15];
+        EC_POINT *rr = NULL, *t = NULL;
+        uint8_t *scalar_bytes = NULL;
+        int scalar_len = 0;
+        uint8_t j, wv;
+        int conditional, i;
         int ret = 0;
 
-        /* XXX - need constant time and blinding. */
+        memset(multiples, 0, sizeof(multiples));
+
+        BN_CTX_start(ctx);
+
+        /* XXX - consider blinding. */
+
+        if ((cardinality = BN_CTX_get(ctx)) == NULL)
+                goto err;
+        if (!BN_mul(cardinality, group->order, group->cofactor, ctx))
+                goto err;
+
+        /* XXX - handle scalar > cardinality and/or negative. */
+
+        /* Convert scalar into big endian bytes. */
+        scalar_len = BN_num_bytes(cardinality);
+        if ((scalar_bytes = calloc(1, scalar_len)) == NULL)
+                goto err;
+        if (!BN_bn2binpad(scalar, scalar_bytes, scalar_len))
+                goto err;
+
+        /* Compute multiples of point. */
+        if ((multiples[0] = EC_POINT_dup(point, group)) == NULL)
+                goto err;
+        for (i = 1; i < 15; i += 2) {
+                if ((multiples[i] = EC_POINT_new(group)) == NULL)
+                        goto err;
+                if (!EC_POINT_dbl(group, multiples[i], multiples[i / 2], ctx))
+                        goto err;
+                if ((multiples[i + 1] = EC_POINT_new(group)) == NULL)
+                        goto err;
+                if (!EC_POINT_add(group, multiples[i + 1], multiples[i], point, ctx))
+                        goto err;
+        }
 
         if ((rr = EC_POINT_new(group)) == NULL)
                 goto err;
+        if ((t = EC_POINT_new(group)) == NULL)
+                goto err;
 
-        bits = BN_num_bits(scalar);
+        if (!EC_POINT_set_to_infinity(group, rr))
+                goto err;
 
-        EC_POINT_copy(rr, point);
+        for (i = 0; i < scalar_len; i++) {
+                if (i != 0) {
+                        if (!EC_POINT_dbl(group, rr, rr, ctx))
+                                goto err;
+                        if (!EC_POINT_dbl(group, rr, rr, ctx))
+                                goto err;
+                        if (!EC_POINT_dbl(group, rr, rr, ctx))
+                                goto err;
+                        if (!EC_POINT_dbl(group, rr, rr, ctx))
+                                goto err;
+                }
+
+                if (!EC_POINT_set_to_infinity(group, t))
+                        goto err;
+
+                wv = scalar_bytes[i] >> 4;
+                for (j = 1; j < 16; j++) {
+                        conditional = crypto_ct_eq_u8(j, wv);
+                        ec_point_select(group, t, t, multiples[j - 1], conditional);
+                }
+                if (!EC_POINT_add(group, rr, rr, t, ctx))
+                        goto err;
 
-        for (i = bits - 2; i >= 0; i--) {
                 if (!EC_POINT_dbl(group, rr, rr, ctx))
                         goto err;
-                if (BN_is_bit_set(scalar, i)) {
-                        if (!EC_POINT_add(group, rr, rr, point, ctx))
-                                goto err;
+                if (!EC_POINT_dbl(group, rr, rr, ctx))
+                        goto err;
+                if (!EC_POINT_dbl(group, rr, rr, ctx))
+                        goto err;
+                if (!EC_POINT_dbl(group, rr, rr, ctx))
+                        goto err;
+
+                if (!EC_POINT_set_to_infinity(group, t))
+                        goto err;
+
+                wv = scalar_bytes[i] & 0xf;
+                for (j = 1; j < 16; j++) {
+                        conditional = crypto_ct_eq_u8(j, wv);
+                        ec_point_select(group, t, t, multiples[j - 1], conditional);
                 }
+                if (!EC_POINT_add(group, rr, rr, t, ctx))
+                        goto err;
         }
 
-        EC_POINT_copy(r, rr);
+        if (!EC_POINT_copy(r, rr))
+                goto err;
 
         ret = 1;
 
  err:
+        for (i = 0; i < 15; i++)
+                EC_POINT_free(multiples[i]);
+
         EC_POINT_free(rr);
+        EC_POINT_free(t);
+
+        freezero(scalar_bytes, scalar_len);
+
+        BN_CTX_end(ctx);
 
         return ret;
 }