[PATCH 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 | 169 +++++++++++++++++++++++++++++++++ dsa-compute-k.h | 63 ++++++++++++ testsuite/.gitignore | 1 + testsuite/.test-rules.make | 3 + testsuite/Makefile.in | 3 +- testsuite/dsa-compute-k-test.c | 85 +++++++++++++++++ 7 files changed, 326 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 a6b8ffd6..b0adcb3c 100644 --- a/Makefile.in +++ b/Makefile.in @@ -186,7 +186,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

@@ -236,7 +237,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..ba9b50df --- /dev/null +++ b/dsa-compute-k.c @@ -0,0 +1,169 @@ +/* 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> + +#define MIN(x, y) ((x) < (y) ? (x) : (y)) +#define MAX(x, y) ((x) < (y) ? (y) : (x)) + +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; + mp_bitcnt_t k_bits; + size_t nbytes = (q_bits + 7) / 8; + const uint8_t c0 = 0x00; + const uint8_t c1 = 0x01; + + 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(hn, qn) * 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) + mpn_copyi (h, &h[hn - qn], qn); + else if (hn < qn) + mpn_zero (&h[hn], qn - hn); + if (h[qn - 1] > 0) + { + h_bits = ((mpn_sizeinbase (h, qn, 2) + 7) / 8) * 8; + if (h_bits > q_bits) + mpn_rshift (h, h, qn, h_bits - q_bits); + } + cnd_sub_n (mpn_cmp (h, q, qn) > 0, 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 (k[qn - 1] > 0) + { + k_bits = ((mpn_sizeinbase (k, qn, 2) + 7) / 8) * 8; + if (k_bits > q_bits) + mpn_rshift (k, k, qn, k_bits - 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 4d680cd1..6adde730 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 ab22da23..c3a5bb85 100644 --- a/testsuite/.test-rules.make +++ b/testsuite/.test-rules.make @@ -277,6 +277,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 9a1fe209..3bc22057 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..07b0a06e --- /dev/null +++ b/testsuite/dsa-compute-k-test.c @@ -0,0 +1,85 @@ +#include "testutils.h" +#include "dsa-compute-k.h" +#include "hmac.h" + +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 (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"); +}