Hello,
The attached patch adds support for the deterministic DSA and ECDSA, as defined in RFC 6979, which enables us to use the signing function without randomness.
The original code has been hosted in GnuTLS for a while, implemented as a custom random function which can be used in combination with dsa_sign and ecdsa_sign. While this approach works in general, it requires pre/post processing: e.g., access to ECC q[1] and cancelling out the Nettle's tweak in dsa_sign adding 1[2] to the random value. Therefore, I would rather like this to be included in Nettle itself. Note also that this implementation should be identical to the latest code in GnuTLS, which addresses the Minerva attack[3].
The same patch is also available at GitLab: https://git.lysator.liu.se/nettle/nettle/-/merge_requests/64
Footnotes: [1] https://gitlab.com/gnutls/gnutls/-/blob/c1428c07d406f18cca94f94e2b7ca1f866df...
[2] https://gitlab.com/gnutls/gnutls/-/blob/c1428c07d406f18cca94f94e2b7ca1f866df...
[3] https://nvd.nist.gov/vuln/detail/CVE-2024-28834
Regards,
Daiki Ueno ueno@gnu.org writes:
The attached patch adds support for the deterministic DSA and ECDSA, as defined in RFC 6979, which enables us to use the signing function without randomness.
Thanks, I've had a first read, and added some comments on your MR (https://git.lysator.liu.se/nettle/nettle/-/merge_requests/64).
Regards, /Niels
Niels Möller nisse@lysator.liu.se writes:
Daiki Ueno ueno@gnu.org writes:
The attached patch adds support for the deterministic DSA and ECDSA, as defined in RFC 6979, which enables us to use the signing function without randomness.
Thanks, I've had a first read, and added some comments on your MR (https://git.lysator.liu.se/nettle/nettle/-/merge_requests/64).
Thank you; I updated the MR to address those comments.
I have a slight feeling that the current API is not easy to use, as the caller needs to instantiate both hash and HMAC contexts, as there are no correlations between the two:
struct sha256_ctx sha256; sha256_init (&sha256); sha256_update (&sha256, length, message); sha256_digest (&sha256, SHA256_DIGEST_SIZE, digest);
struct hmac_sha256_ctx hmac_sha256; ecdsa_sign_deterministic (&key, &hmac_sha256, &nettle_hmac_sha256, digest, &sig);
What would you say to introducing a specialized API, something like the following?
void ecdsa_sha256_sign_deterministic (const struct ecc_scalar *key, size_t length, const uint8_t *message, struct dsa_signature *signature);
Regards,
Daiki Ueno ueno@gnu.org writes:
I have a slight feeling that the current API is not easy to use, as the caller needs to instantiate both hash and HMAC contexts, as there are no correlations between the two:
On a more abstract level, are there any reasonable usecases for having one hash function for processing the message, and a different underlying hash function for the hmac used to produce the deterministic nonce?
What would you say to introducing a specialized API, something like the following?
void ecdsa_sha256_sign_deterministic (const struct ecc_scalar *key, size_t length, const uint8_t *message, struct dsa_signature *signature);
I think that could sense, but we also need an advertised api function that takes the digest as input, for applications that want to process the message using multiple _update calls.
Regards, /Niels
Niels Möller nisse@lysator.liu.se writes:
Daiki Ueno ueno@gnu.org writes:
I have a slight feeling that the current API is not easy to use, as the caller needs to instantiate both hash and HMAC contexts, as there are no correlations between the two:
On a more abstract level, are there any reasonable usecases for having one hash function for processing the message, and a different underlying hash function for the hmac used to produce the deterministic nonce?
Not that I know of. The RFC mandates the same hash function to be used in both for processing the message and generating a nonce.
What would you say to introducing a specialized API, something like the following?
void ecdsa_sha256_sign_deterministic (const struct ecc_scalar *key, size_t length, const uint8_t *message, struct dsa_signature *signature);
I think that could sense, but we also need an advertised api function that takes the digest as input, for applications that want to process the message using multiple _update calls.
I agree, that's a valid use-case. Perhaps this might suffice:
/* Sign DIGEST with KEY using deterministic nonce generation. * * DIGEST must be of the same length of SHA-256 output, that is 32 * octets long. */ void ecdsa_sha256_sign_deterministic (const struct ecc_scalar *key, const uint8_t *digest, struct dsa_signature *signature);
Regards,
Daiki Ueno ueno@gnu.org writes:
I agree, that's a valid use-case. Perhaps this might suffice:
/* Sign DIGEST with KEY using deterministic nonce generation.
- DIGEST must be of the same length of SHA-256 output, that is 32
- octets long. */
void ecdsa_sha256_sign_deterministic (const struct ecc_scalar *key, const uint8_t *digest, struct dsa_signature *signature);
Looks good to me. Underlying more general helper functions (however they are organized) can be internal only.
Regards, /Niels
Niels Möller nisse@lysator.liu.se writes:
Daiki Ueno ueno@gnu.org writes:
I agree, that's a valid use-case. Perhaps this might suffice:
/* Sign DIGEST with KEY using deterministic nonce generation.
- DIGEST must be of the same length of SHA-256 output, that is 32
- octets long. */
void ecdsa_sha256_sign_deterministic (const struct ecc_scalar *key, const uint8_t *digest, struct dsa_signature *signature);
Looks good to me. Underlying more general helper functions (however they are organized) can be internal only.
I've updated the MR along these lines.
Regards,
Somewhat related to RFC 6979, I've made a patch to unify the way digest is converted to integer (bits2int, except that it doesn't produce canonical representation mod q).
I think it would make sense to have a shared helper function for signing, that takes integer representation of both h (hash) and k (nonce) as input.
Regards, /Niels
diff --git a/Makefile.in b/Makefile.in index cfc83e0b..2bf7f1e8 100644 --- a/Makefile.in +++ b/Makefile.in @@ -212,7 +212,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \ ecc-dup-eh.c ecc-add-eh.c ecc-add-ehh.c \ ecc-dup-th.c ecc-add-th.c ecc-add-thh.c \ ecc-mul-g-eh.c ecc-mul-a-eh.c ecc-mul-m.c \ - ecc-mul-g.c ecc-mul-a.c ecc-hash.c ecc-random.c \ + ecc-mul-g.c ecc-mul-a.c ecc-random.c \ ecc-point.c ecc-scalar.c ecc-point-mul.c ecc-point-mul-g.c \ ecc-ecdsa-sign.c ecdsa-sign.c \ ecc-ecdsa-verify.c ecdsa-verify.c ecdsa-keygen.c \ diff --git a/dsa-hash.c b/dsa-hash.c index aab3c838..26aa4917 100644 --- a/dsa-hash.c +++ b/dsa-hash.c @@ -33,25 +33,50 @@ # include "config.h" #endif
+#include <assert.h> + #include "dsa.h" #include "dsa-internal.h"
-#include "bignum.h" +#include "gmp-glue.h"
/* Convert hash value to an integer. The general description of DSA in - FIPS186-3 allows both larger and smaller q; in the the latter case, - the hash must be truncated to the right number of bits. */ + FIPS186-3 allows both larger and smaller q; in the the former case + the hash is zero-padded at the left, in the latter case, the hash + is truncated at the right. + + NOTE: We don't considered the hash value to be secret, so it's ok + if the running time of this conversion depends on h. + + Output size is ceil(bit_size / GMP_NUMB_BITS). +*/ + void -_nettle_dsa_hash (mpz_t h, unsigned bit_size, +_nettle_dsa_hash (mp_limb_t *hp, unsigned bit_size, size_t length, const uint8_t *digest) { - - if (length > (bit_size + 7) / 8) - length = (bit_size + 7) / 8; + unsigned octet_size = (bit_size + 7) / 8; + unsigned limb_size = NETTLE_BIT_SIZE_TO_LIMB_SIZE (bit_size); + + if (length > octet_size) + length = octet_size;
- nettle_mpz_set_str_256_u(h, length, digest); + mpn_set_base256(hp, limb_size, digest, length);
if (8 * length > bit_size) /* We got a few extra bits, at the low end. Discard them. */ - mpz_tdiv_q_2exp (h, h, 8*length - bit_size); + mpn_rshift (hp, hp, limb_size, 8*length - bit_size); +} + +void +_nettle_gostdsa_hash (mp_limb_t *hp, unsigned bit_size, + size_t length, const uint8_t *digest) +{ + unsigned octet_size = (bit_size + 7) / 8; + unsigned limb_size = (bit_size + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS; + + if (length > octet_size) + length = octet_size; + + mpn_set_base256_le(hp, limb_size, digest, length); } diff --git a/dsa-internal.h b/dsa-internal.h index ce57c72a..7baa6ba0 100644 --- a/dsa-internal.h +++ b/dsa-internal.h @@ -38,8 +38,12 @@
/* Internal functions. */ void -_nettle_dsa_hash (mpz_t h, unsigned bit_size, +_nettle_dsa_hash (mp_limb_t *hp, unsigned bit_size, size_t length, const uint8_t *digest);
+void +_nettle_gostdsa_hash (mp_limb_t *hp, unsigned bit_size, + size_t length, const uint8_t *digest); +
#endif /* NETTLE_DSA_INTERNAL_H_INCLUDED */ diff --git a/dsa-sign.c b/dsa-sign.c index 42a0a581..ff66a0a6 100644 --- a/dsa-sign.c +++ b/dsa-sign.c @@ -42,7 +42,7 @@ #include "dsa-internal.h"
#include "bignum.h" - +#include "gmp-glue.h"
int dsa_sign(const struct dsa_params *params, @@ -55,8 +55,11 @@ dsa_sign(const struct dsa_params *params, mpz_t k; mpz_t h; mpz_t tmp; + unsigned bit_size; + unsigned limb_size; + int res; - + /* Check that p is odd, so that invalid keys don't result in a crash inside mpz_powm_sec. */ if (mpz_even_p (params->p)) @@ -75,8 +78,11 @@ dsa_sign(const struct dsa_params *params, mpz_fdiv_r(signature->r, tmp, params->q);
/* Compute hash */ + bit_size = mpz_sizeinbase(params->q, 2); + limb_size = NETTLE_BIT_SIZE_TO_LIMB_SIZE(bit_size); mpz_init(h); - _nettle_dsa_hash (h, mpz_sizeinbase(params->q, 2), digest_size, digest); + _nettle_dsa_hash (mpz_limbs_write (h, limb_size), bit_size, digest_size, digest); + mpz_limbs_finish (h, limb_size);
/* Compute k^-1 (mod q) */ if (mpz_invert(k, k, params->q)) diff --git a/dsa-verify.c b/dsa-verify.c index eb573fe3..aec62fae 100644 --- a/dsa-verify.c +++ b/dsa-verify.c @@ -41,6 +41,7 @@ #include "dsa-internal.h"
#include "bignum.h" +#include "gmp-glue.h"
int dsa_verify(const struct dsa_params *params, @@ -52,6 +53,8 @@ dsa_verify(const struct dsa_params *params, mpz_t w; mpz_t tmp; mpz_t v; + unsigned bit_size; + unsigned limb_size;
int res;
@@ -78,7 +81,10 @@ dsa_verify(const struct dsa_params *params, mpz_init(v);
/* The message digest */ - _nettle_dsa_hash (tmp, mpz_sizeinbase (params->q, 2), digest_size, digest); + bit_size = mpz_sizeinbase(params->q, 2); + limb_size = NETTLE_BIT_SIZE_TO_LIMB_SIZE(bit_size); + _nettle_dsa_hash (mpz_limbs_write (tmp, limb_size), bit_size, digest_size, digest); + mpz_limbs_finish (tmp, limb_size);
/* v = g^{w * h (mod q)} (mod p) */ mpz_mul(tmp, tmp, w); diff --git a/ecc-ecdsa-sign.c b/ecc-ecdsa-sign.c index 6a41c14c..522a04d4 100644 --- a/ecc-ecdsa-sign.c +++ b/ecc-ecdsa-sign.c @@ -40,6 +40,7 @@
#include "ecdsa.h" #include "ecc-internal.h" +#include "dsa-internal.h"
/* Low-level ECDSA signing */
@@ -87,7 +88,7 @@ ecc_ecdsa_sign (const struct ecc_curve *ecc, ecc->q.invert (&ecc->q, kinv, kp, tp);
/* Process hash digest */ - ecc_hash (&ecc->q, hp, length, digest); + _nettle_dsa_hash (hp, ecc->q.bit_size, length, digest);
ecc_mod_mul (&ecc->q, tp, zp, rp, tp); ecc_mod_add (&ecc->q, hp, hp, tp); diff --git a/ecc-ecdsa-verify.c b/ecc-ecdsa-verify.c index 9e324ea2..6481b6c3 100644 --- a/ecc-ecdsa-verify.c +++ b/ecc-ecdsa-verify.c @@ -40,6 +40,7 @@
#include "ecdsa.h" #include "ecc-internal.h" +#include "dsa-internal.h"
/* Low-level ECDSA verify */
@@ -101,7 +102,7 @@ ecc_ecdsa_verify (const struct ecc_curve *ecc, ecc->q.invert (&ecc->q, sinv, sp, sinv + ecc->p.size);
/* u1 = h / s, P1 = u1 * G */ - ecc_hash (&ecc->q, hp, length, digest); + _nettle_dsa_hash (hp, ecc->q.bit_size, length, digest); ecc_mod_mul_canonical (&ecc->q, u1, hp, sinv, u1);
/* u2 = r / s, P2 = u2 * Y */ diff --git a/ecc-gostdsa-sign.c b/ecc-gostdsa-sign.c index c811c87e..f5a0cf7b 100644 --- a/ecc-gostdsa-sign.c +++ b/ecc-gostdsa-sign.c @@ -79,7 +79,7 @@ ecc_gostdsa_sign (const struct ecc_curve *ecc, ecc_j_to_a (ecc, 2, rp, P, P + 3*ecc->p.size);
/* Process hash digest */ - gost_hash (&ecc->q, hp, length, digest); + _nettle_gostdsa_hash (hp, ecc->q.bit_size, length, digest); if (mpn_zero_p (hp, ecc->p.size)) mpn_add_1 (hp, hp, ecc->p.size, 1);
diff --git a/ecc-gostdsa-verify.c b/ecc-gostdsa-verify.c index 0570af7e..14c12335 100644 --- a/ecc-gostdsa-verify.c +++ b/ecc-gostdsa-verify.c @@ -93,7 +93,7 @@ ecc_gostdsa_verify (const struct ecc_curve *ecc, && ecdsa_in_range (ecc, sp))) return 0;
- gost_hash (&ecc->q, hp, length, digest); + _nettle_gostdsa_hash (hp, ecc->q.bit_size, length, digest);
if (mpn_zero_p (hp, ecc->p.size)) mpn_add_1 (hp, hp, ecc->p.size, 1); diff --git a/ecc-hash.c b/ecc-hash.c deleted file mode 100644 index 07877110..00000000 --- a/ecc-hash.c +++ /dev/null @@ -1,75 +0,0 @@ -/* ecdsa-hash.c - - Copyright (C) 2013 Niels Möller - - This file is part of GNU Nettle. - - GNU Nettle is free software: you can redistribute it and/or - modify it under the terms of either: - - * the GNU Lesser General Public License as published by the Free - Software Foundation; either version 3 of the License, or (at your - option) any later version. - - or - - * the GNU General Public License as published by the Free - Software Foundation; either version 2 of the License, or (at your - option) any later version. - - or both in parallel, as here. - - GNU Nettle 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 - General Public License for more details. - - You should have received copies of the GNU General Public License and - the GNU Lesser General Public License along with this program. If - not, see http://www.gnu.org/licenses/. -*/ - -/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */ - -#if HAVE_CONFIG_H -# include "config.h" -#endif - -#include "ecc-internal.h" - -/* Convert hash value to an integer. If the digest is larger than - the ecc bit size, then we must truncate it and use the leftmost - bits. */ - -/* NOTE: We don't considered the hash value to be secret, so it's ok - if the running time of this conversion depends on h. - - Requires m->size + 1 limbs, the extra limb may be needed for - unusual limb sizes. -*/ - -void -ecc_hash (const struct ecc_modulo *m, - mp_limb_t *hp, - size_t length, const uint8_t *digest) -{ - if (length > ((size_t) m->bit_size + 7) / 8) - length = (m->bit_size + 7) / 8; - - mpn_set_base256 (hp, m->size + 1, digest, length); - - if (8 * length > m->bit_size) - /* We got a few extra bits, at the low end. Discard them. */ - mpn_rshift (hp, hp, m->size + 1, 8*length - m->bit_size); -} - -void -gost_hash (const struct ecc_modulo *m, - mp_limb_t *hp, - size_t length, const uint8_t *digest) -{ - if (length > ((size_t) m->bit_size + 7) / 8) - length = (m->bit_size + 7) / 8; - - mpn_set_base256_le (hp, m->size + 1, digest, length); -} diff --git a/ecc-internal.h b/ecc-internal.h index 43233043..b4b45bae 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -58,7 +58,6 @@ #define ecc_mod_random _nettle_ecc_mod_random #define ecc_mod _nettle_ecc_mod #define ecc_mod_inv _nettle_ecc_mod_inv -#define ecc_hash _nettle_ecc_hash #define gost_hash _nettle_gost_hash #define ecc_a_to_j _nettle_ecc_a_to_j #define ecc_j_to_a _nettle_ecc_j_to_a @@ -339,16 +338,6 @@ void ecc_mod_random (const struct ecc_modulo *m, mp_limb_t *xp, void *ctx, nettle_random_func *random, mp_limb_t *scratch);
-void -ecc_hash (const struct ecc_modulo *m, - mp_limb_t *hp, - size_t length, const uint8_t *digest); - -void -gost_hash (const struct ecc_modulo *m, - mp_limb_t *hp, - size_t length, const uint8_t *digest); - /* Converts a point P in affine coordinates into a point R in jacobian coordinates. */ void diff --git a/gmp-glue.h b/gmp-glue.h index afe94635..321cb448 100644 --- a/gmp-glue.h +++ b/gmp-glue.h @@ -85,8 +85,11 @@ is_zero_limb (mp_limb_t x) int sec_zero_p (const mp_limb_t *ap, mp_size_t n);
+#define NETTLE_BIT_SIZE_TO_LIMB_SIZE(n) \ + (((n) + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS) + #define NETTLE_OCTET_SIZE_TO_LIMB_SIZE(n) \ - (((n) * 8 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS) + (NETTLE_BIT_SIZE_TO_LIMB_SIZE((n) * 8))
/* Convenience functions */
nettle-bugs@lists.lysator.liu.se
-
Daiki Ueno -
Niels Möller