commit 66f8235510bb43004f1da5197e760af72abe73b9
author David Benjamin <davidben@google.com> Sat Nov 11 11:37:40 2017 +0800
committer Adam Langley <agl@google.com> Mon Nov 20 16:27:51 2017 +0000
tree dc163ffdc565d0c1eefc453f81a77c65d99ff293
parent a08bba51a5bf8dbcdb5eb6ea9422615e4a1c9c09

Enforce some bounds and invariants on custom curves.

Later code will take advantage of these invariants. Enforcing them on
custom curves avoids making them go through a custom codepath.

Change-Id: I23cee72a90c2e4846b41e03e6be26bc3abeb4a45
Reviewed-on: https://boringssl-review.googlesource.com/23072
Reviewed-by: Adam Langley <agl@google.com>

crypto/fipsmodule/ec/ec.c

diff --git a/crypto/fipsmodule/ec/ec.c b/crypto/fipsmodule/ec/ec.c
index 600aedc..4916b1d 100644
--- a/crypto/fipsmodule/ec/ec.c
+++ b/crypto/fipsmodule/ec/ec.c
@@ -383,6 +383,11 @@
 
 EC_GROUP *EC_GROUP_new_curve_GFp(const BIGNUM *p, const BIGNUM *a,
                                  const BIGNUM *b, BN_CTX *ctx) {
+  if (BN_num_bytes(p) > EC_MAX_SCALAR_BYTES) {
+    OPENSSL_PUT_ERROR(EC, EC_R_INVALID_FIELD);
+    return NULL;
+  }
+
   EC_GROUP *ret = ec_group_new(EC_GFp_mont_method());
   if (ret == NULL) {
     return NULL;
@@ -409,6 +414,12 @@
     // Additionally, |generator| must been created from
     // |EC_GROUP_new_curve_GFp|, not a copy, so that
     // |generator->group->generator| is set correctly.
+    OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+    return 0;
+  }
+
+  if (BN_num_bytes(order) > EC_MAX_SCALAR_BYTES) {
+    OPENSSL_PUT_ERROR(EC, EC_R_INVALID_FIELD);
     return 0;
   }
 
@@ -418,6 +429,31 @@
     return 0;
   }
 
+  // Require that p < 2×order. This simplifies some ECDSA operations.
+  //
+  // Note any curve which did not satisfy this must have been invalid or use a
+  // tiny prime (less than 17). We only work with prime order curves, so the
+  // number of points on the curve is the order. Thus Hasse's theorem gives:
+  //
+  //     |order - (p + 1)| <= 2×sqrt(p)
+  //         p + 1 - order <= 2×sqrt(p)
+  //     p + 1 - 2×sqrt(p) <= order
+  //       p + 1 - 2×(p/4)  < order       (p/4 > sqrt(p) for p >= 17)
+  //         p/2 < p/2 + 1  < order
+  //                     p  < 2×order
+  BIGNUM *tmp = BN_new();
+  if (tmp == NULL ||
+      !BN_lshift1(tmp, order)) {
+    BN_free(tmp);
+    return 0;
+  }
+  int ok = BN_cmp(tmp, &group->field) > 0;
+  BN_free(tmp);
+  if (!ok) {
+    OPENSSL_PUT_ERROR(EC, EC_R_INVALID_GROUP_ORDER);
+    return 0;
+  }
+
   EC_POINT *copy = EC_POINT_new(group);
   if (copy == NULL ||
       !EC_POINT_copy(copy, generator) ||

crypto/fipsmodule/ec/internal.h

diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h
index f065744..65ce61f 100644
--- a/crypto/fipsmodule/ec/internal.h
+++ b/crypto/fipsmodule/ec/internal.h
@@ -73,12 +73,24 @@
 #include <openssl/bn.h>
 #include <openssl/ex_data.h>
 #include <openssl/thread.h>
+#include <openssl/type_check.h>
+
+#include "../bn/internal.h"
 
 #if defined(__cplusplus)
 extern "C" {
 #endif
 
 
+// Cap the size of all field elements and scalars, including custom curves, to
+// 66 bytes, large enough to fit secp521r1 and brainpoolP512r1, which appear to
+// be the largest fields anyone plausibly uses.
+#define EC_MAX_SCALAR_BYTES 66
+#define EC_MAX_SCALAR_WORDS ((66 + BN_BYTES - 1) / BN_BYTES)
+
+OPENSSL_COMPILE_ASSERT(EC_MAX_SCALAR_WORDS <= BN_SMALL_MAX_WORDS,
+                       bn_small_functions_applicable);
+
 struct ec_method_st {
   int (*group_init)(EC_GROUP *);
   void (*group_finish)(EC_GROUP *);