nettle-bugs

nettle-bugs@lists.lysator.liu.se

2196 discussions

[PATCH] Factorize timing functions to a separate file
by Martin Storsjö 25 Mar '13

25 Mar '13

This avoids unconditionally using clock_gettime in {ecc,hogweed}-benchmark, falling back to clock() in these as well. This makes building succeed on e.g. OS X. --- examples/Makefile.in | 16 +++--- examples/ecc-benchmark.c | 26 ++-------- examples/hogweed-benchmark.c | 26 ++-------- examples/nettle-benchmark.c | 69 ++------------------------ examples/timing.c | 110 ++++++++++++++++++++++++++++++++++++++++++ examples/timing.h | 30 ++++++++++++ 6 files changed, 162 insertions(+), 115 deletions(-) create mode 100644 examples/timing.c create mode 100644 examples/timing.h diff --git a/examples/Makefile.in b/examples/Makefile.in index 3455a58..563d0dc 100644 --- a/examples/Makefile.in +++ b/examples/Makefile.in @@ -28,7 +28,7 @@ SOURCES = nettle-benchmark.c hogweed-benchmark.c ecc-benchmark.c \ nettle-openssl.c \ io.c read_rsa_key.c \ rsa-encrypt.c rsa-decrypt.c rsa-keygen.c rsa-sign.c rsa-verify.c \ - base16enc.c base16dec.c base64enc.c base64dec.c + base16enc.c base16dec.c base64enc.c base64dec.c timing.c GETOPT_OBJS = ../getopt.$(OBJEXT) ../getopt1.$(OBJEXT) @@ -36,7 +36,7 @@ GETOPT_OBJS = ../getopt.$(OBJEXT) ../getopt1.$(OBJEXT) TS_ALL = rsa-sign-test rsa-verify-test rsa-encrypt-test DISTFILES= $(SOURCES) Makefile.in $(TS_ALL) setup-env teardown-env \ - io.h rsa-session.h + io.h rsa-session.h timing.h all: $(TARGETS) @@ -102,16 +102,18 @@ eratosthenes$(EXEEXT): eratosthenes.$(OBJEXT) $(GETOPT_OBJS) $(LINK) eratosthenes.$(OBJEXT) $(GETOPT_OBJS) -o eratosthenes$(EXEEXT) BENCH_OBJS = nettle-benchmark.$(OBJEXT) nettle-openssl.$(OBJEXT) \ - $(GETOPT_OBJS) ../nettle-internal.$(OBJEXT) + $(GETOPT_OBJS) ../nettle-internal.$(OBJEXT) timing.$(OBJEXT) nettle-benchmark$(EXEEXT): $(BENCH_OBJS) $(LINK) $(BENCH_OBJS) -lnettle $(BENCH_LIBS) $(OPENSSL_LIBFLAGS) -o nettle-benchmark$(EXEEXT) -ecc-benchmark$(EXEEXT): ecc-benchmark.$(OBJEXT) - $(LINK) ecc-benchmark.$(OBJEXT) -lhogweed -lnettle $(BENCH_LIBS) $(LIBS) \ +ECC_BENCH_OBJS = ecc-benchmark.$(OBJEXT) timing.$(OBJEXT) +ecc-benchmark$(EXEEXT): $(ECC_BENCH_OBJS) + $(LINK) $(ECC_BENCH_OBJS) -lhogweed -lnettle $(BENCH_LIBS) $(LIBS) \ -o ecc-benchmark$(EXEEXT) -hogweed-benchmark$(EXEEXT): hogweed-benchmark.$(OBJEXT) - $(LINK) hogweed-benchmark.$(OBJEXT) \ +HOGWEED_BENCH_OBJS = hogweed-benchmark.$(OBJEXT) timing.$(OBJEXT) +hogweed-benchmark$(EXEEXT): $(HOGWEED_BENCH_OBJS) + $(LINK) $(HOGWEED_BENCH_OBJS) \ -lhogweed -lnettle $(BENCH_LIBS) $(LIBS) $(OPENSSL_LIBFLAGS) \ -o hogweed-benchmark$(EXEEXT) diff --git a/examples/ecc-benchmark.c b/examples/ecc-benchmark.c index 596b2ff..e14e55e 100644 --- a/examples/ecc-benchmark.c +++ b/examples/ecc-benchmark.c @@ -35,6 +35,8 @@ #include <time.h> +#include "timing.h" + #include "../ecc.h" #include "../ecc-internal.h" #include "../gmp-glue.h" @@ -70,24 +72,6 @@ xalloc_limbs (mp_size_t size) return xalloc (size * sizeof(mp_limb_t)); } -inline static void -time_start(struct timespec *start) -{ - if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, start) < 0) - die("clock_gettime failed: %s\n", strerror(errno)); -} - -static inline double -time_end(struct timespec *start) -{ - struct timespec end; - if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end) < 0) - die("clock_gettime failed: %s\n", strerror(errno)); - - return end.tv_sec - start->tv_sec - + 1e-9 * (end.tv_nsec - start->tv_nsec); -} - /* Returns second per function call */ static double time_function(void (*f)(void *arg), void *arg) @@ -100,12 +84,11 @@ time_function(void (*f)(void *arg), void *arg) for (ncalls = 10 ;;) { unsigned i; - struct timespec t; - time_start(&t); + time_start(); for (i = 0; i < ncalls; i++) f(arg); - elapsed = time_end(&t); + elapsed = time_end(); if (elapsed > BENCH_INTERVAL) break; else if (elapsed < BENCH_INTERVAL / 10) @@ -293,6 +276,7 @@ main (int argc UNUSED, char **argv UNUSED) { unsigned i; + time_init(); printf ("%4s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s (us)\n", "size", "modp", "redc", "modq", "modinv", "mi_gcd", "dup_jj", "ad_jja", "ad_jjj", diff --git a/examples/hogweed-benchmark.c b/examples/hogweed-benchmark.c index f6ceda9..56860e0 100644 --- a/examples/hogweed-benchmark.c +++ b/examples/hogweed-benchmark.c @@ -34,6 +34,8 @@ #include <time.h> +#include "timing.h" + #include "dsa.h" #include "rsa.h" @@ -90,24 +92,6 @@ hash_string (const struct nettle_hash *hash, return digest; } -inline static void -time_start(struct timespec *start) -{ - if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, start) < 0) - die("clock_gettime failed: %s\n", strerror(errno)); -} - -static inline double -time_end(struct timespec *start) -{ - struct timespec end; - if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end) < 0) - die("clock_gettime failed: %s\n", strerror(errno)); - - return end.tv_sec - start->tv_sec - + 1e-9 * (end.tv_nsec - start->tv_nsec); -} - struct alg { const char *name; unsigned size; @@ -129,12 +113,11 @@ time_function(void (*f)(void *arg), void *arg) for (ncalls = 10 ;;) { unsigned i; - struct timespec t; - time_start(&t); + time_start(); for (i = 0; i < ncalls; i++) f(arg); - elapsed = time_end(&t); + elapsed = time_end(); if (elapsed > BENCH_INTERVAL) break; else if (elapsed < BENCH_INTERVAL / 10) @@ -625,6 +608,7 @@ main (int argc, char **argv) if (argc > 1) filter = argv[1]; + time_init(); printf ("%15s %4s %9s %9s\n", "name", "size", "sign/ms", "verify/ms"); diff --git a/examples/nettle-benchmark.c b/examples/nettle-benchmark.c index 90d6c72..852baef 100644 --- a/examples/nettle-benchmark.c +++ b/examples/nettle-benchmark.c @@ -38,6 +38,8 @@ #include <time.h> +#include "timing.h" + #include "aes.h" #include "arcfour.h" #include "blowfish.h" @@ -112,58 +114,6 @@ die(const char *format, ...) static double overhead = 0.0; -#if HAVE_CLOCK_GETTIME && defined CLOCK_PROCESS_CPUTIME_ID -#define TRY_CLOCK_GETTIME 1 -struct timespec cgt_start; - -static int -cgt_works_p(void) -{ - struct timespec now; - return clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &now) == 0; -} - -static void -cgt_time_start(void) -{ - if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &cgt_start) < 0) - die("clock_gettime failed: %s\n", strerror(errno)); -} - -static double -cgt_time_end(void) -{ - struct timespec end; - if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end) < 0) - die("clock_gettime failed: %s\n", strerror(errno)); - - return end.tv_sec - cgt_start.tv_sec - + 1e-9 * (end.tv_nsec - cgt_start.tv_nsec); -} - -static void (*time_start)(void); -static double (*time_end)(void); - -#else /* !HAVE_CLOCK_GETTIME */ -#define TRY_CLOCK_GETTIME 0 -#define time_start clock_time_start -#define time_end clock_time_end -#endif /* !HAVE_CLOCK_GETTIME */ - -static clock_t clock_start; - -static void -clock_time_start(void) -{ - clock_start = clock(); -} - -static double -clock_time_end(void) -{ - return (double) (clock() - (clock_start)) / CLOCKS_PER_SEC; -} - /* Returns second per function call */ static double time_function(void (*f)(void *arg), void *arg) @@ -700,20 +650,7 @@ main(int argc, char **argv) alg = argv[optind]; - /* Choose timing function */ -#if TRY_CLOCK_GETTIME - if (cgt_works_p()) - { - time_start = cgt_time_start; - time_end = cgt_time_end; - } - else - { - fprintf(stderr, "clock_gettime not working, falling back to clock\n"); - time_start = clock_time_start; - time_end = clock_time_end; - } -#endif + time_init(); bench_sha1_compress(); bench_salsa20_core(); bench_sha3_permute(); diff --git a/examples/timing.c b/examples/timing.c new file mode 100644 index 0000000..108399a --- /dev/null +++ b/examples/timing.c @@ -0,0 +1,110 @@ +/* timing.c */ + +/* nettle, low-level cryptographics library + * + * Copyright (C) 2013 Niels Möller + * + * The nettle library 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; either version 2.1 of the License, or (at your + * option) any later version. + * + * The nettle library 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 the nettle library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, + * MA 02111-1301, USA. + */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "timing.h" + +#include <errno.h> +#include <stdarg.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#if HAVE_CLOCK_GETTIME && defined CLOCK_PROCESS_CPUTIME_ID +#define TRY_CLOCK_GETTIME 1 +struct timespec cgt_start; + +static void NORETURN PRINTF_STYLE(1,2) +die(const char *format, ...) +{ + va_list args; + va_start(args, format); + vfprintf(stderr, format, args); + va_end(args); + + exit(EXIT_FAILURE); +} + +static int +cgt_works_p(void) +{ + struct timespec now; + return clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &now) == 0; +} + +static void +cgt_time_start(void) +{ + if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &cgt_start) < 0) + die("clock_gettime failed: %s\n", strerror(errno)); +} + +static double +cgt_time_end(void) +{ + struct timespec end; + if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end) < 0) + die("clock_gettime failed: %s\n", strerror(errno)); + + return end.tv_sec - cgt_start.tv_sec + + 1e-9 * (end.tv_nsec - cgt_start.tv_nsec); +} +#endif /* !HAVE_CLOCK_GETTIME */ + +static clock_t clock_start; + +static void +clock_time_start(void) +{ + clock_start = clock(); +} + +static double +clock_time_end(void) +{ + return (double) (clock() - (clock_start)) / CLOCKS_PER_SEC; +} + +void (*time_start)(void) = clock_time_start; +double (*time_end)(void) = clock_time_end; + +void time_init(void) +{ + /* Choose timing function */ +#if TRY_CLOCK_GETTIME + if (cgt_works_p()) + { + time_start = cgt_time_start; + time_end = cgt_time_end; + } + else + { + fprintf(stderr, "clock_gettime not working, falling back to clock\n"); + time_start = clock_time_start; + time_end = clock_time_end; + } +#endif +} diff --git a/examples/timing.h b/examples/timing.h new file mode 100644 index 0000000..7307fa1 --- /dev/null +++ b/examples/timing.h @@ -0,0 +1,30 @@ +/* timing.c */ + +/* nettle, low-level cryptographics library + * + * Copyright (C) 2013 Niels Möller + * + * The nettle library 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; either version 2.1 of the License, or (at your + * option) any later version. + * + * The nettle library 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 the nettle library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, + * MA 02111-1301, USA. + */ + +#ifndef NETTLE_EXAMPLES_TIMING_H_INCLUDED +#define NETTLE_EXAMPLES_TIMING_H_INCLUDED + +void time_init(void); +extern void (*time_start)(void); +extern double (*time_end)(void); + +#endif /* NETTLE_EXAMPLES_TIMING_H_INCLUDED */ -- 1.7.9.4

2 1

[PATCH] Add a fallback definition for mpn_sqr
by Martin Storsjö 25 Mar '13

25 Mar '13

--- gmp-glue.h | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/gmp-glue.h b/gmp-glue.h index 0cde62f..d154a50 100644 --- a/gmp-glue.h +++ b/gmp-glue.h @@ -58,6 +58,10 @@ typedef unsigned long int mp_bitcnt_t; #define mpn_zero _nettle_mpn_zero #endif +#ifndef mpn_sqr +#define mpn_sqr(rp, ap, n) mpn_mul_n((rp), (ap), (ap), (n)) +#endif + #define mpz_limbs_cmp _nettle_mpz_limbs_cmp #define mpz_limbs_read_n _nettle_mpz_limbs_read_n #define mpz_limbs_copy _nettle_mpz_limbs_copy -- 1.7.9.4

1 0

[PATCH] Use local paths for including headers in examples and tests
by Martin Storsjö 23 Mar '13

23 Mar '13

This makes sure a plain "make" succeeds without doing "make install". --- examples/hogweed-benchmark.c | 10 +++++----- testsuite/ecdsa-keygen-test.c | 2 +- 2 files changed, 6 insertions(+), 6 deletions(-) diff --git a/examples/hogweed-benchmark.c b/examples/hogweed-benchmark.c index 803f056..b1a0e89 100644 --- a/examples/hogweed-benchmark.c +++ b/examples/hogweed-benchmark.c @@ -34,12 +34,12 @@ #include <time.h> -#include <nettle/dsa.h> -#include <nettle/rsa.h> +#include "dsa.h" +#include "rsa.h" -#include <nettle/nettle-meta.h> -#include <nettle/sexp.h> -#include <nettle/knuth-lfib.h> +#include "nettle-meta.h" +#include "sexp.h" +#include "knuth-lfib.h" #include "../ecdsa.h" #include "../ecc-internal.h" diff --git a/testsuite/ecdsa-keygen-test.c b/testsuite/ecdsa-keygen-test.c index 4f46d0d..7c25421 100644 --- a/testsuite/ecdsa-keygen-test.c +++ b/testsuite/ecdsa-keygen-test.c @@ -1,5 +1,5 @@ #include "testutils.h" -#include <nettle/knuth-lfib.h> +#include "knuth-lfib.h" /* Check if y^2 = x^3 - 3x + b */ static int -- 1.7.9.4

1 0

ARM assembly
by nisse＠lysator.liu.se 16 Mar '13

16 Mar '13

I've new written some ARM assembly files for AES, SHA1 and SHA256. I haven't tried any clever scheduling (it seems quite unpredictable), so I think I win over the C code is mainly because I fit the important values in registers. I have benchmarked on a cortex-a9 system, with nice but not earth-shattering improvements over the C implementation. In my benchmarks, AES decrypt is significantly slower than AES decrypt, for no reason that I understand, and I have tried some other variants of instruction scheduling. I have one question on the ABI, if there's anyone on the list with more ARM experience: In the ABI spec, register r9 is reserved for use for things such as thread local storage. I'm almost sure that a leaf function can use r9 like any other callee-save register, but I'd like to have that confirmed before I make use of it. Potential problem case is if the function is interrupted by a signal and signal handler somehow depends on having a valid value in r9, or if context switching somehow assumes that r9 is never modified. Any suggestion for what to try optimizing next? I imagine all algorithms that make use of 64-bit data or are designed for simd operations could be sped up a bit using the neon simd instructions (which I so far haven't made any use of). This includes sha512, sha3, serpent, salsa, maybe camellia. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

3 3

ECC integration
by nisse＠lysator.liu.se 18 Feb '13

18 Feb '13

I'm working on integration of the new ECC code into nettle, on a separate branch, see http://git.lysator.liu.se/nettle/nettle/commits/ecc-support I've probably broken cross-compilation support, but otherwise it should be working. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

1 0

ECC low-level interface
by nisse＠lysator.liu.se 18 Feb '13

18 Feb '13

I'd like to post the interface I use for low-level ecc functions. All functions are intended to be side-channel silent. I have tried to stick to the nettle principle of "no allocation" (I mostly call low-level gmp functions which don't allocate storage). Functions which need scratch space gets this space from the caller, as an extra argument. And for the function foo, there's a corresponding function foo_itch, saying how much working storage is needed. Sizes are in units of mp_limb_t. Of these low-level functions, the highest level ones are ecc_mul_g and ecc_mul_a. Feedback is appreciated. The rest of the code is available at http://git.lysator.liu.se/nettle/se-nettle-2013 Regards, /Niels /* ecc.h */ /* nettle, low-level cryptographics library * * Copyright (C) 2013 Niels MÃ¶ller * * The nettle library 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; either version 2.1 of the License, or (at your * option) any later version. * * The nettle library 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 the nettle library; see the file COPYING.LIB. If not, write to * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, * MA 02111-1301, USA. */ /* Development of Nettle's ECC support was funded by Internetfonden. */ #ifndef NETTLE_ECC_H_INCLUDED #define NETTLE_ECC_H_INCLUDED #include <stdint.h> #include <gmp.h> /* The contets of this struct is internal. */ struct ecc_curve; extern const struct ecc_curve ecc_secp_192r1; extern const struct ecc_curve ecc_secp_224r1; extern const struct ecc_curve ecc_secp_256r1; extern const struct ecc_curve ecc_secp_384r1; extern const struct ecc_curve ecc_secp_521r1; /* Points on a curve are represented as arrays of mp_limb_t. For some curves, point coordinates are represented in montgomery form. We use either affine coordinates x,y, or Jacobian coordinates X, Y, Z, where x = X/Z^2 and y = X/Z^2. Since we use additive notation for the groups, the infinity point on the curve is denoted 0. The infinity point can be represented with x = y = 0 in affine coordinates, and Z = 0 in Jacobian coordinates. However, note that most of the ECC functions do *not* support infinity as an input or output. */ /* FIXME: Also provided some compile time constants? */ /* Returns the size of a single coordinate. */ mp_size_t ecc_size (const struct ecc_curve *ecc); /* Size of a point, using affine coordinates x, y. */ mp_size_t ecc_size_a (const struct ecc_curve *ecc); /* Size of a point, using jacobian coordinates X, Y and Z. */ mp_size_t ecc_size_j (const struct ecc_curve *ecc); /* FIXME: Rename the low-level (and side-channel silent) functions to _ecc_*, and provide public ecc_* functions which handle the infinity points properly? */ /* Converts the affine coordinates of a point into montgomery form, if used for this curve. */ mp_size_t ecc_a_to_a_itch (const struct ecc_curve *ecc); void ecc_a_to_a (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, mp_limb_t *scratch); /* Converts a point P in affine coordinates into a point R in jacobian coordinates. If INITIAL is non-zero, and the curve uses montgomery coordinates, also convert coordinates to montgomery form. */ void ecc_a_to_j (const struct ecc_curve *ecc, int initial, mp_limb_t *r, const mp_limb_t *p); /* Converts a point P in jacobian coordinates into a point R in affine coordinates. If FLAGS has bit 0 set, and the curve uses montgomery coordinates, also undo the montgomery conversion. If flags has bit 1 set, produce x coordinate only. */ mp_size_t ecc_j_to_a_itch (const struct ecc_curve *ecc); void ecc_j_to_a (const struct ecc_curve *ecc, int flags, mp_limb_t *r, const mp_limb_t *p, mp_limb_t *scratch); /* Group operations */ /* Point doubling, with jacobian output and affine input. Corner cases: Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */ mp_size_t ecc_dup_ja_itch (const struct ecc_curve *ecc); void ecc_dup_ja (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, mp_limb_t *scratch); /* Point doubling, with jacobian input and output. Corner cases: Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */ mp_size_t ecc_dup_jj_itch (const struct ecc_curve *ecc); void ecc_dup_jj (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, mp_limb_t *scratch); /* Point addition, with jacobian output, one jacobian input and one affine input. Corner cases: Fails for the cases P = Q != 0 Duplication of non-zero point P = 0, Q != 0 or P != 0, Q = 0 One input zero Correctly gives R = 0 if P = Q = 0 or P = -Q. */ mp_size_t ecc_add_jja_itch (const struct ecc_curve *ecc); void ecc_add_jja (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, mp_limb_t *scratch); /* Point addition with Jacobian input and output. */ mp_size_t ecc_add_jjj_itch (const struct ecc_curve *ecc); void ecc_add_jjj (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, mp_limb_t *scratch); /* Computes N * the group generator. N is an array of ecc_size() limbs. It must be in the range 0 < N < group order, then R != 0, and the algorithm can work without any intermediate values getting to zero. */ mp_size_t ecc_mul_g_itch (const struct ecc_curve *ecc); void ecc_mul_g (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *np, mp_limb_t *scratch); /* Computes N * P. The scalar N is the same as for ecc_mul_g. P is a non-zero point on the curve, in affine coordinates. Pass a non-zero INITIAL if the point coordinates have not previously been converted to Montgomery representation. Output R is a non-zero point, in Jacobian coordinates. */ mp_size_t ecc_mul_a_itch (const struct ecc_curve *ecc); void ecc_mul_a (const struct ecc_curve *ecc, int initial, mp_limb_t *r, const mp_limb_t *np, const mp_limb_t *p, mp_limb_t *scratch); #endif /* NETTLE_ECC_H_INCLUDED */ -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

2 11

ECC benchmarks
by nisse＠lysator.liu.se 17 Feb '13

17 Feb '13

It's some time since I posted benchmark figures. The speed dropped a bit when I started to use the slow side-channel silent modinv, but I think it's reasonable. For comparison, I just added openssl's ecdsa functions to my benchmark program. These are the current figures for x86_64: size modp redc modq add_jja dup_jj (us) 192 0.0248 0.0265 0.0450 0.6319 0.5151 224 0.0519 0.0467 0.0680 0.9136 0.7149 256 0.0834 0.0409 0.0802 0.8222 0.6617 384 0.0927 0.0000 0.0607 1.6663 1.2559 521 0.0347 0.0514 0.1289 1.5239 1.1670 name size sign / ms verify / ms rsa 1024 6.3180 102.7909 rsa 2048 0.9562 29.2339 dsa 1024 11.1780 5.7492 ecdsa 192 14.9983 4.5612 ecdsa 224 8.0952 2.6880 ecdsa 256 7.7640 2.5785 ecdsa 384 2.9131 0.9155 ecdsa 521 1.7974 0.6594 ecdsa (openssl) 224 3.4939 3.0582 ecdsa (openssl) 384 1.4637 1.2603 ecdsa (openssl) 521 0.6962 0.5981 If we extract common functions for openssl (it seemed to lack secp192r1 and secp256r1), we get ecdsa 224 8.0952 2.6880 ecdsa (openssl) 224 3.4939 3.0582 ecdsa 384 2.9131 0.9155 ecdsa (openssl) 384 1.4637 1.2603 ecdsa 521 1.7974 0.6594 ecdsa (openssl) 521 0.6962 0.5981 So it looks like for signing, the current code beats openssl by a factor of two. While for verify, we're a little behind. And my code tries hard to be side-channel silent (even for verify, where it doesn't matter). I'm not sure if openssl tries to be side-channel silent. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

3 8

ARM support
by nisse＠lysator.liu.se 06 Feb '13

06 Feb '13

I've now pushed in some configure tweaks to support arm (more specifically, configure recognizes armv7l*. As a warmup, I implemented memxor in arm assembly. Seems to work, and it's a modest performance improvement over the C code (in the aligned case, both memxor and memxor3 do 0.75 cycles per byte when I benchmark on Cortex-A9). Could surely be further improved. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

1 0

ECC status update for January
by nisse＠lysator.liu.se 04 Feb '13

04 Feb '13

Here's a copy of the status update for January which I just submitted to Internetfonden. Regards, /Niels Nettle project funded by Internetfonden Status update for January 2013 * Summary Project has started. ARM-based test system is up and running. A first implementation of elliptic curve-based signatures is done. * Activities Work on the project was initiated January 9, installing the test hardware: A Pandaboard, based on a dual core Arm Cortex-A9 processor, now running Debian GNU/Linux. I used the instructions on http://www.eewiki.net/display/linuxonarm/PandaBoard for the installation, but after cross compiling kernel etc, I can now use native compiler and debugger for development. I have confirmed that current versions of GNU Nettle and GNU GMP work fine on this hardware. I have been reading ARM manuals (but not yet done any ARM assembly coding), and reading up on relevant methods for elliptic curve operations. For the elliptic curves, I have decided to aim for "side-channel silent" algorithms. This means that for each curve, instructions executed and memory access pattern must not depend on the input data. This is to avoid leaking information about secret keys to an attacker monitoring the timing of operations, as well as to an attacker running an untrusted process which can manipulate and observe cache misses. Most of January have been spent on implementing the elliptic curve machinery needed for creating and verifying ECDSA signatures, over the standard curves secp192r1, secp224r1, secp256r1, secp384r1 and secp521r1. The work-in-progress code as, well as various working notes, is published as a public git repository, see http://git.lysator.liu.se/nettle/se-nettle-2013. During the month, roughly 130 working hours have been spent on the project. * About elliptic curves Elliptic curve operations are based on Jacobi coordinates (http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html). Multiplication involving the group generator use a special case of Pippenger's algorithm (described in Daniel J. Bernstein's draft paper http://cr.yp.to/papers.html#pippenger). This algorithm has later been rediscovered and is covered by a couple of, most likely invalid, patents (also explained by Daniel J. Bernstein). With current parameter choices, we use precomputed tables of modest size, roughly 16 KByte for each supported curve, which are compiled into the library. I have not yet decided on the algorithm to use for multiplication involving an arbitrary point. The current implementation uses a side-channel silent variant of the most basic binary multiplication; it can be improved by using window-based algorithm, similar to what GMP uses for the function mpz_powm_sec. The implementation includes a testsuite, and it is tested both on x86_64 (a 64-bit PC platform) and on the Pandaboard (32-bit ARM platform). It is also benchmarked on both those platforms. To give some quantitative numbers, I compare performance to 2048-bit RSA, and measure number of signing and verifications operations that can be done per ms. Intel i5, 3.4 GHz: name size sign / ms verify / ms rsa 1024 6.3228 102.9886 rsa 2048 0.9559 29.5987 dsa 1024 11.1867 5.7500 ecdsa 192 17.9380 3.7946 ecdsa 224 10.0423 2.0285 ecdsa 256 9.3953 2.2191 ecdsa 384 3.5025 0.7830 ecdsa 521 2.1572 0.5291 ARM Cortex A9, 1 GHz: name size sign / ms verify / ms rsa 1024 0.2627 4.5487 rsa 2048 0.0392 1.2488 dsa 1024 0.4691 0.2377 ecdsa 192 1.2888 0.2883 ecdsa 224 0.7856 0.1790 ecdsa 256 0.5900 0.1280 ecdsa 384 0.2423 0.0545 ecdsa 521 0.1327 0.0296 When looking at the verify operations, ECDSA is not competitive to RSA, and maybe never will. RSA has the advantage of using a small public exponent; in these benchmarks, I use e = 65537. For signing operations, let us focus on ECDSA 224, which is believed to give slightly higher security than RSA 2048 (see http://www.keylength.com/en/3/). Then ECDSA signatures, with the current code, is a factor 10 faster on ARM, and a factor 20 faster on x86_64. When comparing the benchmark numbers, one should keep in mind that performance is not everything. In some applications, the smaller size of keys and signatures for ECDSA is also of high importance. * Remaining tasks For elliptic curve signatures, one large remaining task is designing, implementing, and documenting the public programming interface. This is part of the integration work required, before the elliptic curve implementation can be incorporated in the Nettle library. For optimizations, performance of the verify operations can be improved by algorithmic improvements. Performance of all operations can be further improved by platform-specific optimizations, implementing a few key functions in assembly. It's also possible to write alternative elliptic curve primitives, without the requirement of side-channel silence. These could be used to speed up operations which don't have any secret inputs, in particular, verification of signatures. I give that a lower priority than the other potential optimizations, though. For the other sub-project, to do ARM-specific optimizations for cryptographic primitives unrelated to elliptic curves, no work has been done during January, beyond a general study of the ARM architecture. Most important functions are the AES block cipher and the hash functions in the SHA family: SHA1, SHA256, SHA512, and possibly also the recently standardized SHA3 hash function. Also the memxor function is a candidate to be the first ARM-assembly function in Nettle. -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

1 0

ECC plans
by nisse＠lysator.liu.se 26 Jan '13

26 Jan '13

I've started to read up on ECC again (and I've also spent some time reading up on ARM architecture, but that's for a different message). As I wrote earlier, for a start I'll limit the support to standard NIST curves. So first question is naming; what's the most established names for these curves? It seems gnutls uses, e.g., "SECP256R1", I guess we can just follow that (rather than, e.g, "P-256", as it's called in the DSA spec fips-186-3)? My current plan is as follows: 1. The top-level functions for ECDSA and the like will use mpz_t to represent point coordinates, exponents, etc, just like the current DSA code. 2. Internally, I think I want to use GMP's lower-level mpn interface, for two reasons: (i) that should make it possible, with some effort, to use ecc functions without any allocation inside Nettle. (ii) For performance, I'd like to do specific mod p functions for the various curves, and this is done best on top of functions such as mpn_add_n and mpn_addmul_1. After all, the primes p used for the curves are carefully chosen to have special structure, to enable optimizations. 3. Representation of a curve will for now be an opaque struct. The header will just declare struct ecc_curve; extern const struct ecc_curve nettle secp256r1; Tables for point multiplication will be compiled into the library. They will be somewhat machine dependent, depending on the GMP limb size, so they have to be generated at build time. 4. I think I'll use Jacobian coordinates. These have a penalty for addition of arbitrary points, but we can try to use multiplication algorithms where one of the points being added always is a constant, which can be represented in normalized form. Then there's no penalty over plain homogeneous coordinates (this is the operation called "madd" in gnutls sources). I've been intrigued by the recent (2007) breakthrough of Edwards curves, but as far as I understand, that can't easily be applied to the standard NIST curves. See http://cr.yp.to/newelliptic/newelliptic.html. 5. For point multiplication with the fixed generator, I think I'll use the L=1 special case of Pippenger's algorithm, described in Daniel Bernstein's paper http://cr.yp.to/papers/pippenger.pdf. I think this is more or less the same as the "comb" method or "Lim-Lee"-method, but predating any bogus patents on the algorithm. (I can try to summarize the algorithm later, but it's pretty simple once one gets past the notation). I think it's fairly easy to silence with regards to timing and cache side-channels. One nice feature is that even with pretty large tables, not all of the table index bits are data-dependent (extracted from the exponent). Then it should be practical to read all possible table entries and use masking to copy the selected one, see http://gmplib.org:8000/gmp/file/eee6b8e54765/mpn/generic/tabselect.c. This operation is the working horse for ECDSA signing, and for the first half of ECDH. I'm not sure how large tables it makes sense to create for each curve, but I guess somewehere between a few KByte to at most 100 Kbyte. This could be made configurable at compile time, but I'd expect almost all users to stick to the default tables. 6. For general point multiplication, I tend towards using a simple non-sliding window, with a small point-specific table computed at run time. If the table is small enough, it might make sense to normalize the entries. As far as I understand, one can't beat the plain binary algorithm by a large factor; the algorithms I'm aware of only reduce the number of adds, but not the number of dups. This operation is the working horse for the second half of ECDH. 7. For verifying ECDSA signatures, one needs to operate on two points, computing e_1 G + e_2 Y, where G is the generator (and hence offers possibilities for precomputation), and Y is the public key. I haven't yet looked into this in detail, but it seems clear this should be done as a single operation, with only one chain of point duplications. Preferably, it should be implemented in such a way that the tables for G (from 5 above) can be reused. Comments? Does this make sense, or is it anything which ought to be done differently? I have had a quick look at the gnutls code. wmNAF makes me a bit uneasy when I think about side channels; there seems to be a lot of branches depending on exponent bits. In the point addition, it seems hard to avoid special cases when adding a point to itself or to its negation, or adding the zero point. Which will cause sidechannel leaks. Not sure what to do about that, but there are some papers on "unified" ecc operations, or maybe one can do something analogous to rsa blinding. As far as I understand, for point multiplication in both ECDSA and ECDH, it's only the scalar that ever is secret, the points multiplied are always public. Are there other uses of point multiplication where also the point is secret? Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

4 13

Jump to page:

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

nettle-bugs