Enforce that EC Parameters correspond to a builtin curve

EC parameters are very general. While there are some minimal sanity checks,
for the parameters due to DoS risks found in the last decade, the elliptic
curve code is poorly written and a target rich environment for NULL
dereferences, busy loops, expensive computations and whatever other
nastiness you can think of. It is not too hard to come up with parameters
that reach very ugly code. While we have removed for the worst of it (the
"fast" nist code and GF2m come to mind), the code very much resembles the
Augean Stables.

Unfortunately, curve parameters are still in use - even mandatory in some
contexts - for example in machine-readable travel documents signed by ICAO
country signing certification authorities (see ICAO Doc 9303).

To avoid many of these DoS vectors, start enforcing that we know what the
curve parameters are about, namely that they correspond to a builtin curve.
This way we know that the parameters are at least as good as the standards
we implement and checking this is cheap:

Translate curve parameters into the ad hoc representation in the builtin
curve code and check there's a match. That's very cheap since most curves
are distinguished by cofactor and parameter length and we need to use an
actual parameter comparison for at most half a dozen curves, usually only
one or two.

ok jsing

3 files changed, 227 insertions, 3 deletions

diff --git a/lib/libcrypto/ec/ec_asn1.c b/lib/libcrypto/ec/ec_asn1.c
index 289bc3b2719..548afb2d1a8 100644
--- a/lib/libcrypto/ec/ec_asn1.c
+++ b/lib/libcrypto/ec/ec_asn1.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ec_asn1.c,v 1.74 2024/10/17 14:34:06 tb Exp $ */
+/* $OpenBSD: ec_asn1.c,v 1.75 2024/10/18 17:27:07 tb Exp $ */
 /*
  * Written by Nils Larsch for the OpenSSL project.
  */
@@ -993,6 +993,8 @@ ec_asn1_parameters2group(const ECPARAMETERS *params)
 
 	if (!ec_asn1_parameters_extract_prime_group(params, &group))
 		goto err;
+	if (!ec_group_is_builtin_curve(group))
+		goto err;
 
 	return group;
 
diff --git a/lib/libcrypto/ec/ec_curve.c b/lib/libcrypto/ec/ec_curve.c
index dc7779358d0..2529229ba57 100644
--- a/lib/libcrypto/ec/ec_curve.c
+++ b/lib/libcrypto/ec/ec_curve.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ec_curve.c,v 1.43 2024/03/24 06:05:41 tb Exp $ */
+/* $OpenBSD: ec_curve.c,v 1.44 2024/10/18 17:27:07 tb Exp $ */
 /*
  * Written by Nils Larsch for the OpenSSL project.
  */
@@ -69,6 +69,7 @@
  *
  */
 
+#include <limits.h>
 #include <string.h>
 
 #include <openssl/opensslconf.h>
@@ -2457,6 +2458,225 @@ EC_GROUP_new_by_curve_name(int nid)
 }
 LCRYPTO_ALIAS(EC_GROUP_new_by_curve_name);
 
+static void
+ec_list_element_free(struct ec_list_element *curve)
+{
+	if (curve == NULL)
+		return;
+
+	/* PERM UGLY CASTS */
+	free((uint8_t *)curve->seed);
+	free((uint8_t *)curve->p);
+	free((uint8_t *)curve->a);
+	free((uint8_t *)curve->b);
+	free((uint8_t *)curve->x);
+	free((uint8_t *)curve->y);
+	free((uint8_t *)curve->order);
+
+	free(curve);
+}
+
+static int
+ec_list_element_encode_parameter(const BIGNUM *bn, int param_len,
+    const uint8_t **out_param)
+{
+	uint8_t *buf = NULL;
+	int ret = 0;
+
+	if (out_param == NULL || *out_param != NULL)
+		goto err;
+
+	if ((buf = calloc(1, param_len)) == NULL)
+		goto err;
+	if (BN_bn2binpad(bn, buf, param_len) != param_len)
+		goto err;
+
+	*out_param = buf;
+	buf = NULL;
+
+	ret = 1;
+
+ err:
+	free(buf);
+
+	return ret;
+}
+
+static struct ec_list_element *
+ec_list_element_from_group(const EC_GROUP *group)
+{
+	struct ec_list_element *curve = NULL;
+	BN_CTX *ctx;
+	BIGNUM *p, *a, *b, *x, *y;
+	const EC_POINT *generator = NULL;
+	const BIGNUM *order, *cofactor;
+	size_t seed_len;
+
+	if ((ctx = BN_CTX_new()) == NULL)
+		goto err;
+	BN_CTX_start(ctx);
+
+	if ((p = BN_CTX_get(ctx)) == NULL)
+		goto err;
+	if ((a = BN_CTX_get(ctx)) == NULL)
+		goto err;
+	if ((b = BN_CTX_get(ctx)) == NULL)
+		goto err;
+	if ((x = BN_CTX_get(ctx)) == NULL)
+		goto err;
+	if ((y = BN_CTX_get(ctx)) == NULL)
+		goto err;
+
+	if (!EC_GROUP_get_curve(group, p, a, b, ctx))
+		goto err;
+	if ((generator = EC_GROUP_get0_generator(group)) == NULL)
+		goto err;
+	if (!EC_POINT_get_affine_coordinates(group, generator, x, y, ctx))
+		goto err;
+	if ((order = EC_GROUP_get0_order(group)) == NULL)
+		goto err;
+
+	if ((curve = calloc(1, sizeof(*curve))) == NULL)
+		goto err;
+
+	curve->param_len = BN_num_bytes(p);
+	if (BN_num_bytes(order) > curve->param_len)
+		curve->param_len = BN_num_bytes(order);
+
+	if (!ec_list_element_encode_parameter(p, curve->param_len, &curve->p))
+		goto err;
+	if (!ec_list_element_encode_parameter(a, curve->param_len, &curve->a))
+		goto err;
+	if (!ec_list_element_encode_parameter(b, curve->param_len, &curve->b))
+		goto err;
+	if (!ec_list_element_encode_parameter(x, curve->param_len, &curve->x))
+		goto err;
+	if (!ec_list_element_encode_parameter(y, curve->param_len, &curve->y))
+		goto err;
+	if (!ec_list_element_encode_parameter(order, curve->param_len, &curve->order))
+		goto err;
+
+	if ((cofactor = EC_GROUP_get0_cofactor(group)) != NULL) {
+		BN_ULONG cofactor_word;
+
+		if ((cofactor_word = BN_get_word(cofactor)) == BN_MASK2)
+			goto err;
+		if (cofactor_word > INT_MAX)
+			goto err;
+
+		curve->cofactor = cofactor_word;
+	}
+
+	if ((seed_len = EC_GROUP_get_seed_len(group)) > 0) {
+		uint8_t *seed;
+
+		if (seed_len > INT_MAX)
+			goto err;
+		if ((seed = calloc(1, seed_len)) == NULL)
+			goto err;
+		memcpy(seed, EC_GROUP_get0_seed(group), seed_len);
+
+		curve->seed = seed;
+		curve->seed_len = seed_len;
+	}
+
+	BN_CTX_end(ctx);
+	BN_CTX_free(ctx);
+
+	return curve;
+
+ err:
+	BN_CTX_end(ctx);
+	BN_CTX_free(ctx);
+
+	ec_list_element_free(curve);
+
+	return NULL;
+}
+
+static int
+ec_list_element_cmp(const struct ec_list_element *a, const struct ec_list_element *b)
+{
+	int cmp;
+
+	/* Treat nid as optional. The OID isn't part of EC parameters. */
+	if (a->nid != NID_undef && b->nid != NID_undef) {
+		if (a->nid < b->nid)
+			return -1;
+		if (a->nid > b->nid)
+			return 1;
+	}
+
+	if (a->cofactor < b->cofactor)
+		return -1;
+	if (a->cofactor > b->cofactor)
+		return 1;
+	if (a->param_len < b->param_len)
+		return -1;
+	if (a->param_len > b->param_len)
+		return 1;
+
+	if ((cmp = memcmp(a->p, b->p, a->param_len)) != 0)
+		return cmp;
+	if ((cmp = memcmp(a->a, b->a, a->param_len)) != 0)
+		return cmp;
+	if ((cmp = memcmp(a->b, b->b, a->param_len)) != 0)
+		return cmp;
+	if ((cmp = memcmp(a->x, b->x, a->param_len)) != 0)
+		return cmp;
+	if ((cmp = memcmp(a->y, b->y, a->param_len)) != 0)
+		return cmp;
+	if ((cmp = memcmp(a->order, b->order, a->param_len)) != 0)
+		return cmp;
+
+	/* Seed is optional, not used for computation. Must match if present. */
+	if (a->seed_len != 0 && b->seed_len != 0) {
+		if (a->seed_len < b->seed_len)
+			return -1;
+		if (a->seed_len > b->seed_len)
+			return 1;
+		if (a->seed != NULL && b->seed != NULL) {
+			if ((cmp = memcmp(a->seed, b->seed, a->seed_len)) != 0)
+				return cmp;
+		}
+	}
+
+	return 0;
+}
+
+static int
+ec_group_nid_from_curve(const struct ec_list_element *curve)
+{
+	size_t i;
+
+	for (i = 0; i < CURVE_LIST_LENGTH; i++) {
+		if (ec_list_element_cmp(curve, &curve_list[i]) == 0)
+			return curve_list[i].nid;
+	}
+
+	return NID_undef;
+}
+
+int
+ec_group_is_builtin_curve(const EC_GROUP *group)
+{
+	struct ec_list_element *curve;
+	int ret = 0;
+
+	if ((curve = ec_list_element_from_group(group)) == NULL)
+		goto err;
+
+	if (ec_group_nid_from_curve(curve) == NID_undef)
+		goto err;
+
+	ret = 1;
+
+ err:
+	ec_list_element_free(curve);
+
+	return ret;
+}
+
 size_t
 EC_get_builtin_curves(EC_builtin_curve *r, size_t nitems)
 {
diff --git a/lib/libcrypto/ec/ec_local.h b/lib/libcrypto/ec/ec_local.h
index ca55770ba83..b837e291f7c 100644
--- a/lib/libcrypto/ec/ec_local.h
+++ b/lib/libcrypto/ec/ec_local.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: ec_local.h,v 1.29 2024/10/15 06:27:43 tb Exp $ */
+/* $OpenBSD: ec_local.h,v 1.30 2024/10/18 17:27:07 tb Exp $ */
 /*
  * Originally written by Bodo Moeller for the OpenSSL project.
  */
@@ -355,6 +355,8 @@ int EC_POINT_set_Jprojective_coordinates(const EC_GROUP *group, EC_POINT *p,
 int EC_POINT_get_Jprojective_coordinates(const EC_GROUP *group,
     const EC_POINT *p, BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx);
 
+int ec_group_is_builtin_curve(const EC_GROUP *group);
+
 /* Public API in OpenSSL */
 const BIGNUM *EC_GROUP_get0_cofactor(const EC_GROUP *group);
 const BIGNUM *EC_GROUP_get0_order(const EC_GROUP *group);