From 77fdf13a3806b30dd8c2caac23ce5c160904bac9 Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Fri, 6 Sep 2013 10:46:54 +0100 Subject: [PATCH] gdsa: Generate nonces more securely. Hash the private key and message, together with some random stuff. This ought to be hard to guess even if the randomness is bad. --- pub/dsa-misc.c | 47 +++++++++++++++++++++++++++++++++++++++++++++++ pub/dsa.h | 18 ++++++++++++++++++ pub/gdsa.c | 26 ++++++++++++++++++++++++-- pub/gkcdsa.c | 31 ++++++++++++++++++++++++++++--- pub/t/gkcdsa | 7 +++++++ 5 files changed, 124 insertions(+), 5 deletions(-) diff --git a/pub/dsa-misc.c b/pub/dsa-misc.c index 4d8bc2aa..4f68c7bc 100644 --- a/pub/dsa-misc.c +++ b/pub/dsa-misc.c @@ -61,4 +61,51 @@ mp *dsa_h2n(mp *d, mp *r, const void *h, size_t hsz) return (d); } +/* --- @dsa_nonce@ --- * + * + * Arguments: @mp *d@ = destination integer + * @mp *q@ = order of the DSA group + * @mp *x@ = secret key + * @const octet *m@ = message hash + * @const gchash *h@ = hash class + * @grand *r@ = random bit source, or null + * + * Returns: A nonce. + * + * Use: Generates a nonce for use in DSA (or another Fiat--Shamir + * signature scheme). + */ + +mp *dsa_nonce(mp *d, mp *q, mp *x, const octet *m, + const gchash *ch, grand *r) +{ + uint32 i = 0; + size_t nb = mp_bits(q), n = (nb + 7)/8, j; + size_t bsz = 2*n + 2*ch->hashsz; + octet *b = XS_ALLOC(bsz); + octet *kb = b, *rb = kb + n, *hb = rb + ch->hashsz; + ghash *h; + + mp_storeb(x, kb, n); + if (r) grand_fill(r, rb, ch->hashsz); + + do { + for (j = 0; j < n; j += ch->hashsz) { + h = GH_INIT(ch); + GH_HASHBUF32(h, kb, n); + GH_HASHBUF32(h, m, ch->hashsz); + if (r) GH_HASHBUF32(h, rb, ch->hashsz); + GH_HASHU32(h, i); + GH_DONE(h, hb + j); + GH_DESTROY(h); + i++; + } + d = mp_loadb(d, hb, n); + d = mp_lsr(d, d, 8*n - nb); + } while (MP_CMP(d, >=, q)); + + memset(b, 0, bsz); XS_FREE(b); + return (d); +} + /*----- That's all, folks -------------------------------------------------*/ diff --git a/pub/dsa.h b/pub/dsa.h index 3b93d933..97046fde 100644 --- a/pub/dsa.h +++ b/pub/dsa.h @@ -190,6 +190,24 @@ extern int dsa_checkparam(keycheck */*kc*/, const dsa_param */*dp*/, extern mp *dsa_h2n(mp */*d*/, mp */*r*/, const void */*h*/, size_t /*hsz*/); +/* --- @dsa_nonce@ --- * + * + * Arguments: @mp *d@ = destination integer + * @mp *q@ = order of the DSA group + * @mp *x@ = secret key + * @const octet *m@ = message hash + * @const gchash *h@ = hash class + * @grand *r@ = random bit source, or null + * + * Returns: A nonce. + * + * Use: Generates a nonce for use in DSA (or another Fiat--Shamir + * signature scheme). + */ + +extern mp *dsa_nonce(mp */*d*/, mp */*q*/, mp */*x*/, const octet */*m*/, + const gchash */*ch*/, grand */*r*/); + /* --- @dsa_mksig@ --- * * * Arguments: @const dsa_param *dp@ = pointer to DSA parameters diff --git a/pub/gdsa.c b/pub/gdsa.c index 6b985ded..92084d06 100644 --- a/pub/gdsa.c +++ b/pub/gdsa.c @@ -85,7 +85,7 @@ void gdsa_sign(const gdsa *c, gdsa_sig *s, const void *m, mp *k) if (k) { MP_COPY(k); goto have_k; } new_k: - k = mprand_range(k, g->r, c->r, 0); + k = dsa_nonce(k, g->r, c->u, m, c->h, c->r); have_k: if (MP_ZEROP(k)) goto new_k; G_EXP(g, z, g->g, k); @@ -142,6 +142,8 @@ done: #ifdef TEST_RIG +#include "rand.h" + static group *getgroup(const char *p) { group *g; qd_parse qd; qd.p = p; qd.e = 0; g = group_parse(&qd); @@ -178,12 +180,14 @@ static int tsign(dstr *v) gdsa c; gdsa_sig s, ss = GDSA_SIG_INIT; ghash *h; + octet *m; mp *k; int ok = 1; c.g = getgroup(v[0].buf); c.h = ghash_byname(v[1].buf); c.u = *(mp **)v[2].buf; k = *(mp **)v[4].buf; s.r = *(mp **)v[5].buf; s.s = *(mp **)v[6].buf; + c.p = G_CREATE(c.g); G_EXP(c.g, c.p, c.g->g, c.u); h = gdsa_beginhash(&c); GH_HASH(h, v[3].buf, v[3].len); @@ -199,8 +203,26 @@ static int tsign(dstr *v) showmp("computed r", ss.r, 16); showmp("computed s", ss.s, 16); showmp("expected r", s.r, 16); showmp("expected s", s.s, 16); } + + c.r = &rand_global; + h = gdsa_beginhash(&c); + GH_HASH(h, v[3].buf, v[3].len); + m = GH_DONE(h, 0); + GH_DESTROY(h); + gdsa_sign(&c, &ss, m, 0); + if (gdsa_verify(&c, &ss, m)) { + ok = 0; + fprintf(stderr, "*** sign cross-check failed!\n"); + fprintf(stderr, "*** group: %s\n", v[0].buf); + fprintf(stderr, "*** hash: %s\n", c.h->name); + showmp("private key", c.u, 16); + showge(c.g, "public key", c.p); + fprintf(stderr, "*** message: `%s'\n", v[3].buf); + showmp("computed r", ss.r, 16); showmp("computed s", ss.s, 16); + } + mp_drop(s.r); mp_drop(s.s); mp_drop(ss.r); mp_drop(ss.s); - mp_drop(k); mp_drop(c.u); G_DESTROYGROUP(c.g); GH_DESTROY(h); + mp_drop(k); mp_drop(c.u); G_DESTROY(c.g, c.p); G_DESTROYGROUP(c.g); assert(mparena_count(MPARENA_GLOBAL) == 0); return (ok); } diff --git a/pub/gkcdsa.c b/pub/gkcdsa.c index 99883c4c..94f22aa0 100644 --- a/pub/gkcdsa.c +++ b/pub/gkcdsa.c @@ -27,6 +27,7 @@ /*----- Header files ------------------------------------------------------*/ +#include "dsa.h" #include "gkcdsa.h" #include "group.h" #include "ghash.h" @@ -125,7 +126,7 @@ void gkcdsa_sign(const gkcdsa *c, gkcdsa_sig *s, const void *m, mp *k) if (k) { MP_COPY(k); goto have_k; } new_k: - k = mprand_range(k, g->r, c->r, 0); + k = dsa_nonce(k, g->r, c->u, m, c->h, c->r); have_k: if (MP_ZEROP(k)) goto new_k; G_EXP(g, z, g->g, k); @@ -183,6 +184,8 @@ int gkcdsa_verify(const gkcdsa *c, const gkcdsa_sig *s, const void *m) #ifdef TEST_RIG +#include "rand.h" + static group *getgroup(const char *p) { group *g; qd_parse qd; qd.p = p; qd.e = 0; g = group_parse(&qd); @@ -219,6 +222,7 @@ static int tsign(dstr *v) gdsa c; gkcdsa_sig s, ss = GKCDSA_SIG_INIT; ghash *h; + octet *m; mp *k; dstr d = DSTR_INIT; mp *x; @@ -236,6 +240,7 @@ static int tsign(dstr *v) GH_HASH(h, v[3].buf, v[3].len); gkcdsa_endhash(&c, h); gkcdsa_sign(&c, &ss, GH_DONE(h, 0), k); + GH_DESTROY(h); if (memcmp(s.r, ss.r, c.h->hashsz) || !MP_EQ(s.s, ss.s)) { ok = 0; fprintf(stderr, "*** sign failed!\n"); @@ -251,8 +256,28 @@ static int tsign(dstr *v) type_hex.dump(&v[5], stderr); putc('\n', stderr); showmp("expected s", s.s, 16); } - mp_drop(s.s); dstr_destroy(&d); mp_drop(ss.s); mp_drop(x); mp_drop(k); - mp_drop(c.u); G_DESTROY(c.g, c.p); G_DESTROYGROUP(c.g); GH_DESTROY(h); + + c.r = &rand_global; + h = gkcdsa_beginhash(&c); + GH_HASH(h, v[3].buf, v[3].len); + m = GH_DONE(h, 0); + GH_DESTROY(h); + gkcdsa_sign(&c, &ss, m, 0); + if (gkcdsa_verify(&c, &ss, m)) { + ok = 0; + fprintf(stderr, "*** sign cross-check failed!\n"); + fprintf(stderr, "*** group: %s\n", v[0].buf); + fprintf(stderr, "*** hash: %s\n", c.h->name); + showmp("private key", c.u, 16); + showge(c.g, "public key", c.p); + fprintf(stderr, "*** message: `%s'\n", v[3].buf); + fprintf(stderr, "*** computed r = "); + type_hex.dump(&d, stderr); putc('\n', stderr); + showmp("computed s", ss.s, 16); + } + + mp_drop(s.s); mp_drop(x); mp_drop(k); dstr_destroy(&d); mp_drop(ss.s); + mp_drop(c.u); G_DESTROY(c.g, c.p); G_DESTROYGROUP(c.g); assert(mparena_count(MPARENA_GLOBAL) == 0); return (ok); } diff --git a/pub/t/gkcdsa b/pub/t/gkcdsa index 29f47cfc..06a4df99 100644 --- a/pub/t/gkcdsa +++ b/pub/t/gkcdsa @@ -19,6 +19,13 @@ sign { 0x8d68905434b020ccb849e17a03a5c441d2a104aaf523699c1cc7a93174d21d9c e3f05cea444ec44d508b3af5b8d2d8eb2bcbff680e83684e3e630ec5b07393c0 0x42e307f5fa0a4e01906b067965f6253f1a7919a566cf3d73ddd9a35a17b38617; + + "ec { nist-p256 }" sha + 0x7fb838a8a0a95046b9d9d9fb4440f7bbc1a7bd3b4e853fc92d4e1588719986aa + "Testing nonce generation when hash and group size don't match" + 0x8d68905434b020ccb849e17a03a5c441d2a104aaf523699c1cc7a93174d21d9c + 02212cfc321f8c7b4913f17a6c6e0e9dd95a1671 + 0xef6191b5eaa50fc9f9b0b4b12bbad3af34588ab0a125bc3abc226c089c9a475f; } verify { -- 2.11.0