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.

diff --git a/pub/dsa-misc.c b/pub/dsa-misc.c
index 4d8bc2aac463101b250e0d58c77798245056086a..4f68c7bcd9172a350468317a52996fc8959d4e7a 100644 (file)
--- 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 3b93d9338774e6434d96ac4bb104cd91bc60d684..97046fde578198a814d1baa015cc541f3e4f511b 100644 (file)
--- 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 6b985ded8ffa2e8f0b249a9c474d96a8b10c6ca5..92084d069e5617f33d2d00323ff94c50492f1b77 100644 (file)
--- 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 99883c4ce98c93f0b6cd8f7864c933a70da4829f..94f22aa0cd27f57289fd204602879bc13e890033 100644 (file)
--- 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 29f47cfc9fc3e2f940fc5919a5ee53918f350bb4..06a4df9997e607b95de3735d55f8e4f0bcc1797f 100644 (file)
--- 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 {