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 | 74 +++++++ ecdsa.h | 11 ++ testsuite/.gitignore | 1 + testsuite/.test-rules.make | 3 + testsuite/Makefile.in | 3 +- testsuite/ecdsa-sign-deterministic-test.c | 230 ++++++++++++++++++++++ 7 files changed, 322 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 36b2a182..27cbf93f 100644 --- a/Makefile.in +++ b/Makefile.in @@ -188,7 +188,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..11eef5f6 --- /dev/null +++ b/ecdsa-sign-deterministic.c @@ -0,0 +1,74 @@ +/* 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)); + + _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); + + assert (!(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 40fbe046..fb2800e8 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 61080010..8f796efd 100644 --- a/testsuite/.test-rules.make +++ b/testsuite/.test-rules.make @@ -283,6 +283,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 e6acd788..8bdb8ea6 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..6e5e441e --- /dev/null +++ b/testsuite/ecdsa-sign-deterministic-test.c @@ -0,0 +1,230 @@ +#include "testutils.h" +#include "hmac.h" +#include "nettle-internal.h" + +/* This is a identical to struct nettle_mac defined in testutils.h, + * except that set_key is defined as a different type. */ +struct nettle_hmac +{ + const char *name; + + /* Size of the context struct */ + unsigned context_size; + + /* Size of digests */ + unsigned digest_size; + + /* Suggested key size; other sizes are sometimes possible. */ + unsigned key_size; + + /* HMAC require an additional key_length argument to set_key, which + * makes the type incompatible with nettle_set_key_func. */ + nettle_hash_update_func *set_key; + nettle_hash_update_func *update; + nettle_hash_digest_func *digest; +}; + +#undef _NETTLE_HMAC +#define _NETTLE_HMAC(name, NAME) { \ + #name, \ + sizeof(struct hmac_##name##_ctx), \ + NAME##_DIGEST_SIZE, \ + NAME##_DIGEST_SIZE, \ + (nettle_hash_update_func *)hmac_##name##_set_key, \ + (nettle_hash_update_func *)hmac_##name##_update, \ + (nettle_hash_digest_func *)hmac_##name##_digest, \ +} + +static void +test_ecdsa (const struct ecc_curve *ecc, + /* Private key */ + const char *sz, + /* HMAC */ + void *hmac_ctx, + const struct nettle_hmac *hmac, + /* 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, + hmac_ctx, + hmac->set_key, + hmac->update, + hmac->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, hmac_%s\n", + ecc->p.bit_size, hmac->name); + 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); +} + +static const struct nettle_hmac hmac_sha1 = _NETTLE_HMAC(sha1, SHA1); +static const struct nettle_hmac hmac_sha224 = _NETTLE_HMAC(sha224, SHA224); +static const struct nettle_hmac hmac_sha256 = _NETTLE_HMAC(sha256, SHA256); +static const struct nettle_hmac hmac_sha384 = _NETTLE_HMAC(sha384, SHA384); +static const struct nettle_hmac hmac_sha512 = _NETTLE_HMAC(sha512, SHA512); + +static struct +{ + const struct ecc_curve *ecc; + const struct nettle_hash *hash; + const struct nettle_hmac *hmac; + const char *m; + const char *z; + const char *r; + const char *s; +} tests[] = { + /* Test vectors from RFC6979 */ + { &_nettle_secp_192r1, &nettle_sha1, &hmac_sha1, + "sample", + "6fab034934e4c0fc9ae67f5b5659a9d7d1fefd187ee09fd4", + "98C6BD12B23EAF5E2A2045132086BE3EB8EBD62ABF6698FF", + "57A22B07DEA9530F8DE9471B1DC6624472E8E2844BC25B64" }, + { &_nettle_secp_192r1, &nettle_sha224, &hmac_sha224, + "sample", + "6fab034934e4c0fc9ae67f5b5659a9d7d1fefd187ee09fd4", + "a1f00dad97aeec91c95585f36200c65f3c01812aa60378f5", + "e07ec1304c7c6c9debbe980b9692668f81d4de7922a0f97a" }, + { &_nettle_secp_192r1, &nettle_sha256, &hmac_sha256, + "sample", + "6fab034934e4c0fc9ae67f5b5659a9d7d1fefd187ee09fd4", + "4b0b8ce98a92866a2820e20aa6b75b56382e0f9bfd5ecb55", + "ccdb006926ea9565cbadc840829d8c384e06de1f1e381b85" }, + { &_nettle_secp_192r1, &nettle_sha384, &hmac_sha384, + "sample", + "6fab034934e4c0fc9ae67f5b5659a9d7d1fefd187ee09fd4", + "da63bf0b9abcf948fbb1e9167f136145f7a20426dcc287d5", + "c3aa2c960972bd7a2003a57e1c4c77f0578f8ae95e31ec5e" }, + { &_nettle_secp_192r1, &nettle_sha512, &hmac_sha512, + "sample", + "6fab034934e4c0fc9ae67f5b5659a9d7d1fefd187ee09fd4", + "4d60c5ab1996bd848343b31c00850205e2ea6922dac2e4b8", + "3f6e837448f027a1bf4b34e796e32a811cbb4050908d8f67" }, + { &_nettle_secp_224r1, &nettle_sha1, &hmac_sha1, + "sample", + "f220266e1105bfe3083e03ec7a3a654651f45e37167e88600bf257c1", + "22226f9d40a96e19c4a301ce5b74b115303c0f3a4fd30fc257fb57ac", + "66d1cdd83e3af75605dd6e2feff196d30aa7ed7a2edf7af475403d69" }, + { &_nettle_secp_224r1, &nettle_sha224, &hmac_sha224, + "sample", + "f220266e1105bfe3083e03ec7a3a654651f45e37167e88600bf257c1", + "1cdfe6662dde1e4a1ec4cdedf6a1f5a2fb7fbd9145c12113e6abfd3e", + "a6694fd7718a21053f225d3f46197ca699d45006c06f871808f43ebc" }, + { &_nettle_secp_224r1, &nettle_sha256, &hmac_sha256, + "sample", + "f220266e1105bfe3083e03ec7a3a654651f45e37167e88600bf257c1", + "61aa3da010e8e8406c656bc477a7a7189895e7e840cdfe8ff42307ba", + "bc814050dab5d23770879494f9e0a680dc1af7161991bde692b10101" }, + { &_nettle_secp_224r1, &nettle_sha384, &hmac_sha384, + "sample", + "f220266e1105bfe3083e03ec7a3a654651f45e37167e88600bf257c1", + "0b115e5e36f0f9ec81f1325a5952878d745e19d7bb3eabfaba77e953", + "830f34ccdfe826ccfdc81eb4129772e20e122348a2bbd889a1b1af1d" }, + { &_nettle_secp_224r1, &nettle_sha512, &hmac_sha512, + "sample", + "f220266e1105bfe3083e03ec7a3a654651f45e37167e88600bf257c1", + "074bd1d979d5f32bf958ddc61e4fb4872adcafeb2256497cdac30397", + "a4ceca196c3d5a1ff31027b33185dc8ee43f288b21ab342e5d8eb084" }, + { &_nettle_secp_256r1, &nettle_sha1, &hmac_sha1, + "sample", + "c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721", + "61340c88c3aaebeb4f6d667f672ca9759a6ccaa9fa8811313039ee4a35471d32", + "6d7f147dac089441bb2e2fe8f7a3fa264b9c475098fdcf6e00d7c996e1b8b7eb" }, + { &_nettle_secp_256r1, &nettle_sha224, &hmac_sha224, + "sample", + "c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721", + "53b2fff5d1752b2c689df257c04c40a587fababb3f6fc2702f1343af7ca9aa3f", + "b9afb64fdc03dc1a131c7d2386d11e349f070aa432a4acc918bea988bf75c74c" }, + { &_nettle_secp_256r1, &nettle_sha256, &hmac_sha256, + "sample", + "c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721", + "efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716", + "f7cb1c942d657c41d436c7a1b6e29f65f3e900dbb9aff4064dc4ab2f843acda8" }, + { &_nettle_secp_256r1, &nettle_sha512, &hmac_sha512, + "sample", + "c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721", + "8496a60b5e9b47c825488827e0495b0e3fa109ec4568fd3f8d1097678eb97f00", + "2362ab1adbe2b8adf9cb9edab740ea6049c028114f2460f96554f61fae3302fe" }, + { &_nettle_secp_384r1, &nettle_sha256, &hmac_sha256, + "sample", + "6b9d3dad2e1b8c1c05b19875b6659f4de23c3b667bf297ba9aa47740787137d8" + "96d5724e4c70a825f872c9ea60d2edf5", + "21b13d1e013c7fa1392d03c5f99af8b30c570c6f98d4ea8e354b63a21d3daa33" + "bde1e888e63355d92fa2b3c36d8fb2cd", + "f3aa443fb107745bf4bd77cb3891674632068a10ca67e3d45db2266fa7d1feeb" + "efdc63eccd1ac42ec0cb8668a4fa0ab0" }, + { &_nettle_secp_521r1, &nettle_sha256, &hmac_sha256, + "sample", + "0fad06daa62ba3b25d2fb40133da757205de67f5bb0018fee8c86e1b68c7e75c" + "aa896eb32f1f47c70855836a6d16fcc1466f6d8fbec67db89ec0c08b0e996b83" + "538", + "1511bb4d675114fe266fc4372b87682baecc01d3cc62cf2303c92b3526012659" + "d16876e25c7c1e57648f23b73564d67f61c6f14d527d54972810421e7d87589e" + "1a7", + "04a171143a83163d6df460aaf61522695f207a58b95c0644d87e52aa1a347916" + "e4f7a72930b1bc06dbe22ce3f58264afd23704cbb63b29b931f7de6c9d949a7e" + "cfc" } +}; + +void +test_main (void) +{ + size_t i; + + for (i = 0; i < sizeof(tests) / sizeof(*tests); i++) + { + void *hash_ctx; + uint8_t digest[NETTLE_MAX_HASH_DIGEST_SIZE]; + void *hmac_ctx; + + hash_ctx = xalloc (tests[i].hash->context_size); + tests[i].hash->init (hash_ctx); + tests[i].hash->update (hash_ctx, 6, (const uint8_t *)tests[i].m); + tests[i].hash->digest (hash_ctx, tests[i].hash->digest_size, digest); + + hmac_ctx = xalloc (tests[i].hmac->context_size); + test_ecdsa (tests[i].ecc, + tests[i].z, + hmac_ctx, + tests[i].hmac, + tstring_data (tests[i].hash->digest_size, digest), + tests[i].r, + tests[i].s); + free (hmac_ctx); + } +}