EC point multiplication: add `ladder` scaffold

for specialized Montgomery ladder implementations

PR #6009 and #6070 replaced the default EC point multiplication path for
prime and binary curves with a unified Montgomery ladder implementation
with various timing attack defenses (for the common paths when a secret
scalar is feed to the point multiplication).
The newly introduced default implementation directly used
EC_POINT_add/dbl in the main loop.

The scaffolding introduced by this commit allows EC_METHODs to define a
specialized `ladder_step` function to improve performances by taking
advantage of efficient formulas for differential addition-and-doubling
and different coordinate systems.

- `ladder_pre` is executed before the main loop of the ladder: by
  default it copies the input point P into S, and doubles it into R.
  Specialized implementations could, e.g., use this hook to transition
  to different coordinate systems before copying and doubling;
- `ladder_step` is the core of the Montgomery ladder loop: by default it
  computes `S := R+S; R := 2R;`, but specific implementations could,
  e.g., implement a more efficient formula for differential
  addition-and-doubling;
- `ladder_post` is executed after the Montgomery ladder loop: by default
  it's a noop, but specialized implementations could, e.g., use this
  hook to transition back from the coordinate system used for optimizing
  the differential addition-and-doubling or recover the y coordinate of
  the result point.

This commit also renames `ec_mul_consttime` to `ec_scalar_mul_ladder`,
as it better corresponds to what this function does: nothing can be
truly said about the constant-timeness of the overall execution of this
function, given that the underlying operations are not necessarily
constant-time themselves.
What this implementation ensures is that the same fixed sequence of
operations is executed for each scalar multiplication (for a given
EC_GROUP), with no dependency on the value of the input scalar.

Co-authored-by: Sohaib ul Hassan <soh.19.hassan@gmail.com>
Co-authored-by: Billy Brumley <bbrumley@gmail.com>

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

14 files changed, 202 insertions, 57 deletions

diff --git a/CHANGES b/CHANGES
index 4765e0b14a..bfa73aeec3 100644
--- a/CHANGES
+++ b/CHANGES
@@ -9,6 +9,13 @@
 
  Changes between 1.1.0h and 1.1.1 [xx XXX xxxx]
 
+  *) Add a scaffold to optionally enhance the Montgomery ladder implementation
+     for `ec_scalar_mul_ladder` (formerly `ec_mul_consttime`) allowing
+     EC_METHODs to implement their own specialized "ladder step", to take
+     advantage of more favorable coordinate systems or more efficient
+     differential addition-and-doubling algorithms.
+     [Billy Bob Brumley, Sohaib ul Hassan, Nicola Tuveri]
+
   *) Modified the random device based seed sources to keep the relevant
      file descriptors open rather than reopening them on each access.
      This allows such sources to operate in a chroot() jail without
diff --git a/crypto/ec/ec2_smpl.c b/crypto/ec/ec2_smpl.c
index cef6ba4c65..5601912536 100644
--- a/crypto/ec/ec2_smpl.c
+++ b/crypto/ec/ec2_smpl.c
@@ -66,7 +66,10 @@ const EC_METHOD *EC_GF2m_simple_method(void)
         0, /* keyfinish */
         ecdh_simple_compute_key,
         0, /* field_inverse_mod_ord */
-        0  /* blind_coordinates */
+        0, /* blind_coordinates */
+        0, /* ladder_pre */
+        0, /* ladder_step */
+        0  /* ladder_post */
     };
 
     return &ret;
diff --git a/crypto/ec/ec_err.c b/crypto/ec/ec_err.c
index b0bd3be2c1..6e701e29a5 100644
--- a/crypto/ec/ec_err.c
+++ b/crypto/ec/ec_err.c
@@ -226,6 +226,8 @@ static const ERR_STRING_DATA EC_str_functs[] = {
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_SET_TO_INFINITY, 0),
      "EC_POINT_set_to_infinity"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_PRE_COMP_NEW, 0), "ec_pre_comp_new"},
+    {ERR_PACK(ERR_LIB_EC, EC_F_EC_SCALAR_MUL_LADDER, 0),
+     "ec_scalar_mul_ladder"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_WNAF_MUL, 0), "ec_wNAF_mul"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_WNAF_PRECOMPUTE_MULT, 0),
      "ec_wNAF_precompute_mult"},
@@ -314,6 +316,9 @@ static const ERR_STRING_DATA EC_str_reasons[] = {
     "invalid trinomial basis"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_KDF_PARAMETER_ERROR), "kdf parameter error"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_KEYS_NOT_SET), "keys not set"},
+    {ERR_PACK(ERR_LIB_EC, 0, EC_R_LADDER_POST_FAILURE), "ladder post failure"},
+    {ERR_PACK(ERR_LIB_EC, 0, EC_R_LADDER_PRE_FAILURE), "ladder pre failure"},
+    {ERR_PACK(ERR_LIB_EC, 0, EC_R_LADDER_STEP_FAILURE), "ladder step failure"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_MISSING_PARAMETERS), "missing parameters"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_MISSING_PRIVATE_KEY), "missing private key"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_NEED_NEW_SETUP_VALUES),
@@ -333,6 +338,8 @@ static const ERR_STRING_DATA EC_str_reasons[] = {
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_POINT_ARITHMETIC_FAILURE),
     "point arithmetic failure"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_POINT_AT_INFINITY), "point at infinity"},
+    {ERR_PACK(ERR_LIB_EC, 0, EC_R_POINT_COORDINATES_BLIND_FAILURE),
+    "point coordinates blind failure"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_POINT_IS_NOT_ON_CURVE),
     "point is not on curve"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_RANDOM_NUMBER_GENERATION_FAILED),
diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h
index ae380290a2..78be154e44 100644
--- a/crypto/ec/ec_lcl.h
+++ b/crypto/ec/ec_lcl.h
@@ -178,6 +178,15 @@ struct ec_method_st {
     int (*field_inverse_mod_ord)(const EC_GROUP *, BIGNUM *r,
                                  const BIGNUM *x, BN_CTX *);
     int (*blind_coordinates)(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx);
+    int (*ladder_pre)(const EC_GROUP *group,
+                      EC_POINT *r, EC_POINT *s,
+                      EC_POINT *p, BN_CTX *ctx);
+    int (*ladder_step)(const EC_GROUP *group,
+                       EC_POINT *r, EC_POINT *s,
+                       EC_POINT *p, BN_CTX *ctx);
+    int (*ladder_post)(const EC_GROUP *group,
+                       EC_POINT *r, EC_POINT *s,
+                       EC_POINT *p, BN_CTX *ctx);
 };
 
 /*
@@ -638,3 +647,42 @@ void X25519_public_from_private(uint8_t out_public_value[32],
                                 const uint8_t private_key[32]);
 
 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,
+                                      EC_POINT *r, EC_POINT *s,
+                                      EC_POINT *p, BN_CTX *ctx)
+{
+    if (group->meth->ladder_pre != NULL)
+        return group->meth->ladder_pre(group, r, s, p, ctx);
+
+    if (!EC_POINT_copy(s, p)
+        || !EC_POINT_dbl(group, r, s, ctx))
+        return 0;
+
+    return 1;
+}
+
+static inline int ec_point_ladder_step(const EC_GROUP *group,
+                                       EC_POINT *r, EC_POINT *s,
+                                       EC_POINT *p, BN_CTX *ctx)
+{
+    if (group->meth->ladder_step != NULL)
+        return group->meth->ladder_step(group, r, s, p, ctx);
+
+    if (!EC_POINT_add(group, s, r, s, ctx)
+        || !EC_POINT_dbl(group, r, r, ctx))
+        return 0;
+
+    return 1;
+
+}
+
+static inline int ec_point_ladder_post(const EC_GROUP *group,
+                                       EC_POINT *r, EC_POINT *s,
+                                       EC_POINT *p, BN_CTX *ctx)
+{
+    if (group->meth->ladder_post != NULL)
+        return group->meth->ladder_post(group, r, s, p, ctx);
+
+    return 1;
+}
diff --git a/crypto/ec/ec_mult.c b/crypto/ec/ec_mult.c
index 663db57f0c..55cbfa105d 100644
--- a/crypto/ec/ec_mult.c
+++ b/crypto/ec/ec_mult.c
@@ -108,10 +108,9 @@ void EC_ec_pre_comp_free(EC_PRE_COMP *pre)
 } while(0)
 
 /*-
- * This functions computes (in constant time) a point multiplication over the
- * EC group.
- *
- * At a high level, it is Montgomery ladder with conditional swaps.
+ * 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)
@@ -119,20 +118,25 @@ void EC_ec_pre_comp_free(EC_PRE_COMP *pre)
  *          (scalar * point)
  * when point is not NULL.
  *
- * scalar should be in the range [0,n) otherwise all constant time bets are off.
+ * `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).
  *
- * NB: This says nothing about EC_POINT_add and EC_POINT_dbl,
- * which of course are not constant time themselves.
+ * 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.
+ * The product is stored in `r`.
  *
  * Returns 1 on success, 0 otherwise.
  */
-static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r,
-                            const BIGNUM *scalar, const EC_POINT *point,
-                            BN_CTX *ctx)
+static
+int ec_scalar_mul_ladder(const EC_GROUP *group, EC_POINT *r,
+                         const BIGNUM *scalar, const EC_POINT *point,
+                         BN_CTX *ctx)
 {
     int i, cardinality_bits, group_top, kbit, pbit, Z_is_one;
+    EC_POINT *p = NULL;
     EC_POINT *s = NULL;
     BIGNUM *k = NULL;
     BIGNUM *lambda = NULL;
@@ -140,30 +144,49 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r,
     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)
         return 0;
 
     BN_CTX_start(ctx);
 
-    s = EC_POINT_new(group);
-    if (s == NULL)
+    if (((p = EC_POINT_new(group)) == NULL)
+        || ((s = EC_POINT_new(group)) == NULL)) {
+        ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_MALLOC_FAILURE);
         goto err;
+    }
 
     if (point == NULL) {
-        if (!EC_POINT_copy(s, group->generator))
+        if (!EC_POINT_copy(p, group->generator)) {
+            ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_EC_LIB);
             goto err;
+        }
     } else {
-        if (!EC_POINT_copy(s, point))
+        if (!EC_POINT_copy(p, point)) {
+            ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_EC_LIB);
             goto err;
+        }
     }
 
+    EC_POINT_BN_set_flags(p, BN_FLG_CONSTTIME);
+    EC_POINT_BN_set_flags(r, BN_FLG_CONSTTIME);
     EC_POINT_BN_set_flags(s, BN_FLG_CONSTTIME);
 
     cardinality = BN_CTX_get(ctx);
     lambda = BN_CTX_get(ctx);
     k = BN_CTX_get(ctx);
-    if (k == NULL || !BN_mul(cardinality, group->order, group->cofactor, ctx))
+    if (k == NULL) {
+        ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_MALLOC_FAILURE);
+        goto err;
+    }
+
+    if (!BN_mul(cardinality, group->order, group->cofactor, ctx)) {
+        ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB);
         goto err;
+    }
 
     /*
      * Group cardinalities are often on a word boundary.
@@ -174,11 +197,15 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r,
     cardinality_bits = BN_num_bits(cardinality);
     group_top = bn_get_top(cardinality);
     if ((bn_wexpand(k, group_top + 1) == NULL)
-        || (bn_wexpand(lambda, group_top + 1) == NULL))
+        || (bn_wexpand(lambda, group_top + 1) == NULL)) {
+        ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB);
         goto err;
+    }
 
-    if (!BN_copy(k, scalar))
+    if (!BN_copy(k, scalar)) {
+        ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB);
         goto err;
+    }
 
     BN_set_flags(k, BN_FLG_CONSTTIME);
 
@@ -187,15 +214,21 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r,
          * this is an unusual input, and we don't guarantee
          * constant-timeness
          */
-        if (!BN_nnmod(k, k, cardinality, ctx))
+        if (!BN_nnmod(k, k, cardinality, ctx)) {
+            ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB);
             goto err;
+        }
     }
 
-    if (!BN_add(lambda, k, cardinality))
+    if (!BN_add(lambda, k, cardinality)) {
+        ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB);
         goto err;
+    }
     BN_set_flags(lambda, BN_FLG_CONSTTIME);
-    if (!BN_add(k, lambda, cardinality))
+    if (!BN_add(k, lambda, cardinality)) {
+        ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB);
         goto err;
+    }
     /*
      * lambda := scalar + cardinality
      * k := scalar + 2*cardinality
@@ -209,8 +242,13 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r,
         || (bn_wexpand(s->Z, group_top) == NULL)
         || (bn_wexpand(r->X, group_top) == NULL)
         || (bn_wexpand(r->Y, group_top) == NULL)
-        || (bn_wexpand(r->Z, group_top) == NULL))
+        || (bn_wexpand(r->Z, group_top) == NULL)
+        || (bn_wexpand(p->X, group_top) == NULL)
+        || (bn_wexpand(p->Y, group_top) == NULL)
+        || (bn_wexpand(p->Z, group_top) == NULL)) {
+        ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB);
         goto err;
+    }
 
     /*-
      * Apply coordinate blinding for EC_POINT.
@@ -220,19 +258,19 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r,
      * success or if coordinate blinding is not implemented for this
      * group.
      */
-    if (!ec_point_blind_coordinates(group, s, ctx))
-        goto err;
-
-    /* top bit is a 1, in a fixed pos */
-    if (!EC_POINT_copy(r, s))
+    if (!ec_point_blind_coordinates(group, p, ctx)) {
+        ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_POINT_COORDINATES_BLIND_FAILURE);
         goto err;
+    }
 
-    EC_POINT_BN_set_flags(r, BN_FLG_CONSTTIME);
-
-    if (!EC_POINT_dbl(group, s, s, ctx))
+    /* Initialize the Montgomery ladder */
+    if (!ec_point_ladder_pre(group, r, s, p, ctx)) {
+        ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_LADDER_PRE_FAILURE);
         goto err;
+    }
 
-    pbit = 0;
+    /* top bit is a 1, in a fixed pos */
+    pbit = 1;
 
 #define EC_POINT_CSWAP(c, a, b, w, t) do {         \
         BN_consttime_swap(c, (a)->X, (b)->X, w);   \
@@ -304,10 +342,12 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r,
     for (i = cardinality_bits - 1; i >= 0; i--) {
         kbit = BN_is_bit_set(k, i) ^ pbit;
         EC_POINT_CSWAP(kbit, r, s, group_top, Z_is_one);
-        if (!EC_POINT_add(group, s, r, s, ctx))
-            goto err;
-        if (!EC_POINT_dbl(group, r, r, ctx))
+
+        /* Perform a single step of the Montgomery ladder */
+        if (!ec_point_ladder_step(group, r, s, p, ctx)) {
+            ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_LADDER_STEP_FAILURE);
             goto err;
+        }
         /*
          * pbit logic merges this cswap with that of the
          * next iteration
@@ -318,9 +358,16 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r,
     EC_POINT_CSWAP(pbit, r, s, group_top, Z_is_one);
 #undef EC_POINT_CSWAP
 
+    /* Finalize ladder (and recover full point coordinates) */
+    if (!ec_point_ladder_post(group, r, s, p, ctx)) {
+        ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_LADDER_POST_FAILURE);
+        goto err;
+    }
+
     ret = 1;
 
  err:
+    EC_POINT_free(p);
     EC_POINT_free(s);
     BN_CTX_end(ctx);
     BN_CTX_free(new_ctx);
@@ -391,29 +438,30 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 
     if (!BN_is_zero(group->order) && !BN_is_zero(group->cofactor)) {
         /*-
-         * Handle the common cases where the scalar is secret, enforcing a constant
-         * time scalar multiplication algorithm.
+         * Handle the common cases where the scalar is secret, enforcing a
+         * scalar multiplication implementation based on a Montgomery ladder,
+         * with various timing attack defenses.
          */
         if ((scalar != NULL) && (num == 0)) {
             /*-
              * In this case we want to compute scalar * GeneratorPoint: this
-             * codepath is reached most prominently by (ephemeral) key generation
-             * of EC cryptosystems (i.e. ECDSA keygen and sign setup, ECDH
-             * keygen/first half), where the scalar is always secret. This is why
-             * we ignore if BN_FLG_CONSTTIME is actually set and we always call the
-             * constant time version.
+             * codepath is reached most prominently by (ephemeral) key
+             * generation of EC cryptosystems (i.e. ECDSA keygen and sign setup,
+             * ECDH keygen/first half), where the scalar is always secret. This
+             * is why we ignore if BN_FLG_CONSTTIME is actually set and we
+             * always call the ladder version.
              */
-            return ec_mul_consttime(group, r, scalar, NULL, ctx);
+            return ec_scalar_mul_ladder(group, r, scalar, NULL, ctx);
         }
         if ((scalar == NULL) && (num == 1)) {
             /*-
-             * In this case we want to compute scalar * GenericPoint: this codepath
-             * is reached most prominently by the second half of ECDH, where the
-             * secret scalar is multiplied by the peer's public point. To protect
-             * the secret scalar, we ignore if BN_FLG_CONSTTIME is actually set and
-             * we always call the constant time version.
+             * In this case we want to compute scalar * VariablePoint: this
+             * codepath is reached most prominently by the second half of ECDH,
+             * where the secret scalar is multiplied by the peer's public point.
+             * To protect the secret scalar, we ignore if BN_FLG_CONSTTIME is
+             * actually set and we always call the ladder version.
              */
-            return ec_mul_consttime(group, r, scalars[0], points[0], ctx);
+            return ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx);
         }
     }
 
diff --git a/crypto/ec/ecp_mont.c b/crypto/ec/ecp_mont.c
index 358e998e46..fda9a231f6 100644
--- a/crypto/ec/ecp_mont.c
+++ b/crypto/ec/ecp_mont.c
@@ -63,7 +63,10 @@ const EC_METHOD *EC_GFp_mont_method(void)
         0, /* keyfinish */
         ecdh_simple_compute_key,
         0, /* field_inverse_mod_ord */
-        ec_GFp_simple_blind_coordinates
+        ec_GFp_simple_blind_coordinates,
+        0, /* ladder_pre */
+        0, /* ladder_step */
+        0  /* ladder_post */
     };
 
     return &ret;
diff --git a/crypto/ec/ecp_nist.c b/crypto/ec/ecp_nist.c
index 58669d3425..2c23525a51 100644
--- a/crypto/ec/ecp_nist.c
+++ b/crypto/ec/ecp_nist.c
@@ -65,7 +65,10 @@ const EC_METHOD *EC_GFp_nist_method(void)
         0, /* keyfinish */
         ecdh_simple_compute_key,
         0, /* field_inverse_mod_ord */
-        ec_GFp_simple_blind_coordinates
+        ec_GFp_simple_blind_coordinates,
+        0, /* ladder_pre */
+        0, /* ladder_step */
+        0  /* ladder_post */
     };
 
     return &ret;
diff --git a/crypto/ec/ecp_nistp224.c b/crypto/ec/ecp_nistp224.c
index 6155b546df..39fee015d3 100644
--- a/crypto/ec/ecp_nistp224.c
+++ b/crypto/ec/ecp_nistp224.c
@@ -292,7 +292,10 @@ const EC_METHOD *EC_GFp_nistp224_method(void)
         0, /* keyfinish */
         ecdh_simple_compute_key,
         0, /* field_inverse_mod_ord */
-        0  /* blind_coordinates */
+        0, /* blind_coordinates */
+        0, /* ladder_pre */
+        0, /* ladder_step */
+        0  /* ladder_post */
     };
 
     return &ret;
diff --git a/crypto/ec/ecp_nistp256.c b/crypto/ec/ecp_nistp256.c
index 00fcfd5bbd..47e2817e3a 100644
--- a/crypto/ec/ecp_nistp256.c
+++ b/crypto/ec/ecp_nistp256.c
@@ -1821,7 +1821,12 @@ const EC_METHOD *EC_GFp_nistp256_method(void)
         ec_key_simple_generate_public_key,
         0, /* keycopy */
         0, /* keyfinish */
-        ecdh_simple_compute_key
+        ecdh_simple_compute_key,
+        0, /* field_inverse_mod_ord */
+        0, /* blind_coordinates */
+        0, /* ladder_pre */
+        0, /* ladder_step */
+        0  /* ladder_post */
     };
 
     return &ret;
diff --git a/crypto/ec/ecp_nistp521.c b/crypto/ec/ecp_nistp521.c
index 4e6c0f98fb..abcc5bb8ec 100644
--- a/crypto/ec/ecp_nistp521.c
+++ b/crypto/ec/ecp_nistp521.c
@@ -1660,7 +1660,10 @@ const EC_METHOD *EC_GFp_nistp521_method(void)
         0, /* keyfinish */
         ecdh_simple_compute_key,
         0, /* field_inverse_mod_ord */
-        0  /* blind_coordinates */
+        0, /* blind_coordinates */
+        0, /* ladder_pre */
+        0, /* ladder_step */
+        0  /* ladder_post */
     };
 
     return &ret;
diff --git a/crypto/ec/ecp_nistz256.c b/crypto/ec/ecp_nistz256.c
index 045c2e71fb..57a69aa873 100644
--- a/crypto/ec/ecp_nistz256.c
+++ b/crypto/ec/ecp_nistz256.c
@@ -1731,7 +1731,10 @@ const EC_METHOD *EC_GFp_nistz256_method(void)
         0, /* keyfinish */
         ecdh_simple_compute_key,
         ecp_nistz256_inv_mod_ord,                   /* can be #define-d NULL */
-        0                                           /* blind_coordinates */
+        0,                                          /* blind_coordinates */
+        0,                                          /* ladder_pre */
+        0,                                          /* ladder_step */
+        0                                           /* ladder_post */
     };
 
     return &ret;
diff --git a/crypto/ec/ecp_smpl.c b/crypto/ec/ecp_smpl.c
index e0e4996cfd..768922aa11 100644
--- a/crypto/ec/ecp_smpl.c
+++ b/crypto/ec/ecp_smpl.c
@@ -64,7 +64,10 @@ const EC_METHOD *EC_GFp_simple_method(void)
         0, /* keyfinish */
         ecdh_simple_compute_key,
         0, /* field_inverse_mod_ord */
-        ec_GFp_simple_blind_coordinates
+        ec_GFp_simple_blind_coordinates,
+        0, /* ladder_pre */
+        0, /* ladder_step */
+        0 /* ladder_post */
     };
 
     return &ret;
@@ -1418,4 +1421,3 @@ int ec_GFp_simple_blind_coordinates(const EC_GROUP *group, EC_POINT *p,
      BN_CTX_end(ctx);
      return ret;
 }
-
diff --git a/crypto/err/openssl.txt b/crypto/err/openssl.txt
index 007560a171..99bd118c8e 100644
--- a/crypto/err/openssl.txt
+++ b/crypto/err/openssl.txt
@@ -630,6 +630,7 @@ EC_F_EC_POINT_SET_JPROJECTIVE_COORDINATES_GFP:126:\
 	EC_POINT_set_Jprojective_coordinates_GFp
 EC_F_EC_POINT_SET_TO_INFINITY:127:EC_POINT_set_to_infinity
 EC_F_EC_PRE_COMP_NEW:196:ec_pre_comp_new
+EC_F_EC_SCALAR_MUL_LADDER:284:ec_scalar_mul_ladder
 EC_F_EC_WNAF_MUL:187:ec_wNAF_mul
 EC_F_EC_WNAF_PRECOMPUTE_MULT:188:ec_wNAF_precompute_mult
 EC_F_I2D_ECPARAMETERS:190:i2d_ECParameters
@@ -2130,6 +2131,9 @@ EC_R_INVALID_PRIVATE_KEY:123:invalid private key
 EC_R_INVALID_TRINOMIAL_BASIS:137:invalid trinomial basis
 EC_R_KDF_PARAMETER_ERROR:148:kdf parameter error
 EC_R_KEYS_NOT_SET:140:keys not set
+EC_R_LADDER_POST_FAILURE:136:ladder post failure
+EC_R_LADDER_PRE_FAILURE:153:ladder pre failure
+EC_R_LADDER_STEP_FAILURE:162:ladder step failure
 EC_R_MISSING_PARAMETERS:124:missing parameters
 EC_R_MISSING_PRIVATE_KEY:125:missing private key
 EC_R_NEED_NEW_SETUP_VALUES:157:need new setup values
@@ -2144,6 +2148,7 @@ EC_R_PEER_KEY_ERROR:149:peer key error
 EC_R_PKPARAMETERS2GROUP_FAILURE:127:pkparameters2group failure
 EC_R_POINT_ARITHMETIC_FAILURE:155:point arithmetic failure
 EC_R_POINT_AT_INFINITY:106:point at infinity
+EC_R_POINT_COORDINATES_BLIND_FAILURE:163:point coordinates blind failure
 EC_R_POINT_IS_NOT_ON_CURVE:107:point is not on curve
 EC_R_RANDOM_NUMBER_GENERATION_FAILED:158:random number generation failed
 EC_R_SHARED_INFO_ERROR:150:shared info error
diff --git a/include/openssl/ecerr.h b/include/openssl/ecerr.h
index 6ed80ca5e6..cd73c8c9c1 100644
--- a/include/openssl/ecerr.h
+++ b/include/openssl/ecerr.h
@@ -156,6 +156,7 @@ int ERR_load_EC_strings(void);
 #  define EC_F_EC_POINT_SET_JPROJECTIVE_COORDINATES_GFP    126
 #  define EC_F_EC_POINT_SET_TO_INFINITY                    127
 #  define EC_F_EC_PRE_COMP_NEW                             196
+#  define EC_F_EC_SCALAR_MUL_LADDER                        284
 #  define EC_F_EC_WNAF_MUL                                 187
 #  define EC_F_EC_WNAF_PRECOMPUTE_MULT                     188
 #  define EC_F_I2D_ECPARAMETERS                            190
@@ -222,6 +223,9 @@ int ERR_load_EC_strings(void);
 #  define EC_R_INVALID_TRINOMIAL_BASIS                     137
 #  define EC_R_KDF_PARAMETER_ERROR                         148
 #  define EC_R_KEYS_NOT_SET                                140
+#  define EC_R_LADDER_POST_FAILURE                         136
+#  define EC_R_LADDER_PRE_FAILURE                          153
+#  define EC_R_LADDER_STEP_FAILURE                         162
 #  define EC_R_MISSING_PARAMETERS                          124
 #  define EC_R_MISSING_PRIVATE_KEY                         125
 #  define EC_R_NEED_NEW_SETUP_VALUES                       157
@@ -236,6 +240,7 @@ int ERR_load_EC_strings(void);
 #  define EC_R_PKPARAMETERS2GROUP_FAILURE                  127
 #  define EC_R_POINT_ARITHMETIC_FAILURE                    155
 #  define EC_R_POINT_AT_INFINITY                           106
+#  define EC_R_POINT_COORDINATES_BLIND_FAILURE             163
 #  define EC_R_POINT_IS_NOT_ON_CURVE                       107
 #  define EC_R_RANDOM_NUMBER_GENERATION_FAILED             158
 #  define EC_R_SHARED_INFO_ERROR                           150