From e5a554b79b2bc282794430de6918d535b52eb82c Mon Sep 17 00:00:00 2001 From: tb <> Date: Sat, 14 Jun 2025 07:50:37 +0000 Subject: ec_asn1_test: for curves that have a seed, validate the parameters a and b per X9.62, F.3.4.b. This ensures that the table entries in ec_curves.c for the NIST curves P-224, P-256, P-384, and P-521 are internally consistent and in particular that the seed is correct. --- src/regress/lib/libcrypto/ec/ec_asn1_test.c | 197 +++++++++++++++++++++++++++- 1 file changed, 195 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/regress/lib/libcrypto/ec/ec_asn1_test.c b/src/regress/lib/libcrypto/ec/ec_asn1_test.c index d9501922de..a4066ae732 100644 --- a/src/regress/lib/libcrypto/ec/ec_asn1_test.c +++ b/src/regress/lib/libcrypto/ec/ec_asn1_test.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ec_asn1_test.c,v 1.33 2025/05/04 05:00:03 tb Exp $ */ +/* $OpenBSD: ec_asn1_test.c,v 1.34 2025/06/14 07:50:37 tb Exp $ */ /* * Copyright (c) 2017, 2021 Joel Sing * Copyright (c) 2024 Theo Buehler @@ -20,9 +20,10 @@ #include #include -#include #include +#include #include +#include #include "ec_local.h" @@ -2348,6 +2349,197 @@ ec_group_check_private_keys(void) return failed; } +static void +ec_group_sha1_bignum(BIGNUM *out, const BIGNUM *in) +{ + char md[SHA_DIGEST_LENGTH]; + unsigned char *bin; + size_t bin_len; + + if (BN_num_bytes(in) <= 0) + errx(1, "%s: invalid bignum", __func__); + + bin_len = BN_num_bytes(in); + if ((bin = calloc(1, bin_len)) == NULL) + err(1, "calloc"); + if (BN_bn2bin(in, bin) <= 0) + errx(1, "BN_bn2bin"); + + SHA1(bin, bin_len, md); + free(bin); + + if (BN_bin2bn(md, sizeof(md), out) == NULL) + errx(1, "BN_bin2bn"); +} + +static int +ec_group_check_seed(const EC_builtin_curve *curve, BN_CTX *ctx) +{ + EC_GROUP *group = NULL; + BIGNUM *p, *a, *b, *pow2, *r, *seed_bn, *w; + const unsigned char *seed; + size_t seed_len; + int i, g, h, s, t; + int failed = 1; + + if ((group = EC_GROUP_new_by_curve_name(curve->nid)) == NULL) + errx(1, "EC_GROUP_new_by_curve_name"); + + BN_CTX_start(ctx); + + if ((p = BN_CTX_get(ctx)) == NULL) + errx(1, "p = BN_CTX_get()"); + if ((a = BN_CTX_get(ctx)) == NULL) + errx(1, "a = BN_CTX_get()"); + if ((b = BN_CTX_get(ctx)) == NULL) + errx(1, "b = BN_CTX_get()"); + if ((r = BN_CTX_get(ctx)) == NULL) + errx(1, "r = BN_CTX_get()"); + if ((pow2 = BN_CTX_get(ctx)) == NULL) + errx(1, "pow2 = BN_CTX_get()"); + if ((seed_bn = BN_CTX_get(ctx)) == NULL) + errx(1, "seed_bn = BN_CTX_get()"); + if ((w = BN_CTX_get(ctx)) == NULL) + errx(1, "w = BN_CTX_get()"); + + /* + * If the curve has a seed, verify that its parameters a and b have + * been selected using that seed, loosely following X9.62, F.3.4.b. + * Otherwise there's nothing to do. + */ + if ((seed = EC_GROUP_get0_seed(group)) == NULL) + goto done; + seed_len = EC_GROUP_get_seed_len(group); + + /* + * This isn't a requirement but happens to be the case for NIST + * curves - the only built-in curves that have a seed. + */ + if (seed_len != SHA_DIGEST_LENGTH) { + fprintf(stderr, "%s FAIL: unexpected seed length. " + "want %d, got %zu\n", __func__, SHA_DIGEST_LENGTH, seed_len); + goto err; + } + + /* Seed length in bits, per F.3.3.b. */ + g = 8 * seed_len; + + /* + * Prepare to build the verifiably random element r of GFp by + * concatenating the SHA-1 of modifications of the seed as a number. + */ + if (BN_bin2bn(seed, seed_len, seed_bn) == NULL) + errx(1, "BN_bin2bn"); + + if (!EC_GROUP_get_curve(group, p, a, b, ctx)) + errx(1, "EC_GROUP_get_curve"); + + t = BN_num_bits(p); /* bit length needed. */ + s = (t - 1) / 160; /* number of SHA-1 fitting in bit length. */ + h = t - 160 * s; /* remaining number of bits in r. */ + + /* + * Steps 1 - 3: compute hash of the seed and take h - 1 rightmost bits. + */ + + ec_group_sha1_bignum(r, seed_bn); + BN_zero(pow2); + if (!BN_set_bit(pow2, h - 1)) + errx(1, "BN_set_bit"); + if (!BN_mod(r, r, pow2, ctx)) + errx(1, "BN_nnmod"); + + /* + * Steps 4 - 6: for i from 1 to s do Wi = SHA-1(SEED + i mod 2^g), + * With W0 = r as already computed, let r = W0 || W1 || ... || Ws. + */ + + BN_zero(pow2); + if (!BN_set_bit(pow2, g)) + errx(1, "BN_set_bit"); + + for (i = 0; i < s; i++) { + /* + * This is a bit silly since the seed isn't going to have all + * its bits set, so BN_add_word(seed_bn, 1) would do, but for + * the sake of correctness... + */ + if (!BN_mod_add(seed_bn, seed_bn, BN_value_one(), pow2, ctx)) + errx(1, "BN_mod_add"); + + ec_group_sha1_bignum(w, seed_bn); + + if (!BN_lshift(r, r, 8 * SHA_DIGEST_LENGTH)) + errx(1, "BN_lshift"); + if (!BN_add(r, r, w)) + errx(1, "BN_add"); + } + + /* + * Step 7: check that r * b^2 == a^3 (mod p) + */ + + /* Compute r = r * b^2 (mod p). */ + if (!BN_mod_sqr(b, b, p, ctx)) + errx(1, "BN_mod_sqr"); + if (!BN_mod_mul(r, r, b, p, ctx)) + errx(1, "BN_mod_mul"); + + /* Compute a = a^3 (mod p). */ + if (!BN_mod_sqr(b, a, p, ctx)) + errx(1, "BN_mod_sqr"); + if (!BN_mod_mul(a, a, b, p, ctx)) + errx(1, "BN_mod_mul"); + + /* + * XXX - this assumes that a, b, p >= 0, so the results are in [0, p). + * This is currently enforced in the EC code. + */ + if (BN_cmp(r, a) != 0) { + fprintf(stderr, "FAIL: %s verification failed for %s\nr * b^2:\t", + __func__, curve->comment); + BN_print_fp(stderr, r); + fprintf(stderr, "\na^3:\t\t"); + BN_print_fp(stderr, a); + fprintf(stderr, "\n"); + goto err; + } + + done: + failed = 0; + + err: + BN_CTX_end(ctx); + EC_GROUP_free(group); + + return failed; +} + +static int +ec_group_check_seeds(void) +{ + BN_CTX *ctx = NULL; + EC_builtin_curve *all_curves = NULL; + size_t curve_id, ncurves; + int failed = 0; + + if ((ctx = BN_CTX_new()) == NULL) + errx(1, "BN_CTX_new"); + + ncurves = EC_get_builtin_curves(NULL, 0); + if ((all_curves = calloc(ncurves, sizeof(*all_curves))) == NULL) + err(1, "calloc builtin curves"); + EC_get_builtin_curves(all_curves, ncurves); + + for (curve_id = 0; curve_id < ncurves; curve_id++) + failed |= ec_group_check_seed(&all_curves[curve_id], ctx); + + free(all_curves); + BN_CTX_free(ctx); + + return failed; +} + int main(int argc, char **argv) { @@ -2359,6 +2551,7 @@ main(int argc, char **argv) failed |= ec_group_roundtrip_builtin_curves(); failed |= ec_group_non_builtin_curves(); failed |= ec_group_check_private_keys(); + failed |= ec_group_check_seeds(); return failed; } -- cgit v1.2.3-55-g6feb