[PATCH v2 1/3] dsa: Add a function to find k deterministically

From: Daiki Ueno dueno@redhat.com

This adds the _dsa_compute_k function that generates DSA/ECDSA k value from the private key and the hashed message, according to RFC 6979.

Signed-off-by: Daiki Ueno dueno@redhat.com --- Makefile.in | 5 +- dsa-compute-k.c | 179 +++++++++++++++++++++++++++++++++ dsa-compute-k.h | 63 ++++++++++++ testsuite/.gitignore | 1 + testsuite/.test-rules.make | 3 + testsuite/Makefile.in | 3 +- testsuite/dsa-compute-k-test.c | 127 +++++++++++++++++++++++ 7 files changed, 378 insertions(+), 3 deletions(-) create mode 100644 dsa-compute-k.c create mode 100644 dsa-compute-k.h create mode 100644 testsuite/dsa-compute-k-test.c

diff --git a/Makefile.in b/Makefile.in index b54e64b0..36b2a182 100644 --- a/Makefile.in +++ b/Makefile.in @@ -187,7 +187,8 @@ hogweed_SOURCES = sexp.c sexp-format.c \ eddsa-compress.c eddsa-decompress.c eddsa-expand.c \ eddsa-hash.c eddsa-pubkey.c eddsa-sign.c eddsa-verify.c \ ed25519-sha512-pubkey.c \ - ed25519-sha512-sign.c ed25519-sha512-verify.c + ed25519-sha512-sign.c ed25519-sha512-verify.c \ + dsa-compute-k.c

OPT_SOURCES = fat-x86_64.c fat-arm.c mini-gmp.c

@@ -237,7 +238,7 @@ DISTFILES = $(SOURCES) $(HEADERS) getopt.h getopt_int.h \ ctr-internal.h chacha-internal.h sha3-internal.h \ salsa20-internal.h umac-internal.h hogweed-internal.h \ rsa-internal.h pkcs1-internal.h dsa-internal.h eddsa-internal.h \ - gmp-glue.h ecc-internal.h fat-setup.h \ + gmp-glue.h ecc-internal.h fat-setup.h dsa-compute-k.h \ mini-gmp.h asm.m4 \ nettle.texinfo nettle.info nettle.html nettle.pdf sha-example.c

diff --git a/dsa-compute-k.c b/dsa-compute-k.c new file mode 100644 index 00000000..105c500b --- /dev/null +++ b/dsa-compute-k.c @@ -0,0 +1,179 @@ +/* dsa-compute-k.c + + Deterministically find k value for ECDSA/DSA (RFC-6979). + + Copyright (C) 2019 Red Hat, Inc. + + 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/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "dsa-compute-k.h" + +#include "gmp-glue.h" +#include "nettle-internal.h" +#include <string.h> +#include <stdio.h> + +#define MIN(x, y) ((x) < (y) ? (x) : (y)) +#define MAX(x, y) ((x) > (y) ? (x) : (y)) + +void +_dsa_compute_k (mp_limb_t *k, + mp_size_t qn, + const mp_limb_t *q, + const mp_limb_t *x, + void *mac_ctx, + nettle_hash_update_func *set_key, + nettle_hash_update_func *update, + nettle_hash_digest_func *digest, + size_t digest_length, + const uint8_t *digest_message) +{ + TMP_DECL(V, uint8_t, NETTLE_MAX_HASH_DIGEST_SIZE); + TMP_DECL(K, uint8_t, NETTLE_MAX_HASH_DIGEST_SIZE); + TMP_GMP_DECL(xp, uint8_t); + TMP_GMP_DECL(hp, uint8_t); + TMP_GMP_DECL(tp, uint8_t); + TMP_GMP_DECL(h, mp_limb_t); + mp_size_t hn = (digest_length + sizeof(mp_limb_t) - 1) / sizeof(mp_limb_t); + mp_bitcnt_t q_bits = mpn_sizeinbase (q, qn, 2); + mp_bitcnt_t h_bits = digest_length * 8; + size_t nbytes = (q_bits + 7) / 8; + const uint8_t c0 = 0x00; + const uint8_t c1 = 0x01; + mp_limb_t cy; + + TMP_ALLOC(V, digest_length); + TMP_ALLOC(K, digest_length); + TMP_GMP_ALLOC(xp, nbytes); + TMP_GMP_ALLOC(hp, nbytes); + TMP_GMP_ALLOC(tp, nbytes); + TMP_GMP_ALLOC(h, MAX (qn, hn) * sizeof(mp_limb_t)); + + /* int2octets(x) */ + mpn_get_base256 (xp, nbytes, x, qn); + + /* bits2octets(h) */ + mpn_set_base256 (h, hn, digest_message, digest_length); + + if (hn < qn) + /* qlen > blen: add zero bits to the left */ + mpn_zero (&h[hn], qn - hn); + else if (h_bits > q_bits) + { + /* qlen < blen: keep the leftmost qlen bits. We do this in 2 + * steps because mpn_rshift only accepts shift count in the + * range 1 to mp_bits_per_limb-1. + */ + mp_bitcnt_t shift = h_bits - q_bits; + + if (shift / GMP_LIMB_BITS > 0) + { + mpn_copyi (h, &h[shift / GMP_LIMB_BITS], qn); + hn -= shift / GMP_LIMB_BITS; + } + + if (shift % GMP_LIMB_BITS > 0) + mpn_rshift (h, h, hn, shift % GMP_LIMB_BITS); + } + + cy = mpn_sub_n (h, h, q, qn); + cy = cnd_add_n (cy, h, q, qn); + mpn_get_base256 (hp, nbytes, h, qn); + + /* Step b */ + memset (V, c1, digest_length); + + /* Step c */ + memset (K, c0, digest_length); + set_key (mac_ctx, digest_length, K); + + /* Step d */ + update (mac_ctx, digest_length, V); + update (mac_ctx, 1, &c0); + update (mac_ctx, nbytes, xp); + update (mac_ctx, nbytes, hp); + digest (mac_ctx, digest_length, K); + set_key (mac_ctx, digest_length, K); + + /* Step e */ + update (mac_ctx, digest_length, V); + digest (mac_ctx, digest_length, V); + + /* Step f */ + update (mac_ctx, digest_length, V); + update (mac_ctx, 1, &c1); + update (mac_ctx, nbytes, xp); + update (mac_ctx, nbytes, hp); + digest (mac_ctx, digest_length, K); + set_key (mac_ctx, digest_length, K); + + /* Step g */ + update (mac_ctx, digest_length, V); + digest (mac_ctx, digest_length, V); + + /* Step h */ + for (;;) + { + /* Step 1 */ + size_t tlen = 0; + + /* Step 2 */ + while (tlen < nbytes) + { + size_t remaining = MIN(nbytes - tlen, digest_length); + update (mac_ctx, digest_length, V); + digest (mac_ctx, digest_length, V); + memcpy (&tp[tlen], V, remaining); + tlen += remaining; + } + + /* Step 3 */ + mpn_set_base256 (k, qn, tp, tlen); + if (tlen * 8 > q_bits) + mpn_rshift (k, k, qn, tlen * 8 - q_bits); + /* Check if k is in [1,q-1] */ + if (!mpn_zero_p (k, qn) && mpn_cmp (k, q, qn) < 0) + break; + + update (mac_ctx, digest_length, V); + update (mac_ctx, 1, &c0); + digest (mac_ctx, digest_length, K); + set_key (mac_ctx, digest_length, K); + update (mac_ctx, digest_length, V); + digest (mac_ctx, digest_length, V); + } + + TMP_GMP_FREE(xp); + TMP_GMP_FREE(hp); + TMP_GMP_FREE(tp); + TMP_GMP_FREE(h); +} diff --git a/dsa-compute-k.h b/dsa-compute-k.h new file mode 100644 index 00000000..3433e2fb --- /dev/null +++ b/dsa-compute-k.h @@ -0,0 +1,63 @@ +/* dsa-compute-k.h + + Deterministically find k value for ECDSA/DSA (RFC-6979). + + Copyright (C) 2019 Red Hat, Inc. + + 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/. +*/ + +#ifndef NETTLE_DSA_COMPUTE_K_H_INCLUDED +#define NETTLE_DSA_COMPUTE_K_H_INCLUDED + +#include "nettle-types.h" +#include "bignum.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* Namespace mangling */ +#define _dsa_compute_k _nettle_dsa_compute_k + +void +_dsa_compute_k (mp_limb_t *k, + mp_size_t qn, + const mp_limb_t *q, + const mp_limb_t *x, + void *mac_ctx, + nettle_hash_update_func *set_key, + nettle_hash_update_func *update, + nettle_hash_digest_func *digest, + size_t digest_length, + const uint8_t *digest_message); + +#ifdef __cplusplus +} +#endif + +#endif /* NETTLE_DSA_COMPUTE_K_H_INCLUDED */ diff --git a/testsuite/.gitignore b/testsuite/.gitignore index 066bcee2..40fbe046 100644 --- a/testsuite/.gitignore +++ b/testsuite/.gitignore @@ -22,6 +22,7 @@ /des-test /des3-test /dlopen-test +/dsa-compute-k-test /dsa-keygen-test /dsa-test /eax-test diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make index efb7df3c..61080010 100644 --- a/testsuite/.test-rules.make +++ b/testsuite/.test-rules.make @@ -280,6 +280,9 @@ eddsa-verify-test$(EXEEXT): eddsa-verify-test.$(OBJEXT) ed25519-test$(EXEEXT): ed25519-test.$(OBJEXT) $(LINK) ed25519-test.$(OBJEXT) $(TEST_OBJS) -o ed25519-test$(EXEEXT)

+dsa-compute-k-test$(EXEEXT): dsa-compute-k-test.$(OBJEXT) + $(LINK) dsa-compute-k-test.$(OBJEXT) $(TEST_OBJS) -o dsa-compute-k-test$(EXEEXT) + sha1-huge-test$(EXEEXT): sha1-huge-test.$(OBJEXT) $(LINK) sha1-huge-test.$(OBJEXT) $(TEST_OBJS) -o sha1-huge-test$(EXEEXT)

diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in index f8f85701..e6acd788 100644 --- a/testsuite/Makefile.in +++ b/testsuite/Makefile.in @@ -52,7 +52,8 @@ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \ ecdsa-sign-test.c ecdsa-verify-test.c \ ecdsa-keygen-test.c ecdh-test.c \ eddsa-compress-test.c eddsa-sign-test.c \ - eddsa-verify-test.c ed25519-test.c + eddsa-verify-test.c ed25519-test.c \ + dsa-compute-k-test.c

TS_SOURCES = $(TS_NETTLE_SOURCES) $(TS_HOGWEED_SOURCES) CXX_SOURCES = cxx-test.cxx diff --git a/testsuite/dsa-compute-k-test.c b/testsuite/dsa-compute-k-test.c new file mode 100644 index 00000000..3df9b2e8 --- /dev/null +++ b/testsuite/dsa-compute-k-test.c @@ -0,0 +1,127 @@ +#include "testutils.h" +#include "dsa-compute-k.h" +#include "hmac.h" + +#if HAVE_VALGRIND_MEMCHECK_H +# include <valgrind/memcheck.h> + +static nettle_hash_digest_func *digest_func; + +static void +digest_func_for_test(void *ctx, + size_t length, uint8_t *dst) +{ + digest_func (ctx, length, dst); + VALGRIND_MAKE_MEM_DEFINED (dst, length); +} + +static void +_dsa_compute_k_for_test (mp_limb_t *k, + mp_size_t qn, + const mp_limb_t *q, + const mp_limb_t *x, + void *mac_ctx, + nettle_hash_update_func *set_key, + nettle_hash_update_func *update, + nettle_hash_digest_func *digest, + size_t digest_length, + const uint8_t *digest_message) +{ + /* Makes valgrind trigger on any branches depending on the input + data. */ + VALGRIND_MAKE_MEM_UNDEFINED (x, qn * sizeof(mp_limb_t)); + VALGRIND_MAKE_MEM_UNDEFINED (digest_message, digest_length); + + digest_func = digest; + _dsa_compute_k (k, qn, q, x, mac_ctx, set_key, update, digest_func_for_test, + digest_length, digest_message); + + VALGRIND_MAKE_MEM_DEFINED (x, qn * sizeof(mp_limb_t)); + VALGRIND_MAKE_MEM_DEFINED (digest_message, digest_length); + VALGRIND_MAKE_MEM_DEFINED (k, qn * sizeof(mp_limb_t)); +} +#else +#define _dsa_compute_k_test _dsa_compute_k +#endif + +static void +test_dsa_compute_k(const char *sq, + /* Private key */ + const char *sx, + /* HMAC */ + void *mac_ctx, + nettle_hash_update_func *set_key, + nettle_hash_update_func *update, + nettle_hash_digest_func *digest, + /* Hash */ + const struct tstring *h, + /* Expected k */ + const char *sk) +{ + mpz_t k; + mpz_t q; + mpz_t x; + mpz_t e; + + mpz_init (k); + mpz_init_set_str (q, sq, 16); + mpz_init_set_str (x, sx, 16); + mpz_init_set_str (e, sk, 16); + + _dsa_compute_k_for_test (mpz_limbs_write (k, mpz_size (q)), + mpz_size (q), mpz_limbs_read (q), mpz_limbs_read (x), + mac_ctx, set_key, update, digest, + h->length, h->data); + + mpz_limbs_finish (k, mpz_size (q)); + + if (mpz_cmp (e, k) != 0) + { + fprintf (stderr, "k = "); + mpz_out_str (stderr, 16, k); + fprintf (stderr, "\n"); + fprintf (stderr, "e = "); + mpz_out_str (stderr, 16, e); + fprintf (stderr, "\n"); + abort (); + } + + mpz_clear (q); + mpz_clear (x); + mpz_clear (k); + mpz_clear (e); +} + +void +test_main (void) +{ + struct hmac_sha256_ctx hmac; + struct sha256_ctx hash; + uint8_t digest[SHA256_DIGEST_SIZE]; + + sha256_init (&hash); + sha256_update (&hash, 6, (const uint8_t *)"sample"); + sha256_digest (&hash, sizeof(digest), digest); + + /* Test vectors from RFC 6979 */ + test_dsa_compute_k ("996f967f6c8e388d9e28d01e205fba957a5698b1", + "411602cb19a6ccc34494d79d98ef1e7ed5af25f7", + &hmac, + (nettle_hash_update_func *)hmac_sha256_set_key, + (nettle_hash_update_func *)hmac_sha256_update, + (nettle_hash_digest_func *)hmac_sha256_digest, + tstring_data (SHA256_DIGEST_SIZE, digest), + "519ba0546d0c39202a7d34d7dfa5e760b318bcfb"); + + test_dsa_compute_k ("f2c3119374ce76c9356990b465374a17f23f9ed3" + "5089bd969f61c6dde9998c1f", + "69c7548c21d0dfea6b9a51c9ead4e27c33d3b3f1" + "80316e5bcab92c933f0e4dbc", + &hmac, + (nettle_hash_update_func *)hmac_sha256_set_key, + (nettle_hash_update_func *)hmac_sha256_update, + (nettle_hash_digest_func *)hmac_sha256_digest, + tstring_data (SHA256_DIGEST_SIZE, digest), + "8926a27c40484216f052f4427cfd5647338b7b39" + "39bc6573af4333569d597c52"); +}