From: Daiki Ueno dueno@redhat.com
This adds the ecdsa_sign_deterministic function that calculates signature without requiring entropy source. Instead, it uses the deterministic construction described in RFC 6979, through _dsa_compute_k.
Signed-off-by: Daiki Ueno dueno@redhat.com --- Makefile.in | 2 +- ecdsa-sign-deterministic.c | 78 ++++++++++ ecdsa.h | 11 ++ testsuite/.gitignore | 1 + testsuite/.test-rules.make | 3 + testsuite/Makefile.in | 3 +- testsuite/ecdsa-sign-deterministic-test.c | 164 ++++++++++++++++++++++ 7 files changed, 260 insertions(+), 2 deletions(-) create mode 100644 ecdsa-sign-deterministic.c create mode 100644 testsuite/ecdsa-sign-deterministic-test.c
diff --git a/Makefile.in b/Makefile.in index b0adcb3c..5f77b98d 100644 --- a/Makefile.in +++ b/Makefile.in @@ -187,7 +187,7 @@ hogweed_SOURCES = sexp.c sexp-format.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 \ - dsa-compute-k.c + dsa-compute-k.c ecdsa-sign-deterministic.c
OPT_SOURCES = fat-x86_64.c fat-arm.c mini-gmp.c
diff --git a/ecdsa-sign-deterministic.c b/ecdsa-sign-deterministic.c new file mode 100644 index 00000000..dd5b88d9 --- /dev/null +++ b/ecdsa-sign-deterministic.c @@ -0,0 +1,78 @@ +/* ecdsa-sign-deterministic.c + + Copyright (C) 2013 Niels Möller + 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/. +*/ + +/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <assert.h> +#include <stdlib.h> + +#include "ecdsa.h" +#include "ecc-internal.h" +#include "nettle-internal.h" +#include "dsa-compute-k.h" + +void +ecdsa_sign_deterministic (const struct ecc_scalar *key, + 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, + struct dsa_signature *signature) +{ + /* At most 936 bytes. */ + TMP_DECL(k, mp_limb_t, ECC_MAX_SIZE + ECC_ECDSA_SIGN_ITCH (ECC_MAX_SIZE)); + mp_limb_t size = key->ecc->p.size; + mp_limb_t *rp = mpz_limbs_write (signature->r, size); + mp_limb_t *sp = mpz_limbs_write (signature->s, size); + + TMP_ALLOC (k, size + ECC_ECDSA_SIGN_ITCH (size)); + + /* Timing reveals the number of rounds through this loop, but the + timing is still independent of the secret k finally used. */ + do + { + _dsa_compute_k (k, key->ecc->q.size, key->ecc->q.m, key->p, + mac_ctx, set_key, update, digest, + digest_length, digest_message); + ecc_ecdsa_sign (key->ecc, key->p, k, digest_length, digest_message, + rp, sp, k + size); + mpz_limbs_finish (signature->r, size); + mpz_limbs_finish (signature->s, size); + } + while (mpz_sgn (signature->r) == 0 || mpz_sgn (signature->s) == 0); +} diff --git a/ecdsa.h b/ecdsa.h index 693aca8b..7d590367 100644 --- a/ecdsa.h +++ b/ecdsa.h @@ -43,6 +43,7 @@ extern "C" {
/* Name mangling */ #define ecdsa_sign nettle_ecdsa_sign +#define ecdsa_sign_deterministic nettle_ecdsa_sign_deterministic #define ecdsa_verify nettle_ecdsa_verify #define ecdsa_generate_keypair nettle_ecdsa_generate_keypair #define ecc_ecdsa_sign nettle_ecc_ecdsa_sign @@ -61,6 +62,16 @@ ecdsa_sign (const struct ecc_scalar *key, const uint8_t *digest, struct dsa_signature *signature);
+void +ecdsa_sign_deterministic (const struct ecc_scalar *key, + 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, + struct dsa_signature *signature); + int ecdsa_verify (const struct ecc_point *pub, size_t length, const uint8_t *digest, diff --git a/testsuite/.gitignore b/testsuite/.gitignore index 6adde730..10fbbbc0 100644 --- a/testsuite/.gitignore +++ b/testsuite/.gitignore @@ -36,6 +36,7 @@ /ecc-sqrt-test /ecdh-test /ecdsa-keygen-test +/ecdsa-sign-deterministic-test /ecdsa-sign-test /ecdsa-verify-test /ed25519-test diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make index c3a5bb85..463c10d0 100644 --- a/testsuite/.test-rules.make +++ b/testsuite/.test-rules.make @@ -280,6 +280,9 @@ ed25519-test$(EXEEXT): ed25519-test.$(OBJEXT) dsa-compute-k-test$(EXEEXT): dsa-compute-k-test.$(OBJEXT) $(LINK) dsa-compute-k-test.$(OBJEXT) $(TEST_OBJS) -o dsa-compute-k-test$(EXEEXT)
+ecdsa-sign-deterministic-test$(EXEEXT): ecdsa-sign-deterministic-test.$(OBJEXT) + $(LINK) ecdsa-sign-deterministic-test.$(OBJEXT) $(TEST_OBJS) -o ecdsa-sign-deterministic-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 3bc22057..83807d42 100644 --- a/testsuite/Makefile.in +++ b/testsuite/Makefile.in @@ -53,7 +53,8 @@ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \ ecdsa-keygen-test.c ecdh-test.c \ eddsa-compress-test.c eddsa-sign-test.c \ eddsa-verify-test.c ed25519-test.c \ - dsa-compute-k-test.c + dsa-compute-k-test.c \ + ecdsa-sign-deterministic-test.c
TS_SOURCES = $(TS_NETTLE_SOURCES) $(TS_HOGWEED_SOURCES) CXX_SOURCES = cxx-test.cxx diff --git a/testsuite/ecdsa-sign-deterministic-test.c b/testsuite/ecdsa-sign-deterministic-test.c new file mode 100644 index 00000000..37b82217 --- /dev/null +++ b/testsuite/ecdsa-sign-deterministic-test.c @@ -0,0 +1,164 @@ +#include "testutils.h" +#include "hmac.h" +#include "nettle-internal.h" + +static void +test_ecdsa (const struct ecc_curve *ecc, + /* Private key */ + const char *sz, + /* 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 signature */ + const char *r, const char *s) +{ + struct ecc_scalar key; + struct dsa_signature ref; + struct dsa_signature signature; + mpz_t z; + + dsa_signature_init (&ref); + dsa_signature_init (&signature); + + mpz_init_set_str (z, sz, 16); + + ecc_scalar_init (&key, ecc); + ecc_scalar_set (&key, z); + + ecdsa_sign_deterministic (&key, + mac_ctx, set_key, update, digest, + h->length, h->data, &signature); + + mpz_set_str (ref.r, r, 16); + mpz_set_str (ref.s, s, 16); + + if (mpz_limbs_cmp (ref.r, mpz_limbs_read (signature.r), ecc->p.size) != 0 + || mpz_limbs_cmp (ref.s, mpz_limbs_read (signature.s), ecc->p.size) != 0) + { + fprintf (stderr, "_ecdsa_sign failed, bit_size = %u\n", ecc->p.bit_size); + fprintf (stderr, "r = "); + write_mpn (stderr, 16, mpz_limbs_read (signature.r), ecc->p.size); + fprintf (stderr, "\ns = "); + write_mpn (stderr, 16, mpz_limbs_read (signature.s), ecc->p.size); + fprintf (stderr, "\nref.r = "); + mpz_out_str (stderr, 16, ref.r); + fprintf (stderr, "\nref.s = "); + mpz_out_str (stderr, 16, ref.s); + fprintf (stderr, "\n"); + abort(); + } + + dsa_signature_clear (&ref); + dsa_signature_clear (&signature); + ecc_scalar_clear (&key); + mpz_clear (z); +} + +void +test_main (void) +{ + struct hmac_sha256_ctx hmac_sha256; + struct sha256_ctx hash_sha256; + uint8_t digest[NETTLE_MAX_HASH_DIGEST_SIZE]; + + sha256_init (&hash_sha256); + sha256_update (&hash_sha256, 6, (const uint8_t *)"sample"); + sha256_digest (&hash_sha256, SHA256_DIGEST_SIZE, digest); + + test_ecdsa (&_nettle_secp_192r1, + "6fab034934e4c0fc9ae67f5b5659a9d7" + "d1fefd187ee09fd4", /* z */ + + &hmac_sha256, + (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), /* h */ + + "4b0b8ce98a92866a2820e20aa6b75b56" + "382e0f9bfd5ecb55", /* r */ + + "ccdb006926ea9565cbadc840829d8c38" + "4e06de1f1e381b85"); /* s */ + + test_ecdsa (&_nettle_secp_224r1, + "f220266e1105bfe3083e03ec7a3a6546" + "51f45e37167e88600bf257c1", /* z */ + + &hmac_sha256, + (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), /* h */ + + "61aa3da010e8e8406c656bc477a7a718" + "9895e7e840cdfe8ff42307ba", /* r */ + + "bc814050dab5d23770879494f9e0a680" + "dc1af7161991bde692b10101"); /* s */ + + test_ecdsa (&_nettle_secp_256r1, + "c9afa9d845ba75166b5c215767b1d693" + "4e50c3db36e89b127b8a622b120f6721", /* z */ + + &hmac_sha256, + (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), /* h */ + + "efd48b2aacb6a8fd1140dd9cd45e81d6" + "9d2c877b56aaf991c34d0ea84eaf3716", /* r */ + + "f7cb1c942d657c41d436c7a1b6e29f65" + "f3e900dbb9aff4064dc4ab2f843acda8"); /* s */ + + test_ecdsa (&_nettle_secp_384r1, + "6b9d3dad2e1b8c1c05b19875b6659f4d" + "e23c3b667bf297ba9aa47740787137d8" + "96d5724e4c70a825f872c9ea60d2edf5", /* z */ + + &hmac_sha256, + (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), /* h */ + + "21b13d1e013c7fa1392d03c5f99af8b3" + "0c570c6f98d4ea8e354b63a21d3daa33" + "bde1e888e63355d92fa2b3c36d8fb2cd", /* r */ + + "f3aa443fb107745bf4bd77cb38916746" + "32068a10ca67e3d45db2266fa7d1feeb" + "efdc63eccd1ac42ec0cb8668a4fa0ab0"); /* s */ + + test_ecdsa (&_nettle_secp_521r1, + "0fad06daa62ba3b25d2fb40133da7572" + "05de67f5bb0018fee8c86e1b68c7e75c" + "aa896eb32f1f47c70855836a6d16fcc1" + "466f6d8fbec67db89ec0c08b0e996b83" + "538", /* z */ + + &hmac_sha256, + (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), /* h */ + + "1511bb4d675114fe266fc4372b87682b" + "aecc01d3cc62cf2303c92b3526012659" + "d16876e25c7c1e57648f23b73564d67f" + "61c6f14d527d54972810421e7d87589e" + "1a7", /* r */ + + "04a171143a83163d6df460aaf6152269" + "5f207a58b95c0644d87e52aa1a347916" + "e4f7a72930b1bc06dbe22ce3f58264af" + "d23704cbb63b29b931f7de6c9d949a7e" + "cfc"); /* s */ + +}