diff options
| -rw-r--r-- | ChangeLog | 15 | ||||
| -rw-r--r-- | ed25519-sha512-sign.c | 9 | ||||
| -rw-r--r-- | eddsa-hash.c | 34 | ||||
| -rw-r--r-- | eddsa-internal.h | 5 | ||||
| -rw-r--r-- | eddsa-pubkey.c | 3 | ||||
| -rw-r--r-- | eddsa-sign.c | 53 | ||||
| -rw-r--r-- | eddsa-verify.c | 3 | ||||
| -rw-r--r-- | testsuite/eddsa-sign-test.c | 5 |
8 files changed, 97 insertions, 30 deletions
@@ -2,6 +2,21 @@ * eddsa-internal.h (struct ecc_eddsa): Add magic "dom" string, needed for ed448. + * ed25519-sha512.c (_nettle_ed25519_sha512): Empty dom string. + * ed448-shake256.c (_nettle_ed448_shake256): New file and + parameter struct. + + * eddsa-hash.c (_eddsa_hash): Add digest_size as input argument. + Handle ed448 digests with two extra bytes. Update callers. + * eddsa-verify.c (_eddsa_verify): Hash dom string. + * eddsa-sign.c (_eddsa_sign_itch): Assert that + _eddsa_compress_itch isn't too large. + (_eddsa_sign): New argument k1, with the hash prefix. Add hashing + of this prefix and the dom string. Update callers. Fix final + reduction, it's different for ed25519, with q slightly larger than + a power of two, and ed448, with q slightly smaller. + * eddsa-pubkey.c (_eddsa_public_key_itch): Assert that + _eddsa_compress_itch isn't too large. 2020-01-01 Niels Möller <nisse@lysator.liu.se> diff --git a/ed25519-sha512-sign.c b/ed25519-sha512-sign.c index 0205e6f0..389a157e 100644 --- a/ed25519-sha512-sign.c +++ b/ed25519-sha512-sign.c @@ -52,14 +52,13 @@ ed25519_sha512_sign (const uint8_t *pub, #define scratch_out (scratch + ecc->q.size) struct sha512_ctx ctx; uint8_t digest[SHA512_DIGEST_SIZE]; -#define k1 (digest + ED25519_KEY_SIZE) + sha512_init (&ctx); _eddsa_expand_key (ecc, &_nettle_ed25519_sha512, &ctx, priv, digest, k2); - sha512_update (&ctx, ED25519_KEY_SIZE, k1); - _eddsa_sign (ecc, &_nettle_ed25519_sha512, pub, - &ctx, - k2, length, msg, signature, scratch_out); + _eddsa_sign (ecc, &_nettle_ed25519_sha512, &ctx, + pub, digest + ED25519_KEY_SIZE, k2, + length, msg, signature, scratch_out); gmp_free_limbs (scratch, itch); #undef k1 diff --git a/eddsa-hash.c b/eddsa-hash.c index 46f6ca34..e05f6ac1 100644 --- a/eddsa-hash.c +++ b/eddsa-hash.c @@ -1,6 +1,8 @@ /* eddsa-hash.c - Copyright (C) 2014 Niels Möller + Copyright (C) 2014, 2019 Niels Möller + Copyright (C) 2017 Daiki Ueno + Copyright (C) 2017 Red Hat, Inc. This file is part of GNU Nettle. @@ -42,11 +44,35 @@ #include "ecc-internal.h" #include "nettle-internal.h" +/* Convert hash digest to integer, and reduce modulo q, to m->size + limbs. Needs space for 2*m->size + 1 at rp. */ void _eddsa_hash (const struct ecc_modulo *m, - mp_limb_t *rp, const uint8_t *digest) + mp_limb_t *rp, size_t digest_size, const uint8_t *digest) { - size_t nbytes = 1 + m->bit_size / 8; - mpn_set_base256_le (rp, 2*m->size, digest, 2*nbytes); + mp_size_t nlimbs = (8*digest_size + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS; + + mpn_set_base256_le (rp, nlimbs, digest, digest_size); + + if (nlimbs > 2*m->size) + { + /* Special case for Ed448: reduce rp to 2*m->size limbs. + After decoding rp from a hash of size 2*rn: + + rp = r2 || r1 || r0 + + where r0 and r1 have m->size limbs. Reduce this to: + + rp = r1' || r0 + + where r1' has m->size limbs. */ + mp_limb_t hi = rp[2*m->size]; + assert (nlimbs == 2*m->size + 1); + + hi = mpn_addmul_1 (rp + m->size, m->B, m->size, hi); + assert (hi <= 1); + hi = cnd_add_n (hi, rp + m->size, m->B, m->size); + assert (hi == 0); + } m->mod (m, rp); } diff --git a/eddsa-internal.h b/eddsa-internal.h index 4dd441f0..ea4c5e34 100644 --- a/eddsa-internal.h +++ b/eddsa-internal.h @@ -82,7 +82,7 @@ _eddsa_decompress (const struct ecc_curve *ecc, mp_limb_t *p, void _eddsa_hash (const struct ecc_modulo *m, - mp_limb_t *rp, const uint8_t *digest); + mp_limb_t *rp, size_t digest_size, const uint8_t *digest); mp_size_t _eddsa_sign_itch (const struct ecc_curve *ecc); @@ -90,8 +90,9 @@ _eddsa_sign_itch (const struct ecc_curve *ecc); void _eddsa_sign (const struct ecc_curve *ecc, const struct ecc_eddsa *eddsa, - const uint8_t *pub, void *ctx, + const uint8_t *pub, + const uint8_t *k1, const mp_limb_t *k2, size_t length, const uint8_t *msg, diff --git a/eddsa-pubkey.c b/eddsa-pubkey.c index c952ad17..72726e56 100644 --- a/eddsa-pubkey.c +++ b/eddsa-pubkey.c @@ -33,6 +33,8 @@ # include "config.h" #endif +#include <assert.h> + #include "eddsa.h" #include "eddsa-internal.h" @@ -41,6 +43,7 @@ mp_size_t _eddsa_public_key_itch (const struct ecc_curve *ecc) { + assert (_eddsa_compress_itch (ecc) <= ecc->mul_g_itch); return 3*ecc->p.size + ecc->mul_g_itch; } diff --git a/eddsa-sign.c b/eddsa-sign.c index 5e39fe69..a5970e98 100644 --- a/eddsa-sign.c +++ b/eddsa-sign.c @@ -45,14 +45,16 @@ mp_size_t _eddsa_sign_itch (const struct ecc_curve *ecc) { + assert (_eddsa_compress_itch (ecc) <= ecc->mul_g_itch); return 5*ecc->p.size + ecc->mul_g_itch; } void _eddsa_sign (const struct ecc_curve *ecc, const struct ecc_eddsa *eddsa, - const uint8_t *pub, void *ctx, + const uint8_t *pub, + const uint8_t *k1, const mp_limb_t *k2, size_t length, const uint8_t *msg, @@ -61,6 +63,8 @@ _eddsa_sign (const struct ecc_curve *ecc, { mp_size_t size; size_t nbytes; + mp_limb_t q, cy; + #define rp scratch #define hp (scratch + size) #define P (scratch + 2*size) @@ -71,32 +75,51 @@ _eddsa_sign (const struct ecc_curve *ecc, size = ecc->p.size; nbytes = 1 + ecc->p.bit_size / 8; + eddsa->update (ctx, eddsa->dom_size, eddsa->dom); + eddsa->update (ctx, nbytes, k1); eddsa->update (ctx, length, msg); eddsa->digest (ctx, 2*nbytes, hash); - _eddsa_hash (&ecc->q, rp, hash); + _eddsa_hash (&ecc->q, rp, 2*nbytes, hash); + ecc->mul_g (ecc, P, rp, scratch_out); _eddsa_compress (ecc, signature, P, scratch_out); + eddsa->update (ctx, eddsa->dom_size, eddsa->dom); eddsa->update (ctx, nbytes, signature); eddsa->update (ctx, nbytes, pub); eddsa->update (ctx, length, msg); eddsa->digest (ctx, 2*nbytes, hash); - _eddsa_hash (&ecc->q, hp, hash); + _eddsa_hash (&ecc->q, hp, 2*nbytes, hash); ecc_modq_mul (ecc, sp, hp, k2); ecc_modq_add (ecc, sp, sp, rp); /* FIXME: Can be plain add */ - /* FIXME: Special code duplicated in ecc_25519_modq and ecc_eh_to_a. - Define a suitable method? */ - { - unsigned shift; - mp_limb_t cy; - assert (ecc->p.bit_size == 255); - shift = ecc->q.bit_size - 1 - GMP_NUMB_BITS * (ecc->p.size - 1); - cy = mpn_submul_1 (sp, ecc->q.m, ecc->p.size, - sp[ecc->p.size-1] >> shift); - assert (cy < 2); - cnd_add_n (cy, sp, ecc->q.m, ecc->p.size); - } + if (ecc->p.bit_size == 255) + { + /* FIXME: Special code duplicated in ecc_25519_modq + Define a suitable method for canonical reduction? */ + + /* q is slightly larger than 2^252, underflow from below + mpn_submul_1 is unlikely. */ + unsigned shift = 252 - GMP_NUMB_BITS * (ecc->p.size - 1); + q = sp[ecc->p.size-1] >> shift; + } + else + { + unsigned shift; + + assert (ecc->p.bit_size == 448); + /* q is slightly smaller than 2^446 */ + shift = 446 - GMP_NUMB_BITS * (ecc->p.size - 1); + /* Add one, then it's possible but unlikely that below + mpn_submul_1 does *not* underflow. */ + q = (sp[ecc->p.size-1] >> shift) + 1; + } + + cy = mpn_submul_1 (sp, ecc->q.m, ecc->p.size, q); + assert (cy < 2); + cy -= cnd_add_n (cy, sp, ecc->q.m, ecc->p.size); + assert (cy == 0); + mpn_get_base256_le (signature + nbytes, nbytes, sp, ecc->q.size); #undef rp #undef hp diff --git a/eddsa-verify.c b/eddsa-verify.c index e482c9b9..c4e65d69 100644 --- a/eddsa-verify.c +++ b/eddsa-verify.c @@ -106,11 +106,12 @@ _eddsa_verify (const struct ecc_curve *ecc, if (mpn_cmp (sp, ecc->q.m, ecc->q.size) >= 0) return 0; + eddsa->update (ctx, eddsa->dom_size, eddsa->dom); eddsa->update (ctx, nbytes, signature); eddsa->update (ctx, nbytes, pub); eddsa->update (ctx, length, msg); eddsa->digest (ctx, 2*nbytes, hash); - _eddsa_hash (&ecc->q, hp, hash); + _eddsa_hash (&ecc->q, hp, 2*nbytes, hash); /* Compute h A + R - s G, which should be the neutral point */ ecc->mul (ecc, P, hp, A, scratch_out); diff --git a/testsuite/eddsa-sign-test.c b/testsuite/eddsa-sign-test.c index 4cfc4dbb..47ca6e76 100644 --- a/testsuite/eddsa-sign-test.c +++ b/testsuite/eddsa-sign-test.c @@ -69,9 +69,8 @@ test_eddsa_sign (const struct ecc_curve *ecc, fprintf (stderr, "\n"); abort (); } - eddsa->update (ctx, nbytes, k1); - - _eddsa_sign (ecc, eddsa, public->data, ctx, k2, + _eddsa_sign (ecc, eddsa, ctx, + public->data, k1, k2, msg->length, msg->data, signature, scratch); if (!MEMEQ (2*nbytes, signature, ref->data)) |