From f10885cdfe5071de91362106c0fb0b5b21ec8fa8 Mon Sep 17 00:00:00 2001 From: tb Date: Thu, 7 Jul 2022 20:01:20 +0000 Subject: [PATCH] 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. --- regress/lib/libcrypto/wycheproof/Makefile | 43 ++++++++--- .../libcrypto/wycheproof/wycheproof-json.pl | 71 +++++++++++++++++++ .../libcrypto/wycheproof/wycheproof-primes.c | 63 ++++++++++++++++ .../lib/libcrypto/wycheproof/wycheproof.go | 51 ++++++++++++- 4 files changed, 218 insertions(+), 10 deletions(-) create mode 100644 regress/lib/libcrypto/wycheproof/wycheproof-json.pl create mode 100644 regress/lib/libcrypto/wycheproof/wycheproof-primes.c 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 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 +# Copyright (c) 2022 Theo Buehler +# +# 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 = ; +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 + * + * 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 +#include + +#include + +#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 * Copyright (c) 2018,2019,2022 Theo Buehler @@ -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}, -- 2.20.1