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 */
nisse@lysator.liu.se (Niels Möller) writes:
I'd like to post the interface I use for low-level ecc functions.
And here's the current interface for ECDSA functions. Low-level functions with similar conventions as the low-level ecc functions. And high-level functions using mpz_t for arguments, and using the same allocation function as GMP for storage.
For the RSA signature functions, we have a larger number of functions of the form rsa_<hash-algorithm>_sign, mostly because the pkcs#1 padding wants to embed the hash algorithm object identifier.
But for ecdsa, do we need any functions like that? I guess, for convenience and consistency, it would make sense with some functions like
void ecdsa_sha256_sign (const struct ecdsa_private_key *key, void *random_ctx, nettle_random_func *random, struct sha256_ctx *hash, struct dsa_signature *signature);
which take a hashing context as argument. Which hash functions are people using for ecdsa with the various curves? RFC 4754 (IKE and IKEv2 Authentication Using ECDSA) defines:
Digital Signature Algorithm Elliptic Curve Group Hash Function ----------- -------------------------- --------------- ECDSA-256 256-bit random ECP group SHA-256 ECDSA-384 384-bit random ECP group SHA-384 ECDSA-521 521-bit random ECP group SHA-512
Is this typical? (Then it's the first time I've seen a specification using). I implement also secp192r1 and secp224r1, which I guess would be used with sha256 (or possibly sha224).
Regards, /Niels
/* ecdsa.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_ECDSA_H_INCLUDED #define NETTLE_ECDSA_H_INCLUDED
#include <nettle/dsa.h>
#include "ecc.h"
/* High-level ECDSA interface. Uses mpz interface, and allocates storage using the same allocation functions as GMP. */ struct ecdsa_public_key { const struct ecc_curve *ecc; /* Allocated using the same allocation function as GMP. */ mp_limb_t *Y; };
struct ecdsa_private_key { const struct ecc_curve *ecc; /* Size ecc->size. */ mp_limb_t *z; };
void ecdsa_public_key_init (struct ecdsa_public_key *pub, const struct ecc_curve *ecc); void ecdsa_public_key_clear (struct ecdsa_public_key *pub);
int ecdsa_set_public_key (struct ecdsa_public_key *pub, const mpz_t x, const mpz_t y); void ecdsa_get_public_key (struct ecdsa_public_key *pub, mpz_t x, mpz_t y);
void ecdsa_private_key_init (struct ecdsa_private_key *key, const struct ecc_curve *ecc); void ecdsa_private_key_clear (struct ecdsa_private_key *key);
int ecdsa_set_private_key (struct ecdsa_private_key *key, const mpz_t z); void ecdsa_get_private_key (struct ecdsa_private_key *key, mpz_t z);
void ecdsa_sign (const struct ecdsa_private_key *key, void *random_ctx, nettle_random_func *random, unsigned digest_length, const uint8_t *digest, struct dsa_signature *signature);
int ecdsa_verify (const struct ecdsa_public_key *pub, unsigned length, const uint8_t *digest, const struct dsa_signature *signature);
void ecdsa_generate_keypair (struct ecdsa_public_key *pub, struct ecdsa_private_key *key, void *random_ctx, nettle_random_func *random);
/* Low-level ECDSA interface. */
mp_size_t _ecdsa_sign_itch (const struct ecc_curve *ecc); void _ecdsa_sign (const struct ecc_curve *ecc, /* Private key */ const mp_limb_t *zp, /* Random nonce, must be invertible mod ecc group order. */ const mp_limb_t *kp, unsigned length, const uint8_t *digest, mp_limb_t *rp, mp_limb_t *sp, mp_limb_t *scratch);
mp_size_t _ecdsa_verify_itch (const struct ecc_curve *ecc); int _ecdsa_verify (const struct ecc_curve *ecc, const mp_limb_t *pp, /* Public key */ unsigned length, const uint8_t *digest, const mp_limb_t *rp, const mp_limb_t *sp, mp_limb_t *scratch);
#endif /* NETTLE_ECDSA_H_INCLUDED */
On 02/13/2013 02:51 PM, Niels Möller wrote:
Hello Niels, I've checked the high level functions and they seem fine. As far as I am concerned I think they can easily update the current gnutls code.
About the naming you use ecdsa_private_key and public_key. Note that this is the same key for static ECDH, and I think MQV.
If there is a function to do the DH multiplication k*(ecdsa_public_key) I think the gnutls could be tested with that interface, if I get some time to do that.
But for ecdsa, do we need any functions like that? I guess, for
I don't know. I wouldn't probably use them, but others may.
which take a hashing context as argument. Which hash functions are
ECDSA-521 521-bit random ECP group SHA-512
As far as I know these are the only allowed by the DSS standard (I was under the impression that SHA-224 was also allowed).
regards, Nikos
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
About the naming you use ecdsa_private_key and public_key. Note that this is the same key for static ECDH, and I think MQV.
Do you have any suggestions for improved naming? I understand ECDH, although it has been a very low priority for me so far, but I'm not familiar with MQV. Would it be better with more algorithm-neutral names, like "ecc_point" and "ecc_scalar"?
The way I think about it, the ecdsa_public key is a combination of a point and a curve-specification. If I add a highlevel "ecc_point" type, should that include a pointer to the curve or not?
If there is a function to do the DH multiplication k*(ecdsa_public_key) I think the gnutls could be tested with that interface,
For ECDH, you could generate a new keypair (P, z) with ecdsa_generate_keypair, send the "public key" P as a point Q to the other party, receive another point Q, and then to compute Y one would need a function like
void ecdsa_private_key_mul (const struct ecdsa_private_key *key, mpz_t new_x, mpz_t new_y, const mpz_t x, const mpz_t y);
(these are not very good names, but I hope you get the idea). At least, if we think about ECDH as using a temporary keypair, then I think it's clearest to view the above operation as an operation using out private key, not as an operation involving the other party's public key.
At least, fips-186-3 is not very specific, I think it allows any any "approved" hash function with security level high enough for the application. Or even any combination of approved curve and approved hash function where *both* have high enough security level for the application.
Regards, /Niels
On 02/14/2013 08:46 AM, Niels Möller wrote:
Any of those would be fine (I prefer point as more intuitive). Having a pointer to the curve is a good thing I believe (a point on that curve). I don't think there are cases where a point can be used in multiple curves. It should be easy to generate those structures from x,y pairs and knowledge of the curve.
Also a function that checks whether a point lies on a curve would be needed (may already be there, didn't check).
Then you may allow hashing directly the output of the hash and not bother with that.
regards, Nikos
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
Also a function that checks whether a point lies on a curve would be needed (may already be there, didn't check).
ecc_set_public_key should do that check.
Regards, /Niels
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
I'm looking into an interface redesign of the high-level ecdsa, using types
/* Represents a point on the ECC curve */ struct ecc_point { const struct ecc_curve *ecc; /* Allocated using the same allocation function as GMP. */ mp_limb_t *p; };
/* Represents a non-zero scalar, an element of Z_q^*, where q is the group order of the curve. */ struct ecc_scalar { const struct ecc_curve *ecc; /* Allocated using the same allocation function as GMP. */ mp_limb_t *p; };
(which are identical, except that they use different allocation size and contents for p...). I think this will be good enough for both ECDH and ECDSA. Some questions:
1. For the final multiplication in ECDH, do you want the complete point, or do you need the x coordinate only?
2. I wonder if I should somehow add some aliases, ecdsa_public_key <=> ecc_point, ecdsa_private_key <=> ecc_scalar?
3. Is there any need to support operations involving the zero point (group zero, curve infinity)? For now, I don't have any high-level function to add two points.
About the zero point, here's a comment from my current implementation of ecdsa_verify.
/* u = 0 can happen only if h = 0 or h = q, which is extremely unlikely. */ if (!zero_p (ecc, u1)) { /* Total storage: 6*ecc->size + ECC_MUL_G_ITCH (ecc->size) */ ecc_mul_g (ecc, P1, u1, u1 + ecc->size);
/* NOTE: ecc_add_jjj and/or ecc_j_to_a will produce garbage in case u1 G = +/- u2 V. However, anyone who gets his or her hands on a signature where this happens during verification, can also get the private key as z = +/- u1 / u_2 (mod q). And then it doesn't matter very much if verification of signatures with that key succeeds or fails.
u1 G = - u2 V can never happen for a correctly generated signature, since it implies k = 0.
u1 G = u2 V is possible, if we are unlucky enough to get h / s_1 = z. Hitting that is about as unlikely as finding the private key by guessing. */ /* Total storage: 6*ecc->size + ECC_ADD_JJJ_ITCH (ecc->size) */ ecc_add_jjj (ecc, P1, P1, P2, u1); }
If/when I switch to different primitives for ecdsa_verify, which are not side-channel silent, I ought to handle those corner cases correctly. But I wonder how important that really is.
And during signing, would it make sense to check if z s_1 = h (here, z is the private key, s_1 is the x coordinate of k G, and h is the message digest), and try a new random k in that case? In addition to the checks for s_1 == 0 or s_2 == 0?
Regards, /Niels
On Mon, Feb 18, 2013 at 10:55 AM, Niels Möller nisse@lysator.liu.se wrote:
Wouldn't you need more than one members there? I'd expect x,y,z. Or you plan to work internally using X9.62 format? Would you also need to keep the size of limb_t?
Why not keep the scalar as just a number (i.e. mpz_t)? Is there any advantage in treating it as related to the curve?
For TLS we only need x. I don't know about other protocols. P1363 should discuss some but it is not publicly available (and it is a shame that IETF ECC-TLS only refers to that).
They could typedefs, or defines, but I don't know whether this would make it more clear.
Few implementations don't handle it at all, but couldn't that be the result of an intermediate calculation? (quite unlikely though but still possible). In that case I'm not sure what happens (those implementations would still return some result).
The check looks like a good one on a first read, but isn't it the same as checking for k being 3? (or whatever fixed value).
regards, Nikos
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
The idea is to use an internal representation which is the same as what the low-level interface expects. So, e.g, if we have 64 bit limbs, and work over the secp256r1 curve, p would point at an area of 8 limbs, where the first 4 represent x and the next 4 represent y.
But you're not expected to need to know the internal representation, just use the get and set functions with coordinates in mpz_t form.
mpz_t is not suitable for side-channel silent operations, since it uses a limb count dependent on the actual value. So if you put a value related to the 521-bit curve in an mpz_t, most values would use 9 64-bit limbs, but with a probability of about 1/512 you'd get only 8 limbs.
Is there any advantage in treating it as related to the curve?
Not sure, but if we add some operations, like add, mul, invert, ..., they should all be mod the curve order, and hence need the curve data.
Ok, then it makes sense to have a function to return x only.
First question is if it is desirable. If it is, it may be a bit difficult to define cleanly, since I use struct tags rather than typedefs for naming.
For the most important operation, n * P, you should not get any zero intermediates assuming that P is non-zero to start with, and that n != 0 (mod group order). Except initially when processing leading zero bits of n, which I handle specially in the multiplication code.
So it doesn't seem essential until we support addition of arbitrary points.
No, just as for the other checks, the condition depends on both k and h.
Regards, /Niels
On Mon, Feb 18, 2013 at 1:10 PM, Niels Möller nisse@lysator.liu.se wrote:
So has this particular case higher probability than k being randomly chosen to be 3? (I've not seen this test anywhere else, that's why I'd be curious on why you mention this test).
regards, Nikos
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
If the verify code is done as
P1 = u1*G P2 = u2*Y
P = P1 + P2
then an equivalent test is needed there, sine we have to do
if (P1 == P2) P = ecc_dup (P1) else P = ecc_add(P1 ,P2)
And if we do this test, it's trivial to extend it to
if (P1 == P2) { P = ecc_dup (P1) output private key (it's -u2/u1 (mod q) or something like that) } else P = ecc_add(P1 ,P2)
So *if* we think that handling this case correctly on the verify side is appropriate, then it seems reasonable, on the signing side, to make sure that it never occurs.
And conversely, if it's too unlikely to bother about when signing, do we need to bother about it when verifying signatures, or is it ok if ecdsa_verify outputs some incorrect result, most likely always "invalid", for this case ?
I have also not seen this case mentioned anywhere, so I'm not sure what's the right thing to do.
Regards, /Niels
On Mon, Feb 18, 2013 at 2:30 PM, Niels Möller nisse@lysator.liu.se wrote:
That's an interesting case :) Several implementations do not include that case. I was told of a fault injection attack in hardware implementations to force them reach that state (and do an addition instead), but that wouldn't be of much importance here (since it is a verification function). I don't know if caring about that case makes sense. At best I think that looks like the definition for the unlikely() macro.
regards, Nikos
nettle-bugs@lists.lysator.liu.se
-
Nikos Mavrogiannopoulos -
nisse＠lysator.liu.se