nettle-bugs February 2013

nettle-bugs@lists.lysator.liu.se

4 participants
5 discussions

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

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 February 2013