diff options
| -rw-r--r-- | gmp/Makefile | 12 | ||||
| -rw-r--r-- | gmp/gmp_fp25519_a24.c | 78 | ||||
| -rw-r--r-- | gmp/gmp_fp25519_add.c | 80 | ||||
| -rw-r--r-- | gmp/gmp_fp25519_fred.c | 68 | ||||
| -rw-r--r-- | gmp/gmp_fp25519_inv.c | 74 | ||||
| -rw-r--r-- | gmp/gmp_fp25519_mul.c | 69 | ||||
| -rw-r--r-- | gmp/gmp_fp25519_mul2.c | 78 | ||||
| -rw-r--r-- | gmp/gmp_fp25519_red.c | 76 | ||||
| -rw-r--r-- | gmp/gmp_fp25519_red2.c | 92 | ||||
| -rw-r--r-- | gmp/gmp_fp25519_sqr.c | 65 | ||||
| -rw-r--r-- | gmp/gmp_fp25519_sqr2.c | 72 | ||||
| -rw-r--r-- | gmp/gmp_fp25519_sub.c | 79 | ||||
| -rwxr-xr-x | gmp/run.sh | 13 | ||||
| -rw-r--r-- | gmp/shim.h | 147 |
14 files changed, 1003 insertions, 0 deletions
diff --git a/gmp/Makefile b/gmp/Makefile new file mode 100644 index 0000000..4cc9d55 --- /dev/null +++ b/gmp/Makefile @@ -0,0 +1,12 @@ +CFLAGS ?= -O3 -march=native -fomit-frame-pointer + +TARGETS := $(basename $(wildcard *.c)) + +all: $(TARGETS) + +%: %.c + clang -o $@ $(CFLAGS) -I../bogus-include -fsanitize=fuzzer -lgmp $< +clean: + rm -f $(basename $(TARGETS)) *.log + +.PHONY: clean all diff --git a/gmp/gmp_fp25519_a24.c b/gmp/gmp_fp25519_a24.c new file mode 100644 index 0000000..75e4d7d --- /dev/null +++ b/gmp/gmp_fp25519_a24.c @@ -0,0 +1,78 @@ +/** + * Copyright (c) 2017 Armando Faz <armfazh@ic.unicamp.br>. All Rights Reserved. + * Institute of Computing. + * University of Campinas, Brazil. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation, version 2 or greater. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ +#include <assert.h> +#include "shim.h" +#include <gmp.h> +#include <string.h> + +/** + * Verifies that 0<= c=a24*a < 2^256 and that c be congruent to a24*a mod p + * @param Data Random binary data. + * @param Size Non-trivial input size is set -max_len=32 + * @return Always return 0 in case of success. + */ +#ifdef __cplusplus +extern "C" { +#endif + +int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + if (Size != 32) return 0; + const uint64_t a24 = 121666; + EltFp25519_1w_x64 a, get_c, want_c; + + mpz_t gmp_a, gmp_c, gmp_low, gmp_high, two_to_256; + mpz_init(gmp_a); + mpz_init(gmp_c); + mpz_init(gmp_low); + mpz_init(gmp_high); + + // two_to_256 = 2^256 + mpz_init_set_ui(two_to_256, 1); + mpz_mul_2exp(two_to_256, two_to_256, 256); + + setzero_EltFp25519_1w_x64(get_c); + setzero_EltFp25519_1w_x64(want_c); + + memcpy(a, Data + 0, 32); + + mul_a24_EltFp25519_1w_x64(get_c, a); + + mpz_import(gmp_a, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 0); + mpz_mul_ui(gmp_c, gmp_a, a24); + + while (mpz_cmp(gmp_c, two_to_256) >= 0) { + mpz_mod_2exp(gmp_low, gmp_c, 256); + mpz_div_2exp(gmp_high, gmp_c, 256); + mpz_mul_ui(gmp_high, gmp_high, 38); + mpz_add(gmp_c, gmp_low, gmp_high); + } + mpz_export(want_c, NULL, -1, SIZE_BYTES_FP25519, 0, 0, gmp_c); + + assert(memcmp(get_c, want_c, SIZE_BYTES_FP25519) == 0); + + mpz_clear(gmp_a); + mpz_clear(gmp_c); + mpz_clear(gmp_low); + mpz_clear(gmp_high); + mpz_clear(two_to_256); + return 0; +} + +#ifdef __cplusplus +} +#endif diff --git a/gmp/gmp_fp25519_add.c b/gmp/gmp_fp25519_add.c new file mode 100644 index 0000000..7c2751c --- /dev/null +++ b/gmp/gmp_fp25519_add.c @@ -0,0 +1,80 @@ +/** + * Copyright (c) 2017 Armando Faz <armfazh@ic.unicamp.br>. All Rights Reserved. + * Institute of Computing. + * University of Campinas, Brazil. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation, version 2 or greater. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ +#include <assert.h> +#include "shim.h" +#include <gmp.h> +#include <string.h> + +/** + * Verifies that 0 <= c=a+b < 2^256 and that c be congruent to a+b mod p + * @param Data Random binary data. + * @param Size Non-trivial input size is set -max_len=64 + * @return Always return 0 in case of success. + */ +#ifdef __cplusplus +extern "C" { +#endif + +int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + if (Size != 2 * 32) return 0; + + EltFp25519_1w_x64 a, b, get_c, want_c; + + mpz_t gmp_a, gmp_b, gmp_c, two_prime, two_to_256; + mpz_init(gmp_a); + mpz_init(gmp_b); + mpz_init(gmp_c); + + // two_prime = 2^256-38 + mpz_init_set_ui(two_prime, 1); + mpz_mul_2exp(two_prime, two_prime, 256); + mpz_sub_ui(two_prime, two_prime, 38); + + // two_to_256 = 2^256 + mpz_init_set_ui(two_to_256, 1); + mpz_mul_2exp(two_to_256, two_to_256, 256); + + memcpy(a, Data + 0, 32); + memcpy(b, Data + 32, 32); + + setzero_EltFp25519_1w_x64(get_c); + setzero_EltFp25519_1w_x64(want_c); + + add_EltFp25519_1w_x64(get_c, a, b); + + mpz_import(gmp_a, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 0); + mpz_import(gmp_b, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 32); + + mpz_add(gmp_c, gmp_a, gmp_b); + while (mpz_cmp(gmp_c, two_to_256) >= 0) { + mpz_sub(gmp_c, gmp_c, two_prime); + } + mpz_export(want_c, NULL, -1, SIZE_BYTES_FP25519, 0, 0, gmp_c); + assert(memcmp(get_c, want_c, SIZE_BYTES_FP25519) == 0); + + mpz_clear(gmp_a); + mpz_clear(gmp_b); + mpz_clear(gmp_c); + mpz_clear(two_prime); + mpz_clear(two_to_256); + return 0; +} + +#ifdef __cplusplus +} +#endif diff --git a/gmp/gmp_fp25519_fred.c b/gmp/gmp_fp25519_fred.c new file mode 100644 index 0000000..cba671b --- /dev/null +++ b/gmp/gmp_fp25519_fred.c @@ -0,0 +1,68 @@ +/** + * Copyright (c) 2017 Armando Faz <armfazh@ic.unicamp.br>. All Rights Reserved. + * Institute of Computing. + * University of Campinas, Brazil. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation, version 2 or greater. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ +#include <assert.h> +#include "shim.h" +#include <gmp.h> +#include <string.h> + +/** + * Verifies that 0 <= c=a mod p < 2^255-19 for a number 0 <= a < 2^256 + * @param Data Random binary data. + * @param Size Non-trivial input size is set -max_len=32 + * @return Always return 0 in case of success. + */ +#ifdef __cplusplus +extern "C" { +#endif + +int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + if (Size != 32) return 0; + EltFp25519_1w_x64 a, get_c, want_c; + + mpz_t gmp_a, gmp_c, prime; + mpz_init(gmp_a); + mpz_init(gmp_c); + + // prime = p-2 = 2^255-19 + mpz_init_set_ui(prime, 1); + mpz_mul_2exp(prime, prime, 255); + mpz_sub_ui(prime, prime, 19); + + setzero_EltFp25519_1w_x64(get_c); + setzero_EltFp25519_1w_x64(want_c); + + memcpy(a, Data + 0, 32); + + copy_EltFp25519_1w_x64(get_c, a); + fred_EltFp25519_1w_x64(get_c); + + mpz_import(gmp_a, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 0); + mpz_mod(gmp_c, gmp_a, prime); + mpz_export(want_c, NULL, -1, SIZE_BYTES_FP25519, 0, 0, gmp_c); + + assert(memcmp(get_c, want_c, SIZE_BYTES_FP25519) == 0); + + mpz_clear(gmp_a); + mpz_clear(gmp_c); + mpz_clear(prime); + return 0; +} + +#ifdef __cplusplus +} +#endif diff --git a/gmp/gmp_fp25519_inv.c b/gmp/gmp_fp25519_inv.c new file mode 100644 index 0000000..bf7c2f5 --- /dev/null +++ b/gmp/gmp_fp25519_inv.c @@ -0,0 +1,74 @@ +/** + * Copyright (c) 2017 Armando Faz <armfazh@ic.unicamp.br>. All Rights Reserved. + * Institute of Computing. + * University of Campinas, Brazil. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation, version 2 or greater. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ +#include <assert.h> +#include "shim.h" +#include <gmp.h> +#include <string.h> + +/** + * Verifies that 0 <= a < 2^256 and that c be congruent to a^-1 mod p + * @param Data Random binary data. + * @param Size Non-trivial input size is set -max_len=32 + * @return Always return 0 in case of success. + */ +#ifdef __cplusplus +extern "C" { +#endif + +int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + if (Size != 32) return 0; + + EltFp25519_1w_x64 a, get_c, want_c; + + mpz_t gmp_a, gmp_c, prime, prime_minus_two; + mpz_init(gmp_a); + mpz_init(gmp_c); + + // two_prime = 2^255-19 + mpz_init_set_ui(prime, 1); + mpz_mul_2exp(prime, prime, 255); + mpz_sub_ui(prime, prime, 19); + + // expo = p-2 = 2^255-19-2 = 2^255-21 + mpz_init_set_ui(prime_minus_two, 1); + mpz_mul_2exp(prime_minus_two, prime_minus_two, 255); + mpz_sub_ui(prime_minus_two, prime_minus_two, 21); + + memcpy(a, Data + 0, 32); + + setzero_EltFp25519_1w_x64(get_c); + setzero_EltFp25519_1w_x64(want_c); + + inv_EltFp25519_1w_x64(get_c, a); + fred_EltFp25519_1w_x64(get_c); + + mpz_import(gmp_a, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 0); + mpz_powm(gmp_c, gmp_a, prime_minus_two, prime); + mpz_export(want_c, NULL, -1, SIZE_BYTES_FP25519, 0, 0, gmp_c); + assert(memcmp(get_c, want_c, SIZE_BYTES_FP25519) == 0); + + mpz_clear(gmp_a); + mpz_clear(gmp_c); + mpz_clear(prime); + mpz_clear(prime_minus_two); + return 0; +} + +#ifdef __cplusplus +} +#endif diff --git a/gmp/gmp_fp25519_mul.c b/gmp/gmp_fp25519_mul.c new file mode 100644 index 0000000..ebdd5bc --- /dev/null +++ b/gmp/gmp_fp25519_mul.c @@ -0,0 +1,69 @@ +/** + * Copyright (c) 2017 Armando Faz <armfazh@ic.unicamp.br>. All Rights Reserved. + * Institute of Computing. + * University of Campinas, Brazil. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation, version 2 or greater. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ +#include <assert.h> +#include "shim.h" +#include <gmp.h> +#include <string.h> + +/** + * Verifies that 0 <= c=a*b < 2^512 + * @param Data Random binary data. + * @param Size Non-trivial input size is set -max_len=64 + * @return Always return 0 in case of success. + */ +#ifdef __cplusplus +extern "C" { +#endif + +int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + if (Size != 2 * 32) return 0; + + EltFp25519_1w_x64 a, b; + EltFp25519_1w_Buffer_x64 get_c, want_c; + + mpz_t gmp_a, gmp_b, gmp_c; + mpz_init(gmp_a); + mpz_init(gmp_b); + mpz_init(gmp_c); + + memcpy(a, Data + 0, 32); + memcpy(b, Data + 32, 32); + + setzero_EltFp25519_1w_x64(get_c); + setzero_EltFp25519_1w_x64(want_c); + setzero_EltFp25519_1w_x64(get_c + NUM_WORDS_ELTFP25519_X64); + setzero_EltFp25519_1w_x64(want_c + NUM_WORDS_ELTFP25519_X64); + + mul_256x256_integer_x64(get_c, a, b); + + mpz_import(gmp_a, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 0); + mpz_import(gmp_b, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 32); + + mpz_mul(gmp_c, gmp_a, gmp_b); + mpz_export(want_c, NULL, -1, 2 * SIZE_BYTES_FP25519, 0, 0, gmp_c); + assert(memcmp(get_c, want_c, 2 * SIZE_BYTES_FP25519) == 0); + + mpz_clear(gmp_a); + mpz_clear(gmp_b); + mpz_clear(gmp_c); + return 0; +} + +#ifdef __cplusplus +} +#endif diff --git a/gmp/gmp_fp25519_mul2.c b/gmp/gmp_fp25519_mul2.c new file mode 100644 index 0000000..3fd0308 --- /dev/null +++ b/gmp/gmp_fp25519_mul2.c @@ -0,0 +1,78 @@ +/** + * Copyright (c) 2017 Armando Faz <armfazh@ic.unicamp.br>. All Rights Reserved. + * Institute of Computing. + * University of Campinas, Brazil. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation, version 2 or greater. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ +#include <assert.h> +#include "shim.h" +#include <gmp.h> +#include <string.h> + +/** + * Verifies that 0 <= c0=a0*b0 < 2^512 and 0 <= c1=a1*b1 < 2^512 + * @param Data Random binary data. + * @param Size Non-trivial input size is set -max_len=128 + * @return Always return 0 in case of success. + */ +#ifdef __cplusplus +extern "C" { +#endif + +int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + if (Size != 2 * 2 * 32) return 0; + + EltFp25519_2w_x64 a, b; + EltFp25519_2w_Buffer_x64 get_c, want_c; + + mpz_t gmp_a0, gmp_b0, gmp_c0, gmp_a1, gmp_b1, gmp_c1; + mpz_init(gmp_a0); + mpz_init(gmp_a1); + mpz_init(gmp_b0); + mpz_init(gmp_b1); + mpz_init(gmp_c0); + mpz_init(gmp_c1); + + memcpy(a, Data + 0, 64); + memcpy(b, Data + 64, 64); + + memset(get_c, 0, sizeof(get_c)); + memset(want_c, 0, sizeof(want_c)); + + mul2_256x256_integer_x64(get_c, a, b); + + mpz_import(gmp_a0, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 0); + mpz_import(gmp_a1, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 32); + mpz_import(gmp_b0, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 64); + mpz_import(gmp_b1, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 96); + + mpz_mul(gmp_c0, gmp_a0, gmp_b0); + mpz_mul(gmp_c1, gmp_a1, gmp_b1); + mpz_export(want_c, NULL, -1, 2 * SIZE_BYTES_FP25519, 0, 0, gmp_c0); + mpz_export(want_c + 2 * NUM_WORDS_ELTFP25519_X64, NULL, -1, + 2 * SIZE_BYTES_FP25519, 0, 0, gmp_c1); + assert(memcmp(get_c, want_c, sizeof(get_c)) == 0); + + mpz_clear(gmp_a0); + mpz_clear(gmp_a1); + mpz_clear(gmp_b0); + mpz_clear(gmp_b1); + mpz_clear(gmp_c0); + mpz_clear(gmp_c1); + return 0; +} + +#ifdef __cplusplus +} +#endif diff --git a/gmp/gmp_fp25519_red.c b/gmp/gmp_fp25519_red.c new file mode 100644 index 0000000..5f8d226 --- /dev/null +++ b/gmp/gmp_fp25519_red.c @@ -0,0 +1,76 @@ +/** + * Copyright (c) 2017 Armando Faz <armfazh@ic.unicamp.br>. All Rights Reserved. + * Institute of Computing. + * University of Campinas, Brazil. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation, version 2 or greater. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ +#include <assert.h> +#include "shim.h" +#include <gmp.h> +#include <string.h> + +/** + * Verifies that 0 <= c < 2^256 be congruent (mod p) to 0<= a < 2^512 + * @param Data Random binary data. + * @param Size Non-trivial input size is set -max_len=64 + * @return Always return 0 in case of success. + */ +#ifdef __cplusplus +extern "C" { +#endif + +int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + if (Size != 2 * 32) return 0; + EltFp25519_1w_x64 get_c, want_c; + EltFp25519_1w_Buffer_x64 a; + + mpz_t gmp_a, gmp_low, gmp_high, two_to_256; + mpz_init(gmp_a); + mpz_init(gmp_low); + mpz_init(gmp_high); + + // two_to_256 = 2^256 + mpz_init_set_ui(two_to_256, 1); + mpz_mul_2exp(two_to_256, two_to_256, 256); + + setzero_EltFp25519_1w_x64(get_c); + setzero_EltFp25519_1w_x64(want_c); + + memcpy(a, Data + 0, 64); + + red_EltFp25519_1w_x64(get_c, a); + + mpz_import(gmp_a, 2 * SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, + Data + 0); + + while (mpz_cmp(gmp_a, two_to_256) >= 0) { + mpz_mod_2exp(gmp_low, gmp_a, 256); + mpz_div_2exp(gmp_high, gmp_a, 256); + mpz_mul_ui(gmp_high, gmp_high, 38); + mpz_add(gmp_a, gmp_low, gmp_high); + } + mpz_export(want_c, NULL, -1, SIZE_BYTES_FP25519, 0, 0, gmp_a); + + assert(memcmp(get_c, want_c, SIZE_BYTES_FP25519) == 0); + + mpz_clear(gmp_a); + mpz_clear(gmp_low); + mpz_clear(gmp_high); + mpz_clear(two_to_256); + return 0; +} + +#ifdef __cplusplus +} +#endif diff --git a/gmp/gmp_fp25519_red2.c b/gmp/gmp_fp25519_red2.c new file mode 100644 index 0000000..ed29a30 --- /dev/null +++ b/gmp/gmp_fp25519_red2.c @@ -0,0 +1,92 @@ +/** + * Copyright (c) 2017 Armando Faz <armfazh@ic.unicamp.br>. All Rights Reserved. + * Institute of Computing. + * University of Campinas, Brazil. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation, version 2 or greater. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ +#include <assert.h> +#include "shim.h" +#include <gmp.h> +#include <string.h> + +/** + * Verifies that 0 <= c < 2^256 be congruent (mod p) to 0<= a < 2^512 + * @param Data Random binary data. + * @param Size Non-trivial input size is set -max_len=64 + * @return Always return 0 in case of success. + */ +#ifdef __cplusplus +extern "C" { +#endif + +int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + if (Size != 2 * 2 * 32) return 0; + + EltFp25519_2w_x64 get_c, want_c; + EltFp25519_2w_Buffer_x64 a; + + mpz_t gmp_a0, gmp_a1, gmp_low, gmp_high, two_to_256; + mpz_init(gmp_a0); + mpz_init(gmp_a1); + mpz_init(gmp_low); + mpz_init(gmp_high); + + // two_to_256 = 2^256 + mpz_init_set_ui(two_to_256, 1); + mpz_mul_2exp(two_to_256, two_to_256, 256); + + setzero_EltFp25519_1w_x64(get_c + 0); + setzero_EltFp25519_1w_x64(get_c + NUM_WORDS_ELTFP25519_X64); + setzero_EltFp25519_1w_x64(want_c + 0); + setzero_EltFp25519_1w_x64(want_c + NUM_WORDS_ELTFP25519_X64); + + memcpy(a, Data + 0, 128); + + red_EltFp25519_2w_x64(get_c, a); + + mpz_import(gmp_a0, 2 * SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, + Data + 0); + mpz_import(gmp_a1, 2 * SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, + Data + 64); + + while (mpz_cmp(gmp_a0, two_to_256) >= 0) { + mpz_mod_2exp(gmp_low, gmp_a0, 256); + mpz_div_2exp(gmp_high, gmp_a0, 256); + mpz_mul_ui(gmp_high, gmp_high, 38); + mpz_add(gmp_a0, gmp_low, gmp_high); + } + mpz_export(want_c, NULL, -1, SIZE_BYTES_FP25519, 0, 0, gmp_a0); + + while (mpz_cmp(gmp_a1, two_to_256) >= 0) { + mpz_mod_2exp(gmp_low, gmp_a1, 256); + mpz_div_2exp(gmp_high, gmp_a1, 256); + mpz_mul_ui(gmp_high, gmp_high, 38); + mpz_add(gmp_a1, gmp_low, gmp_high); + } + mpz_export(want_c + NUM_WORDS_ELTFP25519_X64, NULL, -1, SIZE_BYTES_FP25519, 0, + 0, gmp_a1); + + assert(memcmp(get_c, want_c, sizeof(get_c)) == 0); + + mpz_clear(gmp_a0); + mpz_clear(gmp_a1); + mpz_clear(gmp_low); + mpz_clear(gmp_high); + mpz_clear(two_to_256); + return 0; +} + +#ifdef __cplusplus +} +#endif diff --git a/gmp/gmp_fp25519_sqr.c b/gmp/gmp_fp25519_sqr.c new file mode 100644 index 0000000..3f85c84 --- /dev/null +++ b/gmp/gmp_fp25519_sqr.c @@ -0,0 +1,65 @@ +/** + * Copyright (c) 2017 Armando Faz <armfazh@ic.unicamp.br>. All Rights Reserved. + * Institute of Computing. + * University of Campinas, Brazil. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation, version 2 or greater. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ +#include <assert.h> +#include "shim.h" +#include <gmp.h> +#include <string.h> + +/** + * Verifies that 0 <= c=a*a < 2^512 + * @param Data Random binary data. + * @param Size Non-trivial input size is set -max_len=32 + * @return Always return 0 in case of success. + */ +#ifdef __cplusplus +extern "C" { +#endif + +int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + if (Size != 32) return 0; + + EltFp25519_1w_x64 a; + EltFp25519_1w_Buffer_x64 get_c, want_c; + + mpz_t gmp_a, gmp_c; + mpz_init(gmp_a); + mpz_init(gmp_c); + + memcpy(a, Data + 0, 32); + + setzero_EltFp25519_1w_x64(get_c); + setzero_EltFp25519_1w_x64(want_c); + setzero_EltFp25519_1w_x64(get_c + NUM_WORDS_ELTFP25519_X64); + setzero_EltFp25519_1w_x64(want_c + NUM_WORDS_ELTFP25519_X64); + + sqr_256x256_integer_x64(get_c, a); + + mpz_import(gmp_a, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 0); + + mpz_mul(gmp_c, gmp_a, gmp_a); + mpz_export(want_c, NULL, -1, 2 * SIZE_BYTES_FP25519, 0, 0, gmp_c); + assert(memcmp(get_c, want_c, 2 * SIZE_BYTES_FP25519) == 0); + + mpz_clear(gmp_a); + mpz_clear(gmp_c); + return 0; +} + +#ifdef __cplusplus +} +#endif diff --git a/gmp/gmp_fp25519_sqr2.c b/gmp/gmp_fp25519_sqr2.c new file mode 100644 index 0000000..132567a --- /dev/null +++ b/gmp/gmp_fp25519_sqr2.c @@ -0,0 +1,72 @@ +/** + * Copyright (c) 2017 Armando Faz <armfazh@ic.unicamp.br>. All Rights Reserved. + * Institute of Computing. + * University of Campinas, Brazil. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation, version 2 or greater. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ +#include <assert.h> +#include "shim.h" +#include <gmp.h> +#include <string.h> + +/** + * Verifies that 0 <= c0=a0*a0 < 2^512 and 0 <= c1=a1*a1 < 2^512 + * @param Data Random binary data. + * @param Size Non-trivial input size is set -max_len=64 + * @return Always return 0 in case of success. + */ +#ifdef __cplusplus +extern "C" { +#endif + +int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + if (Size != 2 * 32) return 0; + + EltFp25519_2w_x64 a; + EltFp25519_2w_Buffer_x64 get_c, want_c; + + mpz_t gmp_a0, gmp_c0, gmp_a1, gmp_c1; + mpz_init(gmp_a0); + mpz_init(gmp_a1); + mpz_init(gmp_c0); + mpz_init(gmp_c1); + + memcpy(a, Data + 0, 64); + + memset(get_c, 0, sizeof(get_c)); + memset(want_c, 0, sizeof(want_c)); + + sqr2_256x256_integer_x64(get_c, a); + + mpz_import(gmp_a0, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 0); + mpz_import(gmp_a1, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 32); + + mpz_mul(gmp_c0, gmp_a0, gmp_a0); + mpz_mul(gmp_c1, gmp_a1, gmp_a1); + + mpz_export(want_c, NULL, -1, 2 * SIZE_BYTES_FP25519, 0, 0, gmp_c0); + mpz_export(want_c + 2 * NUM_WORDS_ELTFP25519_X64, NULL, -1, + 2 * SIZE_BYTES_FP25519, 0, 0, gmp_c1); + assert(memcmp(get_c, want_c, sizeof(get_c)) == 0); + + mpz_clear(gmp_a0); + mpz_clear(gmp_a1); + mpz_clear(gmp_c0); + mpz_clear(gmp_c1); + return 0; +} + +#ifdef __cplusplus +} +#endif diff --git a/gmp/gmp_fp25519_sub.c b/gmp/gmp_fp25519_sub.c new file mode 100644 index 0000000..962e541 --- /dev/null +++ b/gmp/gmp_fp25519_sub.c @@ -0,0 +1,79 @@ +/** + * Copyright (c) 2017 Armando Faz <armfazh@ic.unicamp.br>. All Rights Reserved. + * Institute of Computing. + * University of Campinas, Brazil. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation, version 2 or greater. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ +#include <assert.h> +#include "shim.h" +#include <gmp.h> +#include <string.h> + +/** + * Verifies that 0 <= c=a-b < 2^256 and that c be congruent to a-b mod p + * @param Data Random binary data. + * @param Size Non-trivial input size is set -max_len=64 + * @return Always return 0 in case of success. + */ +#ifdef __cplusplus +extern "C" { +#endif + +int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + if (Size != 2 * 32) return 0; + + EltFp25519_1w_x64 a, b, get_c, want_c; + + mpz_t gmp_a, gmp_b, gmp_c, two_prime, zero; + mpz_init(gmp_a); + mpz_init(gmp_b); + mpz_init(gmp_c); + + // two_prime = 2^256-38 + mpz_init_set_ui(two_prime, 1); + mpz_mul_2exp(two_prime, two_prime, 256); + mpz_sub_ui(two_prime, two_prime, 38); + + // zero = 0 + mpz_init_set_ui(zero, 0); + + memcpy(a, Data + 0, 32); + memcpy(b, Data + 32, 32); + + setzero_EltFp25519_1w_x64(get_c); + setzero_EltFp25519_1w_x64(want_c); + + sub_EltFp25519_1w_x64(get_c, a, b); + + mpz_import(gmp_a, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 0); + mpz_import(gmp_b, SIZE_BYTES_FP25519, -1, sizeof(Data[0]), 0, 0, Data + 32); + + mpz_sub(gmp_c, gmp_a, gmp_b); + while (mpz_cmp(gmp_c, zero) < 0) { + mpz_add(gmp_c, gmp_c, two_prime); + } + mpz_export(want_c, NULL, -1, SIZE_BYTES_FP25519, 0, 0, gmp_c); + assert(memcmp(get_c, want_c, SIZE_BYTES_FP25519) == 0); + + mpz_clear(gmp_a); + mpz_clear(gmp_b); + mpz_clear(gmp_c); + mpz_clear(two_prime); + mpz_clear(zero); + return 0; +} + +#ifdef __cplusplus +} +#endif diff --git a/gmp/run.sh b/gmp/run.sh new file mode 100755 index 0000000..c89d313 --- /dev/null +++ b/gmp/run.sh @@ -0,0 +1,13 @@ +#!/bin/bash +mkdir -p gmp_fp25519_fred.logs && cd gmp_fp25519_fred.logs; ../gmp_fp25519_fred -max_len=32 -workers=5 -jobs=5 & cd .. +mkdir -p gmp_fp25519_sqr2.logs && cd gmp_fp25519_sqr2.logs; ../gmp_fp25519_sqr2 -max_len=64 -workers=5 -jobs=5 & cd .. +mkdir -p gmp_fp25519_inv.logs && cd gmp_fp25519_inv.logs; ../gmp_fp25519_inv -max_len=32 -workers=5 -jobs=5 & cd .. +mkdir -p gmp_fp25519_red2.logs && cd gmp_fp25519_red2.logs; ../gmp_fp25519_red2 -max_len=128 -workers=5 -jobs=5 & cd .. +mkdir -p gmp_fp25519_mul2.logs && cd gmp_fp25519_mul2.logs; ../gmp_fp25519_mul2 -max_len=128 -workers=5 -jobs=5 & cd .. +mkdir -p gmp_fp25519_sqr.logs && cd gmp_fp25519_sqr.logs; ../gmp_fp25519_sqr -max_len=32 -workers=5 -jobs=5 & cd .. +mkdir -p gmp_fp25519_red.logs && cd gmp_fp25519_red.logs; ../gmp_fp25519_red -max_len=64 -workers=5 -jobs=5 & cd .. +mkdir -p gmp_fp25519_add.logs && cd gmp_fp25519_add.logs; ../gmp_fp25519_add -max_len=64 -workers=5 -jobs=5 & cd .. +mkdir -p gmp_fp25519_a24.logs && cd gmp_fp25519_a24.logs; ../gmp_fp25519_a24 -max_len=32 -workers=5 -jobs=5 & cd .. +mkdir -p gmp_fp25519_sub.logs && cd gmp_fp25519_sub.logs; ../gmp_fp25519_sub -max_len=64 -workers=5 -jobs=5 & cd .. +mkdir -p gmp_fp25519_mul.logs && cd gmp_fp25519_mul.logs; ../gmp_fp25519_mul -max_len=64 -workers=5 -jobs=5 & cd .. +wait diff --git a/gmp/shim.h b/gmp/shim.h new file mode 100644 index 0000000..9ce3775 --- /dev/null +++ b/gmp/shim.h @@ -0,0 +1,147 @@ +#include <stdbool.h> +#include <string.h> +#include <assert.h> +#include <linux/types.h> +typedef __u64 u64; +typedef __u32 u32; +typedef __u8 u8; +typedef __s64 s64; +#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ +#define le64_to_cpup(a) __builtin_bswap64(*(a)) +#define le32_to_cpup(a) __builtin_bswap32(*(a)) +#define cpu_to_le64(a) __builtin_bswap64(a) +#else +#define le64_to_cpup(a) (*(a)) +#define le32_to_cpup(a) (*(a)) +#define cpu_to_le64(a) (a) +#endif +#ifndef __always_inline +#define __always_inline __inline __attribute__((__always_inline__)) +#endif +#ifndef noinline +#define noinline __attribute__((noinline)) +#endif +#ifndef __aligned +#define __aligned(x) __attribute__((aligned(x))) +#endif +#ifndef __force +#define __force +#endif +#ifndef memzero_explicit +#define memzero_explicit(a, b) +#endif +#ifndef __ro_after_init +#define __ro_after_init +#endif +#ifndef __init +#define __init +#endif +#define boot_cpu_has(a) true + +enum curve25519_lengths { + CURVE25519_POINT_SIZE = 32, +}; + +static inline void normalize_secret(u8 secret[CURVE25519_POINT_SIZE]) +{ + secret[0] &= 248; + secret[31] &= 127; + secret[31] |= 64; +} + +#include "../WireGuard/src/crypto/curve25519-x86_64.h" + +typedef u8 uint8_t; +typedef u64 uint64_t; +#define NUM_WORDS_ELTFP25519_X64 4 +#define SIZE_BYTES_FP25519 32 +typedef __aligned(32) uint64_t EltFp25519_1w_x64[NUM_WORDS_ELTFP25519_X64]; +typedef __aligned(32) uint64_t EltFp25519_1w_Buffer_x64[2 * NUM_WORDS_ELTFP25519_X64]; +typedef __aligned(32) uint64_t EltFp25519_2w_x64[2 * NUM_WORDS_ELTFP25519_X64]; +typedef __aligned(32) uint64_t EltFp25519_2w_Buffer_x64[4 * NUM_WORDS_ELTFP25519_X64]; +#define setzero_EltFp25519_1w_x64(a) setzero_eltfp25519_1w(a) +#define copy_EltFp25519_1w_x64(a, b) copy_eltfp25519_1w(a, b) + +static inline void mul2_256x256_integer_x64(uint64_t *const c, uint64_t *const a, + uint64_t *const b) +{ + EltFp25519_2w_Buffer_x64 other = { 0 }; + mul2_256x256_integer_adx(other, a, b); + mul2_256x256_integer_bmi2(c, a, b); + assert(!memcmp(other, c, sizeof(other))); +} + + +static inline void sqr2_256x256_integer_x64(uint64_t *const c, uint64_t *const a) +{ + EltFp25519_2w_Buffer_x64 other = { 0 }; + sqr2_256x256_integer_adx(other, a); + sqr2_256x256_integer_bmi2(c, a); + assert(!memcmp(other, c, sizeof(other))); +} + +static inline void red_EltFp25519_2w_x64(uint64_t *const c, uint64_t *const a) +{ + EltFp25519_2w_x64 other = { 0 }; + red_eltfp25519_2w_adx(other, a); + red_eltfp25519_2w_bmi2(c, a); + assert(!memcmp(other, c, sizeof(other))); +} + +static inline void mul_256x256_integer_x64(uint64_t *const c, uint64_t *const a, + uint64_t *const b) +{ + EltFp25519_1w_Buffer_x64 other = { 0 }; + mul_256x256_integer_adx(other, a, b); + mul_256x256_integer_bmi2(c, a, b); + assert(!memcmp(other, c, sizeof(other))); +} + +static inline void sqr_256x256_integer_x64(uint64_t *const c, uint64_t *const a) +{ + EltFp25519_1w_Buffer_x64 other = { 0 }; + sqr_256x256_integer_adx(other, a); + sqr_256x256_integer_bmi2(c, a); + assert(!memcmp(other, c, sizeof(other))); +} + +static inline void red_EltFp25519_1w_x64(uint64_t *const c, uint64_t *const a) +{ + EltFp25519_1w_x64 other = { 0 }; + red_eltfp25519_1w_adx(other, a); + red_eltfp25519_1w_bmi2(c, a); + assert(!memcmp(other, c, sizeof(other))); +} + +static inline void add_EltFp25519_1w_x64(uint64_t *const c, uint64_t *const a, + uint64_t *const b) +{ + EltFp25519_1w_x64 other = { 0 }; + add_eltfp25519_1w_adx(other, a, b); + add_eltfp25519_1w_bmi2(c, a, b); + assert(!memcmp(other, c, sizeof(other))); +} + +static inline void sub_EltFp25519_1w_x64(uint64_t *const c, uint64_t *const a, + uint64_t *const b) +{ + sub_eltfp25519_1w(c, a, b); +} + +static inline void mul_a24_EltFp25519_1w_x64(uint64_t *const c, uint64_t *const a) +{ + mul_a24_eltfp25519_1w(c, a); +} + +static inline void inv_EltFp25519_1w_x64(uint64_t *const c, uint64_t *const a) +{ + EltFp25519_1w_x64 other = { 0 }; + inv_eltfp25519_1w_adx(other, a); + inv_eltfp25519_1w_bmi2(c, a); + assert(!memcmp(other, c, sizeof(other))); +} + +static inline void fred_EltFp25519_1w_x64(uint64_t *const c) +{ + fred_eltfp25519_1w(c); +} |