nettle-bugs

nettle-bugs@lists.lysator.liu.se

2198 discussions

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/… [View More]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. [View Less]

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 … [View More]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. [View Less]

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 … [View More]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. [View Less]

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 … [View More]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. [View Less]

3 6

[PATCH] silence more warnings
by Tim Ruehsen 21 Dec '12

21 Dec '12

some little fixes for nettle-hash.c:53:2: warning: ISO C does not allow extra ';' outside of a function [-pedantic] testutils.c:1072:2: warning: ISO C does not allow extra ';' outside of a function [-pedantic] des-compat-test.c:748:14: warning: old-style function definition [-Wold-style-definition] des-compat-test.c:755:17: warning: initialization discards 'const' qualifier from pointer target type [enabled by default] Regards, Tim diff --cc testsuite/des-compat-test.c index 257c343,257c343..… [View More]

2 1

building without fp
by Nikos Mavrogiannopoulos 16 Dec '12

16 Dec '12

I noticed that trying to build nettle in systems without floating point fails at the shadata, aesdata tools. The attached patch adds a flag (disable-data-targets) to prevent them from being built. regards, Nikos

2 1

Re: [PATCH] build: add --enable-static option
by nisse＠lysator.liu.se 15 Dec '12

15 Dec '12

Alon Bar-Lev <alon.barlev(a)gmail.com> writes: >> Maybe a make install without a previous make all should be supported? > > Usually yes. I just checked the GNU coding standards, and they seem to agree with you. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

1 0

Re: [PATCH] build: add --enable-static option
by nisse＠lysator.liu.se 15 Dec '12

15 Dec '12

Alon Bar-Lev <alon.barlev(a)gmail.com> writes: > Working, thanks! Thanks for testing. ---disable-static checked in now. > BTW: > There is an issue with: > $ ./configure > $ make install DESTDIR=/tmp/xxx Skipping make is not currently supported. I.e., you're supposed to do $ ./configure $ make $ make install or even better $ ./configure $ make $ make check && make install Maybe a make install without a previous make all should be supported? … [View More]

1 0

Some news for the next year
by nisse＠lysator.liu.se 15 Dec '12

15 Dec '12

The first item is a personal one. From January 7, I'll start working for Southpole Consulting AB, a small Sockholm-based consulting company mainly doing embedded (GNU/)Linux development. Second item is more directly related to Nettle. I will get funding from Internetfonden, for "Adapting GNU Nettle for embedded systems". This will mean two things: Support for elliptic curve signatures (and possibly some other ECC-related things), and optimizations for the ARM architecture. The funding is for … [View More]

3 5

Re: [PATCH] Probe for archiver tool
by nisse＠lysator.liu.se 15 Dec '12

15 Dec '12

Comitted now. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

1 0

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