EC2M Lopez-Dahab ladder: use it also for ECDSA verify

By default `ec_scalar_mul_ladder` (which uses the Lopez-Dahab ladder
implementation) is used only for (k * Generator) or (k * VariablePoint).
ECDSA verification uses (a * Generator + b * VariablePoint): this commit
forces the use of `ec_scalar_mul_ladder` also for the ECDSA verification
path, while using the default wNAF implementation for any other case.

With this commit `ec_scalar_mul_ladder` loses the static attribute, and
is added to ec_lcl.h so EC_METHODs can directly use it.

While working on a new custom EC_POINTs_mul implementation, I realized
that many checks (e.g. all the points being compatible with the given
EC_GROUP, creating a temporary BN_CTX if `ctx == NULL`, check for the
corner case `scalar == NULL && num == 0`) were duplicated again and
again in every single implementation (and actually some
implementations lacked some of the tests).
I thought that it makes way more sense for those checks that are
independent from the actual implementation and should always be done, to
be moved in the EC_POINTs_mul wrapper: so this commit also includes
these changes.

Reviewed-by: Andy Polyakov <appro@openssl.org>
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/6690)

9 files changed, 138 insertions, 71 deletions

diff --git a/crypto/ec/ec2_smpl.c b/crypto/ec/ec2_smpl.c
index 14e844dab2..9ce332b32d 100644
--- a/crypto/ec/ec2_smpl.c
+++ b/crypto/ec/ec2_smpl.c
@@ -832,6 +832,63 @@ int ec_GF2m_simple_ladder_post(const EC_GROUP *group,
     return ret;
 }
 
+static
+int ec_GF2m_simple_points_mul(const EC_GROUP *group, EC_POINT *r,
+                              const BIGNUM *scalar, size_t num,
+                              const EC_POINT *points[],
+                              const BIGNUM *scalars[],
+                              BN_CTX *ctx)
+{
+    int ret = 0;
+    EC_POINT *t = NULL;
+
+    /*-
+     * We limit use of the ladder only to the following cases:
+     * - r := scalar * G
+     *   Fixed point mul: scalar != NULL && num == 0;
+     * - r := scalars[0] * points[0]
+     *   Variable point mul: scalar == NULL && num == 1;
+     * - r := scalar * G + scalars[0] * points[0]
+     *   used, e.g., in ECDSA verification: scalar != NULL && num == 1
+     *
+     * In any other case (num > 1) we use the default wNAF implementation.
+     *
+     * We also let the default implementation handle degenerate cases like group
+     * order or cofactor set to 0.
+     */
+    if (num > 1 || BN_is_zero(group->order) || BN_is_zero(group->cofactor))
+        return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
+
+    if (scalar != NULL && num == 0)
+        /* Fixed point multiplication */
+        return ec_scalar_mul_ladder(group, r, scalar, NULL, ctx);
+
+    if (scalar == NULL && num == 1)
+        /* Variable point multiplication */
+        return ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx);
+
+    /*-
+     * Double point multiplication:
+     *  r := scalar * G + scalars[0] * points[0]
+     */
+
+    if ((t = EC_POINT_new(group)) == NULL) {
+        ECerr(EC_F_EC_GF2M_SIMPLE_POINTS_MUL, ERR_R_MALLOC_FAILURE);
+        return 0;
+    }
+
+    if (!ec_scalar_mul_ladder(group, t, scalar, NULL, ctx)
+        || !ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx)
+        || !EC_POINT_add(group, r, t, r, ctx))
+        goto err;
+
+    ret = 1;
+
+ err:
+    EC_POINT_free(t);
+    return ret;
+}
+
 const EC_METHOD *EC_GF2m_simple_method(void)
 {
     static const EC_METHOD ret = {
@@ -866,7 +923,7 @@ const EC_METHOD *EC_GF2m_simple_method(void)
         ec_GF2m_simple_cmp,
         ec_GF2m_simple_make_affine,
         ec_GF2m_simple_points_make_affine,
-        0, /* mul */
+        ec_GF2m_simple_points_mul,
         0, /* precompute_mult */
         0, /* have_precompute_mult */
         ec_GF2m_simple_field_mul,
diff --git a/crypto/ec/ec_err.c b/crypto/ec/ec_err.c
index 6c1d9b7be2..cbe204f597 100644
--- a/crypto/ec/ec_err.c
+++ b/crypto/ec/ec_err.c
@@ -78,6 +78,8 @@ static const ERR_STRING_DATA EC_str_functs[] = {
      "ec_GF2m_simple_oct2point"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_POINT2OCT, 0),
      "ec_GF2m_simple_point2oct"},
+    {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_POINTS_MUL, 0),
+     "ec_GF2m_simple_points_mul"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, 0),
      "ec_GF2m_simple_point_get_affine_coordinates"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES, 0),
@@ -195,6 +197,7 @@ static const ERR_STRING_DATA EC_str_functs[] = {
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_PKEY_PARAM_CHECK, 0), "ec_pkey_param_check"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINTS_MAKE_AFFINE, 0),
      "EC_POINTs_make_affine"},
+    {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINTS_MUL, 0), "EC_POINTs_mul"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_ADD, 0), "EC_POINT_add"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_BN2POINT, 0), "EC_POINT_bn2point"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_CMP, 0), "EC_POINT_cmp"},
@@ -352,6 +355,7 @@ static const ERR_STRING_DATA EC_str_reasons[] = {
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_SLOT_FULL), "slot full"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNDEFINED_GENERATOR), "undefined generator"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNDEFINED_ORDER), "undefined order"},
+    {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNKNOWN_COFACTOR), "unknown cofactor"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNKNOWN_GROUP), "unknown group"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNKNOWN_ORDER), "unknown order"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNSUPPORTED_FIELD), "unsupported field"},
diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h
index 78be154e44..8b16971aab 100644
--- a/crypto/ec/ec_lcl.h
+++ b/crypto/ec/ec_lcl.h
@@ -646,6 +646,39 @@ int X25519(uint8_t out_shared_key[32], const uint8_t private_key[32],
 void X25519_public_from_private(uint8_t out_public_value[32],
                                 const uint8_t private_key[32]);
 
+/*-
+ * This functions computes a single point multiplication over the EC group,
+ * using, at a high level, a Montgomery ladder with conditional swaps, with
+ * various timing attack defenses.
+ *
+ * It performs either a fixed point multiplication
+ *          (scalar * generator)
+ * when point is NULL, or a variable point multiplication
+ *          (scalar * point)
+ * when point is not NULL.
+ *
+ * `scalar` cannot be NULL and should be in the range [0,n) otherwise all
+ * constant time bets are off (where n is the cardinality of the EC group).
+ *
+ * This function expects `group->order` and `group->cardinality` to be well
+ * defined and non-zero: it fails with an error code otherwise.
+ *
+ * NB: This says nothing about the constant-timeness of the ladder step
+ * implementation (i.e., the default implementation is based on EC_POINT_add and
+ * EC_POINT_dbl, which of course are not constant time themselves) or the
+ * underlying multiprecision arithmetic.
+ *
+ * The product is stored in `r`.
+ *
+ * This is an internal function: callers are in charge of ensuring that the
+ * input parameters `group`, `r`, `scalar` and `ctx` are not NULL.
+ *
+ * Returns 1 on success, 0 otherwise.
+ */
+int ec_scalar_mul_ladder(const EC_GROUP *group, EC_POINT *r,
+                         const BIGNUM *scalar, const EC_POINT *point,
+                         BN_CTX *ctx);
+
 int ec_point_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx);
 
 static inline int ec_point_ladder_pre(const EC_GROUP *group,
diff --git a/crypto/ec/ec_lib.c b/crypto/ec/ec_lib.c
index 6a2d1b5800..457cd3593c 100644
--- a/crypto/ec/ec_lib.c
+++ b/crypto/ec/ec_lib.c
@@ -919,11 +919,38 @@ int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
                   size_t num, const EC_POINT *points[],
                   const BIGNUM *scalars[], BN_CTX *ctx)
 {
-    if (group->meth->mul == 0)
+    int ret = 0;
+    size_t i = 0;
+    BN_CTX *new_ctx = NULL;
+
+    if ((scalar == NULL) && (num == 0)) {
+        return EC_POINT_set_to_infinity(group, r);
+    }
+
+    if (!ec_point_is_compat(r, group)) {
+        ECerr(EC_F_EC_POINTS_MUL, EC_R_INCOMPATIBLE_OBJECTS);
+        return 0;
+    }
+    for (i = 0; i < num; i++) {
+        if (!ec_point_is_compat(points[i], group)) {
+            ECerr(EC_F_EC_POINTS_MUL, EC_R_INCOMPATIBLE_OBJECTS);
+            return 0;
+        }
+    }
+
+    if (ctx == NULL && (ctx = new_ctx = BN_CTX_secure_new()) == NULL) {
+        ECerr(EC_F_EC_POINTS_MUL, ERR_R_INTERNAL_ERROR);
+        return 0;
+    }
+
+    if (group->meth->mul != NULL)
+        ret = group->meth->mul(group, r, scalar, num, points, scalars, ctx);
+    else
         /* use default */
-        return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
+        ret = ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
 
-    return group->meth->mul(group, r, scalar, num, points, scalars, ctx);
+    BN_CTX_free(new_ctx);
+    return ret;
 }
 
 int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar,
diff --git a/crypto/ec/ec_mult.c b/crypto/ec/ec_mult.c
index 55cbfa105d..7e1b3650e7 100644
--- a/crypto/ec/ec_mult.c
+++ b/crypto/ec/ec_mult.c
@@ -121,6 +121,9 @@ void EC_ec_pre_comp_free(EC_PRE_COMP *pre)
  * `scalar` cannot be NULL and should be in the range [0,n) otherwise all
  * constant time bets are off (where n is the cardinality of the EC group).
  *
+ * This function expects `group->order` and `group->cardinality` to be well
+ * defined and non-zero: it fails with an error code otherwise.
+ *
  * NB: This says nothing about the constant-timeness of the ladder step
  * implementation (i.e., the default implementation is based on EC_POINT_add and
  * EC_POINT_dbl, which of course are not constant time themselves) or the
@@ -128,9 +131,11 @@ void EC_ec_pre_comp_free(EC_PRE_COMP *pre)
  *
  * The product is stored in `r`.
  *
+ * This is an internal function: callers are in charge of ensuring that the
+ * input parameters `group`, `r`, `scalar` and `ctx` are not NULL.
+ *
  * Returns 1 on success, 0 otherwise.
  */
-static
 int ec_scalar_mul_ladder(const EC_GROUP *group, EC_POINT *r,
                          const BIGNUM *scalar, const EC_POINT *point,
                          BN_CTX *ctx)
@@ -141,15 +146,20 @@ int ec_scalar_mul_ladder(const EC_GROUP *group, EC_POINT *r,
     BIGNUM *k = NULL;
     BIGNUM *lambda = NULL;
     BIGNUM *cardinality = NULL;
-    BN_CTX *new_ctx = NULL;
     int ret = 0;
 
     /* early exit if the input point is the point at infinity */
     if (point != NULL && EC_POINT_is_at_infinity(group, point))
         return EC_POINT_set_to_infinity(group, r);
 
-    if (ctx == NULL && (ctx = new_ctx = BN_CTX_secure_new()) == NULL)
+    if (BN_is_zero(group->order)) {
+        ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_UNKNOWN_ORDER);
         return 0;
+    }
+    if (BN_is_zero(group->cofactor)) {
+        ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_UNKNOWN_COFACTOR);
+        return 0;
+    }
 
     BN_CTX_start(ctx);
 
@@ -370,7 +380,6 @@ int ec_scalar_mul_ladder(const EC_GROUP *group, EC_POINT *r,
     EC_POINT_free(p);
     EC_POINT_free(s);
     BN_CTX_end(ctx);
-    BN_CTX_free(new_ctx);
 
     return ret;
 }
@@ -402,7 +411,6 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
                 size_t num, const EC_POINT *points[], const BIGNUM *scalars[],
                 BN_CTX *ctx)
 {
-    BN_CTX *new_ctx = NULL;
     const EC_POINT *generator = NULL;
     EC_POINT *tmp = NULL;
     size_t totalnum;
@@ -427,15 +435,6 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
                                  * precomputation is not available */
     int ret = 0;
 
-    if (!ec_point_is_compat(r, group)) {
-        ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
-        return 0;
-    }
-
-    if ((scalar == NULL) && (num == 0)) {
-        return EC_POINT_set_to_infinity(group, r);
-    }
-
     if (!BN_is_zero(group->order) && !BN_is_zero(group->cofactor)) {
         /*-
          * Handle the common cases where the scalar is secret, enforcing a
@@ -465,19 +464,6 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
         }
     }
 
-    for (i = 0; i < num; i++) {
-        if (!ec_point_is_compat(points[i], group)) {
-            ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
-            return 0;
-        }
-    }
-
-    if (ctx == NULL) {
-        ctx = new_ctx = BN_CTX_new();
-        if (ctx == NULL)
-            goto err;
-    }
-
     if (scalar != NULL) {
         generator = EC_GROUP_get0_generator(group);
         if (generator == NULL) {
@@ -784,7 +770,6 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
     ret = 1;
 
  err:
-    BN_CTX_free(new_ctx);
     EC_POINT_free(tmp);
     OPENSSL_free(wsize);
     OPENSSL_free(wNAF_len);
diff --git a/crypto/ec/ecp_nistp224.c b/crypto/ec/ecp_nistp224.c
index 39fee015d3..ecae5688d0 100644
--- a/crypto/ec/ecp_nistp224.c
+++ b/crypto/ec/ecp_nistp224.c
@@ -1396,7 +1396,6 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
     int j;
     unsigned i;
     int mixed = 0;
-    BN_CTX *new_ctx = NULL;
     BIGNUM *x, *y, *z, *tmp_scalar;
     felem_bytearray g_secret;
     felem_bytearray *secrets = NULL;
@@ -1413,9 +1412,6 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
     const EC_POINT *p = NULL;
     const BIGNUM *p_scalar = NULL;
 
-    if (ctx == NULL)
-        if ((ctx = new_ctx = BN_CTX_new()) == NULL)
-            return 0;
     BN_CTX_start(ctx);
     x = BN_CTX_get(ctx);
     y = BN_CTX_get(ctx);
@@ -1578,7 +1574,6 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
  err:
     BN_CTX_end(ctx);
     EC_POINT_free(generator);
-    BN_CTX_free(new_ctx);
     OPENSSL_free(secrets);
     OPENSSL_free(pre_comp);
     OPENSSL_free(tmp_felems);
diff --git a/crypto/ec/ecp_nistp256.c b/crypto/ec/ecp_nistp256.c
index 47e2817e3a..22f172be74 100644
--- a/crypto/ec/ecp_nistp256.c
+++ b/crypto/ec/ecp_nistp256.c
@@ -2018,7 +2018,6 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r,
     int ret = 0;
     int j;
     int mixed = 0;
-    BN_CTX *new_ctx = NULL;
     BIGNUM *x, *y, *z, *tmp_scalar;
     felem_bytearray g_secret;
     felem_bytearray *secrets = NULL;
@@ -2036,9 +2035,6 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r,
     const EC_POINT *p = NULL;
     const BIGNUM *p_scalar = NULL;
 
-    if (ctx == NULL)
-        if ((ctx = new_ctx = BN_CTX_new()) == NULL)
-            return 0;
     BN_CTX_start(ctx);
     x = BN_CTX_get(ctx);
     y = BN_CTX_get(ctx);
@@ -2207,7 +2203,6 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r,
  err:
     BN_CTX_end(ctx);
     EC_POINT_free(generator);
-    BN_CTX_free(new_ctx);
     OPENSSL_free(secrets);
     OPENSSL_free(pre_comp);
     OPENSSL_free(tmp_smallfelems);
diff --git a/crypto/ec/ecp_nistp521.c b/crypto/ec/ecp_nistp521.c
index abcc5bb8ec..06945b5f6b 100644
--- a/crypto/ec/ecp_nistp521.c
+++ b/crypto/ec/ecp_nistp521.c
@@ -1855,7 +1855,6 @@ int ec_GFp_nistp521_points_mul(const EC_GROUP *group, EC_POINT *r,
     int ret = 0;
     int j;
     int mixed = 0;
-    BN_CTX *new_ctx = NULL;
     BIGNUM *x, *y, *z, *tmp_scalar;
     felem_bytearray g_secret;
     felem_bytearray *secrets = NULL;
@@ -1872,9 +1871,6 @@ int ec_GFp_nistp521_points_mul(const EC_GROUP *group, EC_POINT *r,
     const EC_POINT *p = NULL;
     const BIGNUM *p_scalar = NULL;
 
-    if (ctx == NULL)
-        if ((ctx = new_ctx = BN_CTX_new()) == NULL)
-            return 0;
     BN_CTX_start(ctx);
     x = BN_CTX_get(ctx);
     y = BN_CTX_get(ctx);
@@ -2041,7 +2037,6 @@ int ec_GFp_nistp521_points_mul(const EC_GROUP *group, EC_POINT *r,
  err:
     BN_CTX_end(ctx);
     EC_POINT_free(generator);
-    BN_CTX_free(new_ctx);
     OPENSSL_free(secrets);
     OPENSSL_free(pre_comp);
     OPENSSL_free(tmp_felems);
diff --git a/crypto/ec/ecp_nistz256.c b/crypto/ec/ecp_nistz256.c
index 57a69aa873..4b5fc62797 100644
--- a/crypto/ec/ecp_nistz256.c
+++ b/crypto/ec/ecp_nistz256.c
@@ -1139,12 +1139,10 @@ __owur static int ecp_nistz256_points_mul(const EC_GROUP *group,
                                           const BIGNUM *scalars[], BN_CTX *ctx)
 {
     int i = 0, ret = 0, no_precomp_for_generator = 0, p_is_infinity = 0;
-    size_t j;
     unsigned char p_str[33] = { 0 };
     const PRECOMP256_ROW *preComputedTable = NULL;
     const NISTZ256_PRE_COMP *pre_comp = NULL;
     const EC_POINT *generator = NULL;
-    BN_CTX *new_ctx = NULL;
     const BIGNUM **new_scalars = NULL;
     const EC_POINT **new_points = NULL;
     unsigned int idx = 0;
@@ -1162,27 +1160,6 @@ __owur static int ecp_nistz256_points_mul(const EC_GROUP *group,
         return 0;
     }
 
-    if (!ec_point_is_compat(r, group)) {
-        ECerr(EC_F_ECP_NISTZ256_POINTS_MUL, EC_R_INCOMPATIBLE_OBJECTS);
-        return 0;
-    }
-
-    if ((scalar == NULL) && (num == 0))
-        return EC_POINT_set_to_infinity(group, r);
-
-    for (j = 0; j < num; j++) {
-        if (!ec_point_is_compat(points[j], group)) {
-            ECerr(EC_F_ECP_NISTZ256_POINTS_MUL, EC_R_INCOMPATIBLE_OBJECTS);
-            return 0;
-        }
-    }
-
-    if (ctx == NULL) {
-        ctx = new_ctx = BN_CTX_new();
-        if (ctx == NULL)
-            goto err;
-    }
-
     BN_CTX_start(ctx);
 
     if (scalar) {
@@ -1380,7 +1357,6 @@ __owur static int ecp_nistz256_points_mul(const EC_GROUP *group,
 err:
     if (ctx)
         BN_CTX_end(ctx);
-    BN_CTX_free(new_ctx);
     OPENSSL_free(new_points);
     OPENSSL_free(new_scalars);
     return ret;