ecc: Fix a minor flaw in the generation of K.

* cipher/dsa.c (gen_k): Factor code out to ..
* cipher/dsa-common.c (_gcry_dsa_gen_k): new file and function.  Add
arg security_level and re-indent a bit.
* cipher/ecc.c (gen_k): Remove and change callers to _gcry_dsa_gen_k.
* cipher/dsa.c: Include pubkey-internal.
* cipher/Makefile.am (libcipher_la_SOURCES): Add dsa-common.c
--

The ECDSA code used the simple $k = k \bmod p$ method which introduces
a small bias.  We now use the bias free method we have always used
with DSA.

Signed-off-by: Werner Koch <wk@gnupg.org>

5 files changed, 117 insertions, 104 deletions

diff --git a/cipher/Makefile.am b/cipher/Makefile.am
index 1e2696fb..687c5992 100644
--- a/cipher/Makefile.am
+++ b/cipher/Makefile.am
@@ -49,6 +49,7 @@ bithelp.h  \
 bufhelp.h  \
 primegen.c  \
 hash-common.c hash-common.h \
+dsa-common.c \
 rmd.h
 
 EXTRA_libcipher_la_SOURCES = \
diff --git a/cipher/dsa-common.c b/cipher/dsa-common.c
new file mode 100644
index 00000000..a5854ce7
--- /dev/null
+++ b/cipher/dsa-common.c
@@ -0,0 +1,101 @@
+/* dsa-common.c - Common code for DSA
+ * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+ * Copyright (C) 2013  g10 Code GmbH
+ *
+ * This file is part of Libgcrypt.
+ *
+ * Libgcrypt is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation; either version 2.1 of
+ * the License, or (at your option) any later version.
+ *
+ * Libgcrypt 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 Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <config.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "g10lib.h"
+#include "mpi.h"
+#include "cipher.h"
+#include "pubkey-internal.h"
+
+
+/*
+ * Generate a random secret exponent K less than Q.
+ * Note that ECDSA uses this code also to generate D.
+ */
+gcry_mpi_t
+_gcry_dsa_gen_k (gcry_mpi_t q, int security_level)
+{
+  gcry_mpi_t k        = mpi_alloc_secure (mpi_get_nlimbs (q));
+  unsigned int nbits  = mpi_get_nbits (q);
+  unsigned int nbytes = (nbits+7)/8;
+  char *rndbuf = NULL;
+
+  /* To learn why we don't use mpi_mod to get the requested bit size,
+     read the paper: "The Insecurity of the Digital Signature
+     Algorithm with Partially Known Nonces" by Nguyen and Shparlinski.
+     Journal of Cryptology, New York. Vol 15, nr 3 (2003)  */
+
+  if (DBG_CIPHER)
+    log_debug ("choosing a random k of %u bits at seclevel %d\n",
+               nbits, security_level);
+  for (;;)
+    {
+      if ( !rndbuf || nbits < 32 )
+        {
+          gcry_free (rndbuf);
+          rndbuf = gcry_random_bytes_secure (nbytes, security_level);
+	}
+      else
+        { /* Change only some of the higher bits.  We could improve
+	     this by directly requesting more memory at the first call
+	     to get_random_bytes() and use these extra bytes here.
+	     However the required management code is more complex and
+	     thus we better use this simple method.  */
+          char *pp = gcry_random_bytes_secure (4, security_level);
+          memcpy (rndbuf, pp, 4);
+          gcry_free (pp);
+	}
+      _gcry_mpi_set_buffer (k, rndbuf, nbytes, 0);
+
+      /* Make sure we have the requested number of bits.  This code
+         looks a bit funny but it is easy to understand if you
+         consider that mpi_set_highbit clears all higher bits.  We
+         don't have a clear_highbit, thus we first set the high bit
+         and then clear it again.  */
+      if (mpi_test_bit (k, nbits-1))
+        mpi_set_highbit (k, nbits-1);
+      else
+        {
+          mpi_set_highbit (k, nbits-1);
+          mpi_clear_bit (k, nbits-1);
+	}
+
+      if (!(mpi_cmp (k, q) < 0))    /* check: k < q */
+        {
+          if (DBG_CIPHER)
+            log_debug ("\tk too large - again");
+          continue; /* no  */
+        }
+      if (!(mpi_cmp_ui (k, 0) > 0)) /* check: k > 0 */
+        {
+          if (DBG_CIPHER)
+            log_debug ("\tk is zero - again");
+          continue; /* no */
+        }
+      break;	/* okay */
+    }
+  gcry_free (rndbuf);
+
+  return k;
+}
diff --git a/cipher/dsa.c b/cipher/dsa.c
index 883a815f..90edeb5a 100644
--- a/cipher/dsa.c
+++ b/cipher/dsa.c
@@ -26,6 +26,8 @@
 #include "g10lib.h"
 #include "mpi.h"
 #include "cipher.h"
+#include "pubkey-internal.h"
+
 
 typedef struct
 {
@@ -94,7 +96,6 @@ static const char sample_public_key[] =
 
 
 
-static gcry_mpi_t gen_k (gcry_mpi_t q);
 static int test_keys (DSA_secret_key *sk, unsigned int qbits);
 static int check_secret_key (DSA_secret_key *sk);
 static gpg_err_code_t generate (DSA_secret_key *sk,
@@ -130,81 +131,6 @@ progress (int c)
 }
 
 
-/*
- * Generate a random secret exponent k less than q.
- */
-static gcry_mpi_t
-gen_k( gcry_mpi_t q )
-{
-  gcry_mpi_t k = mpi_alloc_secure( mpi_get_nlimbs(q) );
-  unsigned int nbits = mpi_get_nbits(q);
-  unsigned int nbytes = (nbits+7)/8;
-  char *rndbuf = NULL;
-
-  /* To learn why we don't use mpi_mod to get the requested bit size,
-     read the paper: "The Insecurity of the Digital Signature
-     Algorithm with Partially Known Nonces" by Nguyen and Shparlinski.
-     Journal of Cryptology, New York. Vol 15, nr 3 (2003)  */
-
-  if ( DBG_CIPHER )
-    log_debug("choosing a random k ");
-  for (;;)
-    {
-      if( DBG_CIPHER )
-        progress('.');
-
-      if ( !rndbuf || nbits < 32 )
-        {
-          gcry_free(rndbuf);
-          rndbuf = gcry_random_bytes_secure( (nbits+7)/8, GCRY_STRONG_RANDOM );
-	}
-      else
-        { /* Change only some of the higher bits.  We could improve
-	     this by directly requesting more memory at the first call
-	     to get_random_bytes() and use these extra bytes here.
-	     However the required management code is more complex and
-	     thus we better use this simple method.  */
-          char *pp = gcry_random_bytes_secure( 4, GCRY_STRONG_RANDOM );
-          memcpy( rndbuf,pp, 4 );
-          gcry_free(pp);
-	}
-      _gcry_mpi_set_buffer( k, rndbuf, nbytes, 0 );
-
-      /* Make sure we have the requested number of bits.  This code
-         looks a bit funny but it is easy to understand if you
-         consider that mpi_set_highbit clears all higher bits.  We
-         don't have a clear_highbit, thus we first set the high bit
-         and then clear it again.  */
-      if ( mpi_test_bit( k, nbits-1 ) )
-        mpi_set_highbit( k, nbits-1 );
-      else
-        {
-          mpi_set_highbit( k, nbits-1 );
-          mpi_clear_bit( k, nbits-1 );
-	}
-
-      if( !(mpi_cmp( k, q ) < 0) ) /* check: k < q */
-        {
-          if( DBG_CIPHER )
-            progress('+');
-          continue; /* no  */
-        }
-      if( !(mpi_cmp_ui( k, 0 ) > 0) )  /* check: k > 0 */
-        {
-          if( DBG_CIPHER )
-            progress('-');
-          continue; /* no */
-        }
-      break;	/* okay */
-    }
-  gcry_free(rndbuf);
-  if( DBG_CIPHER )
-    progress('\n');
-
-  return k;
-}
-
-
 /* Check that a freshly generated key actually works.  Returns 0 on success. */
 static int
 test_keys (DSA_secret_key *sk, unsigned int qbits)
@@ -333,6 +259,13 @@ generate (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
 
   /* Select a random number X with the property:
    *	 0 < x < q-1
+   *
+   * FIXME: Why do we use the requirement x < q-1 ? It should be
+   * sufficient to test for x < q.  FIPS-186-3 check x < q-1 but it
+   * does not check for 0 < x because it makes sure that Q is unsigned
+   * and finally adds one to the result so that 0 will never be
+   * returned.  We should replace the code below with _gcry_dsa_gen_k.
+   *
    * This must be a very good random number because this is the secret
    * part.  The random quality depends on the transient_key flag.  */
   random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
@@ -613,7 +546,7 @@ sign(gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_secret_key *skey )
   gcry_mpi_t tmp;
 
   /* Select a random k with 0 < k < q */
-  k = gen_k( skey->q );
+  k = _gcry_dsa_gen_k (skey->q, GCRY_STRONG_RANDOM);
 
   /* r = (a^k mod p) mod q */
   gcry_mpi_powm( r, skey->g, k, skey->p );
diff --git a/cipher/ecc.c b/cipher/ecc.c
index ea1de3f6..63ee2d04 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -306,7 +306,6 @@ static void *progress_cb_data;
 
 
 /* Local prototypes. */
-static gcry_mpi_t gen_k (gcry_mpi_t p, int security_level);
 static void test_keys (ECC_secret_key * sk, unsigned int nbits);
 static int check_secret_key (ECC_secret_key * sk);
 static gpg_err_code_t sign (gcry_mpi_t input, ECC_secret_key *skey,
@@ -424,30 +423,6 @@ gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base)
 }
 
 
-/* Generate a random secret scalar k with an order of p
-
-   At the beginning this was identical to the code is in elgamal.c.
-   Later imporved by mmr.   Further simplified by wk.  */
-static gcry_mpi_t
-gen_k (gcry_mpi_t p, int security_level)
-{
-  gcry_mpi_t k;
-  unsigned int nbits;
-
-  nbits = mpi_get_nbits (p);
-  k = mpi_snew (nbits);
-  if (DBG_CIPHER)
-    log_debug ("choosing a random k of %u bits at seclevel %d\n",
-               nbits, security_level);
-
-  gcry_mpi_randomize (k, nbits, security_level);
-
-  mpi_mod (k, k, p);  /*  k = k mod p  */
-
-  return k;
-}
-
-
 /* Generate the crypto system setup.  This function takes the NAME of
    a curve or the desired number of bits and stores at R_CURVE the
    parameters of the named curve or those of a suitable curve.  If
@@ -554,7 +529,7 @@ generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
     }
 
   random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
-  d = gen_k (E.n, random_level);
+  d = _gcry_dsa_gen_k (E.n, random_level);
 
   /* Compute Q.  */
   point_init (&Q);
@@ -806,7 +781,7 @@ sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s)
              do_while because we want to keep the value of R even if S
              has to be recomputed.  */
           mpi_free (k);
-          k = gen_k (skey->E.n, GCRY_STRONG_RANDOM);
+          k = _gcry_dsa_gen_k (skey->E.n, GCRY_STRONG_RANDOM);
           _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
           if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
             {
diff --git a/cipher/pubkey-internal.h b/cipher/pubkey-internal.h
index 0ca17a50..ae7e77b0 100644
--- a/cipher/pubkey-internal.h
+++ b/cipher/pubkey-internal.h
@@ -20,6 +20,9 @@
 #ifndef GCRY_PUBKEY_INTERNAL_H
 #define GCRY_PUBKEY_INTERNAL_H
 
+/*-- dsa-common.h --*/
+gcry_mpi_t _gcry_dsa_gen_k (gcry_mpi_t q, int security_level);
+
 
 /*-- ecc.c --*/
 gpg_err_code_t _gcry_pk_ecc_get_sexp (gcry_sexp_t *r_sexp, int mode,