nettle-bugs January 2013

nettle-bugs@lists.lysator.liu.se

4 participants
3 discussions

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

25 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

ANNOUNCE: Nettle-2.6
by nisse＠lysator.liu.se 16 Jan '13

16 Jan '13

I'm happy to annnounce a new version of GNU Nettle, a low-level cryptographics library. The Nettle home page can be found at http://www.lysator.liu.se/~nisse/nettle/. The release is signed using a new gpg key (2560R/28C67298). That key is also signed by the previous, 13 year old, release key (1024D/A8F4C2FD). NEWS for the 2.6 release Bug fixes: * Fixed a bug in ctr_crypt. For zero length (which should be a NOP), it sometimes incremented the counter. Reported by Tim Kosse. * Fixed a small memory leak in nettle_realloc and nettle_xrealloc. New features: * Support for PKCS #5 PBKDF2, to generate a key from a password or passphrase. Contributed by Simon Josefsson. Specification in RFC 2898 and test vectors in RFC 6070. * Support for SHA3. * Support for the GOST R 34.11-94 hash algorithm. Ported from librhash by Nikos Mavrogiannopoulos. Written by Aleksey Kravchenko. More information in RFC4357. Test vectors taken from the GOST hash wikipedia page. Miscellaneous: * The include file <nettle/sha.h> has been split into <nettle/sha1.h> and <nettle/sha2.h>. For now, sha.h is kept for backwards compatibility and it simply includes both files, but applications are encouraged to use the new names. The new SHA3 functions are declared in <nettle/sha3.h>. * Testsuite can be run under valgrind, using make check EMULATOR='$(VALGRIND)' For this to work, test programs and other executables now deallocate storage. * New configure options --disable-documentation and --disable-static. Contributed by Sam Thursfield and Alon Bar-Lev, respectively. * The section on hash functions in the manual is split into separate nodes for recommended hash functions and legacy hash functions. * Various smaller improvements, most of them portability fixes. Credits go to David Woodhouse, Tim Rühsen, Martin Storsjö, Nikos Mavrogiannopoulos, Fredrik Thulin and Dennis Clarke. Finally, a note on the naming of the various "SHA" hash functions. Naming is a bit inconsistent; we have, e.g., SHA1: sha1_digest SHA2: sha256_digest (not sha2_256_digest) SHA3: sha3_256_digest Renaming the SHA2 functions to make Nettle's naming more consistent has been considered, but the current naming follows common usage. Most documents (including the specification for SHA2) refer to 256-bit SHA2 as "SHA-256" or "SHA256" rather than "SHA2-256". The libraries are intended to be binary compatible with nettle-2.2 and later. The shared library names are libnettle.so.4.5 and libhogweed.so.2.3, with sonames still libnettle.so.4 and libhogweed.so.2 Available at http://ftp.gnu.org/gnu/nettle/nettle-2.6.tar.gz ftp://ftp.gnu.org/gnu/nettle/nettle-2.6.tar.gz http://www.lysator.liu.se/~nisse/archive/nettle-2.6.tar.gz and soon also at ftp://ftp.lysator.liu.se/pub/security/lsh/nettle-2.6.tar.gz Happy hacking, /Niels Möller -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

1 0

Getting closer to nettle-2.6
by nisse＠lysator.liu.se 04 Jan '13

04 Jan '13

I think I'd like to make a nettle-2.6 release fairly soon. Recent changes: 1. I disabled the x86_64 assembly for sha3_permute. It gave a very modest speedup on the Intel processor I benchmarked it on, and a sever slowdown on the AMD processor I also benchmarked it on. The latter machine seemed to execute the loop at only one instruction per cycle, rather than three as it should; my best guess is that it's the moves of data between regular registers and xmm registers that somehow stall. Maybe it could be rewritten to use xmm registers exclusively, but then register allocation gets *very* tight, so one might need to keep a few words of the state on the stack instead. But I don't think I'll try that soon; the current C implementation is reasonably efficient, with performance of sha256 and sha3-256 in the same ballbark (but both slower than sha512). 2. I think I fixed the bugs in some subdirectory make targets which broke "make install" without a preceding "make all". Ah, and a technical detail. There are no new features added to to libhogweed, but I still intend to increment the minor number of that shared library in the release. Is that right, or should I keep the same hogweed minor number as in nettle-2.5 (i.e., libhogweed.so.4.4)? I've updated the NEWS file (current version of the 2.6 entries appended below, for convenience). Are you aware of any missing pieces, either in the code, in NEWS, or in other documentation? Regards, /Niels NEWS for the 2.6 release Bug fixes: * Fixed a bug in ctr_crypt. For zero length (which should be a NOP), it sometimes incremented the counter. Reported by Tim Kosse. * Fixed a small memory leak in nettle_realloc and nettle_xrealloc. New features: * Support for PKCS #5 PBKDF2. Contributed by Simon Josefsson. Specification in RFC 2898 and test vectors in RFC 6070. * Support for GOST R 34.11-94 hash algorithm. Ported from librhash by Nikos Mavrogiannopoulos. Written by Aleksey Kravchenko. More information in RFC4357. Test vectors taken from the GOST hash wikipedia page. * Support for SHA3. Miscellaneous: * The include file <nettle/sha.h> has been split into <nettle/sha1.h> and <nettle/sha2.h>. For now, sha.h is kept for backwards compatibility and it simply includes both files, but applications are encouraged to use the new names. The new SHA3 functions are declared in <nettle/sha3.h>. * Testsuite can be run under valgrind, using make check EMULATOR='$(VALGRIND)' For this to work, test programs and other executables now deallocate storage. * New configure options --disable-documentation and --disable-static. Contributed by Sam Thursfield and Alon Bar-Lev, respectively. * The section on hash functions in the manual is split into separate nodes for recommended hash functions and legacy hash functions. * Various smaller improvements, most of them portability fixes. Credits go to David Woodhouse, Tim Rühsen, Martin Storsjö, Nikos Mavrogiannopoulos, Fredrik Thulin and Dennis Clarke. Finally, a note on the naming of the various "SHA" hash functions. Naming is a bit inconsistent; we have, e.g., SHA1: sha1_digest SHA2: sha256_digest (not sha2_256_digest) SHA3: sha3_256_digest Renaming the SHA2 functions to make Nettle's naming more consistent has been considered, but the current naming follows common usage. Most documents (including the specification for SHA2) refer to 256-bit SHA2 as "SHA-256" or "SHA256" rather than "SHA2-256". The libraries are intended to be binary compatible with nettle-2.2 and later. The shared library names are libnettle.so.4.5 and libhogweed.so.2.3, with sonames still libnettle.so.4 and libhogweed.so.2 -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

3 6

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