Reimplement a variant of the bn_mod_exp tests from scratch

This exercises the same corner cases as bn_mod_exp and a few more.
With input from jsing

1 files changed, 202 insertions, 2 deletions

diff --git a/regress/lib/libcrypto/bn/bn_mod_exp_zero.c b/regress/lib/libcrypto/bn/bn_mod_exp_zero.c
index 292983e86ba..23cfffc5b66 100644
--- a/regress/lib/libcrypto/bn/bn_mod_exp_zero.c
+++ b/regress/lib/libcrypto/bn/bn_mod_exp_zero.c
@@ -1,7 +1,7 @@
-/*	$OpenBSD: bn_mod_exp_zero.c,v 1.2 2023/03/15 00:41:04 tb Exp $ */
+/*	$OpenBSD: bn_mod_exp_zero.c,v 1.3 2023/03/18 08:55:42 tb Exp $ */
 
 /*
- * Copyright (c) 2022 Theo Buehler <tb@openbsd.org>
+ * Copyright (c) 2022,2023 Theo Buehler <tb@openbsd.org>
  *
  * Permission to use, copy, modify, and distribute this software for any
  * purpose with or without fee is hereby granted, provided that the above
@@ -176,12 +176,212 @@ run_bn_mod_exp_zero_tests(void)
 	return failed;
 }
 
+#define N_MOD_EXP_TESTS	400
+
+static const struct mod_exp_test {
+	const char *name;
+	int (*mod_exp_fn)(BIGNUM *,const BIGNUM *, const BIGNUM *,
+	    const BIGNUM *, BN_CTX *);
+	int (*mod_exp_mont_fn)(BIGNUM *,const BIGNUM *, const BIGNUM *,
+	    const BIGNUM *, BN_CTX *, BN_MONT_CTX *);
+} mod_exp_fn[] = {
+	INIT_MOD_EXP_FN(BN_mod_exp),
+	INIT_MOD_EXP_FN(BN_mod_exp_ct),
+	INIT_MOD_EXP_FN(BN_mod_exp_nonct),
+	INIT_MOD_EXP_FN(BN_mod_exp_recp),
+	INIT_MOD_EXP_MONT_FN(BN_mod_exp_mont),
+	INIT_MOD_EXP_MONT_FN(BN_mod_exp_mont_ct),
+	INIT_MOD_EXP_MONT_FN(BN_mod_exp_mont_consttime),
+	INIT_MOD_EXP_MONT_FN(BN_mod_exp_mont_nonct),
+};
+
+#define N_MOD_EXP_FN (sizeof(mod_exp_fn) / sizeof(mod_exp_fn[0]))
+
+static int
+generate_bn(BIGNUM *bn, int avg_bits, int deviate, int force_odd)
+{
+	int bits;
+
+	if (avg_bits <= 0 || deviate <= 0 || deviate >= avg_bits)
+		return 0;
+
+	bits = avg_bits + arc4random_uniform(deviate) - deviate;
+
+	return BN_rand(bn, bits, 0, force_odd);
+}
+
+static int
+generate_test_triple(int reduce, BIGNUM *a, BIGNUM *p, BIGNUM *m, BN_CTX *ctx)
+{
+	BIGNUM *mmodified;
+	BN_ULONG multiple;
+	int avg = 2 * BN_BITS, deviate = BN_BITS / 2;
+	int ret = 0;
+
+	if (!generate_bn(a, avg, deviate, 0))
+		return 0;
+
+	if (!generate_bn(p, avg, deviate, 0))
+		return 0;
+
+	if (!generate_bn(m, avg, deviate, 1))
+		return 0;
+
+	if (reduce)
+		return BN_mod(a, a, m, ctx);
+
+	/*
+	 * Add a random multiple of m to a to test unreduced exponentiation.
+	 */
+
+	BN_CTX_start(ctx);
+
+	if ((mmodified = BN_CTX_get(ctx)) == NULL)
+		goto err;
+
+	if (BN_copy(mmodified, m) == NULL)
+		goto err;
+
+	multiple = arc4random_uniform(1023) + 2;
+
+	if (!BN_mul_word(mmodified, multiple))
+		goto err;
+
+	if (!BN_add(a, a, mmodified))
+		goto err;
+
+	ret = 1;
+ err:
+	BN_CTX_end(ctx);
+
+	return ret;
+}
+
+static void
+dump_results(const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
+    const BIGNUM *got, const BIGNUM *want, const char *name)
+{
+	printf("BN_mod_exp_simple() and %s() disagree", name);
+
+	printf("\nwant: ");
+	BN_print_fp(stdout, want);
+	printf("\ngot:  ");
+	BN_print_fp(stdout, got);
+
+	printf("\na: ");
+	BN_print_fp(stdout, a);
+	printf("\nb: ");
+	BN_print_fp(stdout, p);
+	printf("\nm: ");
+	BN_print_fp(stdout, m);
+	printf("\n\n");
+}
+
+static int
+test_mod_exp(const BIGNUM *want, const BIGNUM *a, const BIGNUM *p,
+    const BIGNUM *m, BN_CTX *ctx, const struct mod_exp_test *test)
+{
+	BIGNUM *got;
+	int ret = 0;
+
+	BN_CTX_start(ctx);
+
+	if ((got = BN_CTX_get(ctx)) == NULL)
+		goto err;
+
+	if (test->mod_exp_fn != NULL)
+		ret = test->mod_exp_fn(got, a, p, m, ctx);
+	else
+		ret = test->mod_exp_mont_fn(got, a, p, m, ctx, NULL);
+
+	if (!ret)
+		errx(1, "%s() failed", test->name);
+
+	if (BN_cmp(want, got) != 0) {
+		dump_results(a, p, m, want, got, test->name);
+		goto err;
+	}
+
+	ret = 1;
+
+ err:
+	BN_CTX_end(ctx);
+
+	return ret;
+}
+
+static int
+bn_mod_exp_test(int reduce, BIGNUM *want, BIGNUM *a, BIGNUM *p, BIGNUM *m,
+    BN_CTX *ctx)
+{
+	size_t i, j;
+	int failed = 0;
+
+	if (!generate_test_triple(reduce, a, p, m, ctx))
+		errx(1, "generate_test_triple");
+
+	for (i = 0; i < 4; i++) {
+		BN_set_negative(a, i & 1);
+		BN_set_negative(p, (i >> 1) & 1);
+
+		if ((BN_mod_exp_simple(want, a, p, m, ctx)) <= 0)
+			errx(1, "BN_mod_exp_simple");
+
+		for (j = 0; j < N_MOD_EXP_FN; j++) {
+			const struct mod_exp_test *test = &mod_exp_fn[j];
+
+			if (!test_mod_exp(want, a, p, m, ctx, test))
+				failed |= 1;
+		}
+	}
+
+	return failed;
+}
+
+static int
+run_bn_mod_exp_tests(void)
+{
+	BIGNUM *a, *p, *m, *want;
+	BN_CTX *ctx;
+	int i;
+	int reduce;
+	int failed = 0;
+
+	if ((ctx = BN_CTX_new()) == NULL)
+		errx(1, "BN_CTX_new");
+
+	BN_CTX_start(ctx);
+
+	if ((a = BN_CTX_get(ctx)) == NULL)
+		errx(1, "a = BN_CTX_get()");
+	if ((p = BN_CTX_get(ctx)) == NULL)
+		errx(1, "p = BN_CTX_get()");
+	if ((m = BN_CTX_get(ctx)) == NULL)
+		errx(1, "m = BN_CTX_get()");
+	if ((want = BN_CTX_get(ctx)) == NULL)
+		errx(1, "want = BN_CTX_get()");
+
+	reduce = 0;
+	for (i = 0; i < N_MOD_EXP_TESTS; i++)
+		failed |= bn_mod_exp_test(reduce, want, a, p, m, ctx);
+
+	reduce = 1;
+	for (i = 0; i < N_MOD_EXP_TESTS; i++)
+		failed |= bn_mod_exp_test(reduce, want, a, p, m, ctx);
+
+	BN_CTX_end(ctx);
+	BN_CTX_free(ctx);
+
+	return failed;
+}
+
 int
 main(void)
 {
 	int failed = 0;
 
 	failed |= run_bn_mod_exp_zero_tests();
+	failed |= run_bn_mod_exp_tests();
 
 	return failed;
 }