Add support for primality checking

Project Wycheproof's primality_tests.json contain a set of 280 numbers
that trigger edge cases in Miller-Rabin and related checks. libcrypto's
Miller-Rabin test is known to be rather poor, hopefully we will soon see
a diff on tech that improves on this.

This extends the Go test in the usual way and also adds a perl script
that allows testing on non-Go architectures.

Deliberately not yet linked to regress since the tests are flaky with
the current BN_is_prime_ex() implementatation.

4 files changed, 218 insertions, 10 deletions

diff --git a/regress/lib/libcrypto/wycheproof/Makefile b/regress/lib/libcrypto/wycheproof/Makefile
index 0fcde086f7d..2e1d16b1653 100644
--- a/regress/lib/libcrypto/wycheproof/Makefile
+++ b/regress/lib/libcrypto/wycheproof/Makefile
@@ -1,17 +1,21 @@
-# $OpenBSD: Makefile,v 1.3 2019/04/24 20:25:19 bluhm Exp $
+# $OpenBSD: Makefile,v 1.4 2022/07/07 20:01:20 tb Exp $
 
-.if ! (make(clean) || make(cleandir) || make(obj))
-GO_VERSION != sh -c "(go version) 2>/dev/null || true"
-.endif
+WYCHEPROOF_TESTVECTORS = /usr/local/share/wycheproof/testvectors/
 
-.if empty(GO_VERSION)
+.if !exists(${WYCHEPROOF_TESTVECTORS})
 regress:
-	@echo package go is required for this regress
+	@echo package wycheproof-testvectors is required for this regress
+	@echo package go should be installed if available
 	@echo SKIPPED
-.endif
+.else
+
+# REGRESS_TARGETS += regress-wycheproof-primes
+
+. if exists(/usr/local/bin/go)
 
-CLEANFILES+=wycheproof
-REGRESS_TARGETS=regress-wycheproof
+REGRESS_TARGETS += regress-wycheproof
+
+CLEANFILES +=	wycheproof
 
 audit: wycheproof
 	./wycheproof -v
@@ -24,4 +28,25 @@ regress-wycheproof: wycheproof
 
 .PHONY: audit
 
+. endif
+
+PROGS += wycheproof-primes
+
+LDADD =		-lcrypto
+DPADD =		${LIBCRYPTO}
+CFLAGS =	-I${.CURDIR} -I${.OBJDIR}
+
+primality_testcases.h: wycheproof-json.pl ${WYCHEPROOF_TESTVECTORS}/primality_test.json
+	perl ${.CURDIR}/wycheproof-json.pl > $@.tmp
+	mv -f $@.tmp $@
+
+wycheproof-primes: wycheproof-primes.c primality_testcases.h
+
+regress-wycheproof-primes: primality_testcases.h wycheproof-primes
+	./wycheproof-primes
+
+CLEANFILES +=	primality_testcases.h
+
+.endif
+
 .include <bsd.regress.mk>
diff --git a/regress/lib/libcrypto/wycheproof/wycheproof-json.pl b/regress/lib/libcrypto/wycheproof/wycheproof-json.pl
new file mode 100644
index 00000000000..01fa66f7f78
--- /dev/null
+++ b/regress/lib/libcrypto/wycheproof/wycheproof-json.pl
@@ -0,0 +1,71 @@
+# $OpenBSD: wycheproof-json.pl,v 1.1 2022/07/07 20:01:20 tb Exp $
+
+# Copyright (c) 2022 Joel Sing <jsing@openbsd.org>
+# Copyright (c) 2022 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
+# copyright notice and this permission notice appear in all copies.
+# 
+# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+
+use JSON::PP;
+
+$test_vector_path = "/usr/local/share/wycheproof/testvectors";
+
+open JSON, "$test_vector_path/primality_test.json" or die;
+@json = <JSON>;
+close JSON;
+
+$tv = JSON::PP::decode_json(join "\n", @json);
+$test_groups = %$tv{"testGroups"};
+
+my $wycheproof_struct = <<"EOL";
+struct wycheproof_testcase {
+	int id;
+	const char *value;
+	int acceptable;
+	int result;
+};
+
+struct wycheproof_testcase testcases[] = {
+EOL
+
+print $wycheproof_struct;
+
+foreach $test_group (@$test_groups) {
+	$test_group_type = %$test_group{"type"};
+	$test_group_tests = %$test_group{"tests"};
+
+	foreach $test_case (@$test_group_tests) {
+		%tc = %$test_case;
+
+		$tc_id = $tc{"tcId"};
+		$tc_value = $tc{"value"};
+		$tc_result = $tc{"result"};
+		$tc_flags = @{$tc{"flags"}};
+
+		my $result = $tc_result eq "valid" ? 1 : 0;
+
+		print "\t{\n";
+		print "\t\t.id = $tc_id,\n";
+		print "\t\t.value = \"$tc_value\",\n";
+		print "\t\t.result = $result,\n";
+
+		if ($tc_result eq "acceptable") {
+			print "\t\t.acceptable = 1,\n";
+		}
+
+		print "\t},\n";
+	}
+}
+
+print "};\n\n";
+
+print "#define N_TESTS (sizeof(testcases) / sizeof(testcases[0]))\n"
diff --git a/regress/lib/libcrypto/wycheproof/wycheproof-primes.c b/regress/lib/libcrypto/wycheproof/wycheproof-primes.c
new file mode 100644
index 00000000000..669531d1356
--- /dev/null
+++ b/regress/lib/libcrypto/wycheproof/wycheproof-primes.c
@@ -0,0 +1,63 @@
+/*	$OpenBSD: wycheproof-primes.c,v 1.1 2022/07/07 20:01:20 tb Exp $ */
+/*
+ * Copyright (c) 2022 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
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <err.h>
+#include <stdio.h>
+
+#include <openssl/bn.h>
+
+#include "primality_testcases.h"
+
+int
+primality_test(struct wycheproof_testcase *test)
+{
+	BIGNUM *value = NULL;
+	int ret;
+	int failed = 1;
+
+	if (!BN_hex2bn(&value, test->value))
+		errx(1, "%d: failed to set value \"%s\"", test->id, test->value);
+
+	if ((ret = BN_is_prime_ex(value, BN_prime_checks, NULL, NULL)) < 0)
+		errx(1, "%d: BN_is_prime_ex errored", test->id);
+
+	if (ret != test->result && !test->acceptable) {
+		fprintf(stderr, "%d failed, want %d, got %d\n", test->id,
+		    test->result, ret);
+		goto err;
+	}
+
+	failed = 0;
+ err:
+	BN_free(value);
+
+	return failed;
+}
+
+int
+main(void)
+{
+	size_t i;
+	int failed = 0;
+
+	for (i = 0; i < N_TESTS; i++)
+		failed |= primality_test(&testcases[i]);
+
+	printf("%s\n", failed ? "FAILED" : "SUCCESS");
+
+	return failed;
+}
diff --git a/regress/lib/libcrypto/wycheproof/wycheproof.go b/regress/lib/libcrypto/wycheproof/wycheproof.go
index bd45a733b44..a638d0fdd94 100644
--- a/regress/lib/libcrypto/wycheproof/wycheproof.go
+++ b/regress/lib/libcrypto/wycheproof/wycheproof.go
@@ -1,4 +1,4 @@
-/* $OpenBSD: wycheproof.go,v 1.126 2022/05/05 18:34:27 tb Exp $ */
+/* $OpenBSD: wycheproof.go,v 1.127 2022/07/07 20:01:20 tb Exp $ */
 /*
  * Copyright (c) 2018 Joel Sing <jsing@openbsd.org>
  * Copyright (c) 2018,2019,2022 Theo Buehler <tb@openbsd.org>
@@ -349,6 +349,19 @@ type wycheproofTestGroupKW struct {
 	Tests   []*wycheproofTestKW `json:"tests"`
 }
 
+type wycheproofTestPrimality struct {
+	TCID    int      `json:"tcId"`
+	Comment string   `json:"comment"`
+	Value   string   `json:"value"`
+	Result  string   `json:"result"`
+	Flags   []string `json:"flags"`
+}
+
+type wycheproofTestGroupPrimality struct {
+	Type  string                     `json:"type"`
+	Tests []*wycheproofTestPrimality `json:"tests"`
+}
+
 type wycheproofTestRSA struct {
 	TCID    int      `json:"tcId"`
 	Comment string   `json:"comment"`
@@ -2223,6 +2236,35 @@ func runKWTestGroup(algorithm string, wtg *wycheproofTestGroupKW) bool {
 	return success
 }
 
+func runPrimalityTest(wt *wycheproofTestPrimality) bool {
+	var bnValue *C.BIGNUM
+	value := C.CString(wt.Value)
+	if C.BN_hex2bn(&bnValue, value) == 0 {
+		log.Fatal("Failed to set bnValue")
+	}
+	C.free(unsafe.Pointer(value))
+	defer C.BN_free(bnValue)
+
+	ret := C.BN_is_prime_ex(bnValue, C.BN_prime_checks, (*C.BN_CTX)(unsafe.Pointer(nil)), (*C.BN_GENCB)(unsafe.Pointer(nil)))
+	success := wt.Result == "acceptable" || (ret == 0 && wt.Result == "invalid") || (ret == 1 && wt.Result == "valid")
+	if !success {
+		fmt.Printf("FAIL: Test case %d (%q) %v failed - got %d, want %v\n", wt.TCID, wt.Comment, wt.Flags, ret, wt.Result)
+	}
+	return success
+}
+
+func runPrimalityTestGroup(algorithm string, wtg *wycheproofTestGroupPrimality) bool {
+	fmt.Printf("Running %v test group...\n", algorithm)
+
+	success := true
+	for _, wt := range wtg.Tests {
+		if !runPrimalityTest(wt) {
+			success = false
+		}
+	}
+	return success
+}
+
 func runRsaesOaepTest(rsa *C.RSA, sha *C.EVP_MD, mgfSha *C.EVP_MD, wt *wycheproofTestRsaes) bool {
 	ct, err := hex.DecodeString(wt.CT)
 	if err != nil {
@@ -2733,6 +2775,8 @@ func runTestVectors(path string, variant testVariant) bool {
 		wtg = &wycheproofTestGroupHmac{}
 	case "KW":
 		wtg = &wycheproofTestGroupKW{}
+	case "PrimalityTest":
+		wtg = &wycheproofTestGroupPrimality{}
 	case "RSAES-OAEP":
 		wtg = &wycheproofTestGroupRsaesOaep{}
 	case "RSAES-PKCS1-v1_5":
@@ -2812,6 +2856,10 @@ func runTestVectors(path string, variant testVariant) bool {
 			if !runKWTestGroup(wtv.Algorithm, wtg.(*wycheproofTestGroupKW)) {
 				success = false
 			}
+		case "PrimalityTest":
+			if !runPrimalityTestGroup(wtv.Algorithm, wtg.(*wycheproofTestGroupPrimality)) {
+				success = false
+			}
 		case "RSAES-OAEP":
 			if !runRsaesOaepTestGroup(wtv.Algorithm, wtg.(*wycheproofTestGroupRsaesOaep)) {
 				success = false
@@ -2875,6 +2923,7 @@ func main() {
 		{"HKDF", "hkdf_sha*_test.json", Normal},
 		{"HMAC", "hmac_sha*_test.json", Normal},
 		{"KW", "kw_test.json", Normal},
+		{"Primality test", "primality_test.json", Skip}, // XXX
 		{"RSA", "rsa_*test.json", Normal},
 		{"X25519", "x25519_test.json", Normal},
 		{"X25519 ASN", "x25519_asn_test.json", Skip},