Prepare for FIPS186-3.
authorWerner Koch <wk@gnupg.org>
Wed, 26 Nov 2008 11:59:14 +0000 (11:59 +0000)
committerWerner Koch <wk@gnupg.org>
Wed, 26 Nov 2008 11:59:14 +0000 (11:59 +0000)
cipher/ChangeLog
cipher/dsa.c
cipher/primegen.c
doc/gcrypt.texi
src/g10lib.h

index db149c2..86a2d52 100644 (file)
@@ -1,3 +1,9 @@
+2008-11-26  Werner Koch  <wk@g10code.com>
+
+       * primegen.c (_gcry_generate_fips186_3_prime): New.
+       * dsa.c (generate_fips186): Add arg USE_FIPS186_2.
+       (dsa_generate_ext): Parse new flag use-fips183-2.
+
 2008-11-25  Werner Koch  <wk@g10code.com>
 
        * dsa.c (generate_fips186): New.
index cda4e52..8e68793 100644 (file)
@@ -355,11 +355,12 @@ generate (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
 
 
 /* Generate a DSA key pair with a key of size NBITS using the
-   algorithm given in FIPS-186.  At the time of implementation FIPS
-   186-3 was not released; the Draft from November 2008 was used
-   instead to avoid limiting ourself to FIPS 186-2.  */
+   algorithm given in FIPS-186-3.  If USE_FIPS186_2 is true,
+   FIPS-186-2 is used and thus the length is restricted to
+   1024/160.  */
 static gpg_err_code_t
 generate_fips186 (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
+                  int use_fips186_2,
                   int *r_counter, void **r_seed, size_t *r_seedlen,
                   gcry_mpi_t *r_h)
 {
@@ -397,18 +398,23 @@ generate_fips186 (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
     ;
   else if (nbits == 2048 && qbits == 256)
     ;
-  else if (nbits == 2048 && qbits == 256)
+  else if (nbits == 3072 && qbits == 256)
     ;
   else
     return GPG_ERR_INV_VALUE;
 
-  /* Note that we currently do not yet support 186-3 for prime
-     generation becuase it is not clear whether CAVS is prepared for
-     it.  */
-  ec = _gcry_generate_fips186_2_prime (nbits, qbits, NULL, 0,
-                                       &prime_q, &prime_p, 
-                                       r_counter,
-                                       r_seed, r_seedlen);
+  /* Fixme: Enable 186-3 after it has been approved and after fixing
+     the generation fucntion.  */
+/*   if (use_fips186_2) */
+    ec = _gcry_generate_fips186_2_prime (nbits, qbits, NULL, 0,
+                                         &prime_q, &prime_p, 
+                                         r_counter,
+                                         r_seed, r_seedlen);
+/*   else */
+/*     ec = _gcry_generate_fips186_3_prime (nbits, qbits, NULL, 0, */
+/*                                          &prime_q, &prime_p, */
+/*                                          r_counter, */
+/*                                          r_seed, r_seedlen, NULL); */
   if (ec)
     goto leave;
 
@@ -610,6 +616,7 @@ dsa_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
   unsigned int qbits = 0;
   gcry_sexp_t deriveparms = NULL;
   gcry_sexp_t seedinfo = NULL;
+  int use_fips186_2 = 0;
   int use_fips186 = 0;
   
 
@@ -640,23 +647,29 @@ dsa_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
 
       deriveparms = gcry_sexp_find_token (genparms, "derive-parms", 0);
 
-      /* Parse the optional "use-fips186" flag.  */
+      /* Parse the optional "use-fips186" flags.  */
       l1 = gcry_sexp_find_token (genparms, "use-fips186", 0);
       if (l1)
         {
           use_fips186 = 1;
           gcry_sexp_release (l1);
         }
+      l1 = gcry_sexp_find_token (genparms, "use-fips186-2", 0);
+      if (l1)
+        {
+          use_fips186_2 = 1;
+          gcry_sexp_release (l1);
+        }
     }
 
-  if (deriveparms || use_fips186 || fips_mode ())
+  if (deriveparms || use_fips186 || use_fips186_2 || fips_mode ())
     {
       int counter;
       void *seed;
       size_t seedlen;
       gcry_mpi_t h_value;
 
-      ec = generate_fips186 (&sk, nbits, qbits, 
+      ec = generate_fips186 (&sk, nbits, qbits, use_fips186_2,
                              &counter, &seed, &seedlen, &h_value);
       gcry_sexp_release (deriveparms);
       if (!ec)
index c8dbdab..1d8aba8 100644 (file)
@@ -1417,7 +1417,7 @@ _gcry_derive_x931_prime (const gcry_mpi_t xp,
 \f
 /* Generate the two prime used for DSA using the algorithm specified
    in FIPS 186-2.  PBITS is the desired length of the prime P and a
-   QBIST the length of the prime Q.  If SEED is not supplied and
+   QBITS the length of the prime Q.  If SEED is not supplied and
    SEEDLEN is 0 the function generates an appropriate SEED.  On
    success the generated primes are stored at R_Q and R_P, the counter
    value is stored at R_COUNTER and the seed actually used for
@@ -1580,7 +1580,7 @@ _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits,
     }
 
   /* Step 15:  Save p, q, counter and seed.  */
-/*   log_debug ("fips186-2 nbits p=%u q=%u counter=%d\n", */
+/*   log_debug ("fips186-2 pbits p=%u q=%u counter=%d\n", */
 /*              mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter); */
 /*   log_printhex("fips186-2 seed:", seed, seedlen);  */
 /*   log_mpidump ("fips186-2 prime p", prime_p); */
@@ -1616,3 +1616,247 @@ _gcry_generate_fips186_2_prime (unsigned int pbits, unsigned int qbits,
   gcry_mpi_release (val_2);
   return ec;
 }
+
+
+\f
+/* WARNING: The code below has not yet been tested!  However, it is
+   not yet used.  We need to wait for FIPS 186-3 final and for test
+   vectors.
+
+   Generate the two prime used for DSA using the algorithm specified
+   in FIPS 186-3, A.1.1.2.  PBITS is the desired length of the prime P
+   and a QBITS the length of the prime Q.  If SEED is not supplied and
+   SEEDLEN is 0 the function generates an appropriate SEED.  On
+   success the generated primes are stored at R_Q and R_P, the counter
+   value is stored at R_COUNTER and the seed actually used for
+   generation is stored at R_SEED and R_SEEDVALUE.  The hash algorithm
+   used is stored at R_HASHALGO.
+   
+   Note that this function is very similar to the fips186_2 code.  Due
+   to the minor differences, other buffer sizes and for documentarion,
+   we use a separate function.
+*/
+gpg_err_code_t
+_gcry_generate_fips186_3_prime (unsigned int pbits, unsigned int qbits,
+                                const void *seed, size_t seedlen,
+                                gcry_mpi_t *r_q, gcry_mpi_t *r_p,
+                                int *r_counter,
+                                void **r_seed, size_t *r_seedlen,
+                                int *r_hashalgo)
+{
+  gpg_err_code_t ec;
+  unsigned char seed_help_buffer[256/8];  /* Used to hold a generated SEED. */
+  unsigned char *seed_plus;     /* Malloced buffer to hold SEED+x.  */
+  unsigned char digest[256/8];  /* Helper buffer for SHA-1 digest.  */
+  gcry_mpi_t val_2 = NULL;      /* Helper for the prime test.  */
+  gcry_mpi_t tmpval = NULL;     /* Helper variable.  */
+  int hashalgo;                 /* The id of the Approved Hash Function.  */
+  int i;
+  
+  unsigned char value_u[256/8];
+  int value_n, value_b, value_j;
+  int counter;
+  gcry_mpi_t value_w = NULL;
+  gcry_mpi_t value_x = NULL;
+  gcry_mpi_t prime_q = NULL;
+  gcry_mpi_t prime_p = NULL;
+
+  gcry_assert (sizeof seed_help_buffer == sizeof digest
+               && sizeof seed_help_buffer == sizeof value_u);
+
+  /* Step 1:  Check the requested prime lengths.  */
+  /* Note that due to the size of our buffers QBITS is limited to 256.  */
+  if (pbits == 1024 && qbits == 160)
+    hashalgo = GCRY_MD_SHA1;
+  else if (pbits == 2048 && qbits == 224)
+    hashalgo = GCRY_MD_SHA224;
+  else if (pbits == 2048 && qbits == 256)
+    hashalgo = GCRY_MD_SHA256;
+  else if (pbits == 3072 && qbits == 256)
+    hashalgo = GCRY_MD_SHA256;
+  else
+    return GPG_ERR_INV_KEYLEN;
+
+  /* Also check that the hash algorithm is available.  */
+  ec = gpg_err_code (gcry_md_test_algo (hashalgo));
+  if (ec)
+    return ec;
+  gcry_assert (qbits/8 <= sizeof digest);
+  gcry_assert (gcry_md_get_algo_dlen (hashalgo) == qbits/8);
+
+
+  /* Step 2:  Check seedlen.  */
+  if (!seed && !seedlen)
+    ; /* No seed value given:  We are asked to generate it.  */
+  else if (!seed || seedlen < qbits/8)
+    return GPG_ERR_INV_ARG;
+  
+  /* Allocate a buffer to later compute SEED+some_increment and a few
+     helper variables.  */
+  seed_plus = gcry_malloc (seedlen < sizeof seed_help_buffer? 
+                           sizeof seed_help_buffer : seedlen);
+  if (!seed_plus)
+    {
+      ec = gpg_err_code_from_syserror ();
+      goto leave;
+    }
+  val_2   = mpi_alloc_set_ui (2);
+  value_w = gcry_mpi_new (pbits);
+  value_x = gcry_mpi_new (pbits);
+
+  /* Step 3: n = \lceil L / outlen \rceil - 1  */
+  value_n = (pbits + qbits - 1) / qbits - 1;
+  /* Step 4: b = L - 1 - (n * outlen)  */
+  value_b = pbits - 1 - (value_n * qbits);
+
+ restart:  
+  /* Generate Q.  */
+  for (;;)
+    {
+      /* Step 5:  Generate a (new) seed unless one has been supplied.  */
+      if (!seed)
+        {
+          seedlen = qbits/8;
+          gcry_assert (seedlen <= sizeof seed_help_buffer);
+          gcry_create_nonce (seed_help_buffer, seedlen);
+          seed = seed_help_buffer;
+        }
+      
+      /* Step 6:  U = hash(seed)  */
+      gcry_md_hash_buffer (hashalgo, value_u, seed, seedlen);
+
+      /* Step 7:  q = 2^{N-1} + U + 1 - (U mod 2)  */
+      if ( !(value_u[qbits/8-1] & 0x01) )
+        {
+          for (i=qbits/8-1; i >= 0; i--)
+            {
+              value_u[i]++;
+              if (value_u[i])
+                break;
+            }
+        }
+      gcry_mpi_release (prime_q); prime_q = NULL;
+      ec = gpg_err_code (gcry_mpi_scan (&prime_q, GCRYMPI_FMT_USG, 
+                                        value_u, sizeof value_u, NULL));
+      if (ec)
+        goto leave;
+      mpi_set_highbit (prime_q, qbits-1 );
+      
+      /* Step 8:  Test whether Q is prime using 64 round of Rabin-Miller.
+                  According to table C.1 this is sufficient for all
+                  supported prime sizes (i.e. up 3072/256).  */
+      if (check_prime (prime_q, val_2, 64, NULL, NULL))
+        break; /* Yes, Q is prime.  */
+
+      /* Step 8.  */
+      seed = NULL;  /* Force a new seed at Step 5.  */
+    }
+  
+  /* Step 11.  Note that we do no use an explicit offset but increment
+     SEED_PLUS accordingly.  */
+  memcpy (seed_plus, seed, seedlen);
+  counter = 0;
+
+  /* Generate P. */
+  prime_p = gcry_mpi_new (pbits);
+  for (;;)
+    {
+      /* Step 11.1: For j = 0,...n let 
+                      V_j = hash(seed+offset+j)  
+         Step 11.2: W = V_0 + V_1*2^outlen + 
+                            ... 
+                            + V_{n-1}*2^{(n-1)*outlen}
+                            + (V_{n} mod 2^b)*2^{n*outlen}                
+       */
+      mpi_set_ui (value_w, 0);
+      for (value_j=0; value_j <= value_n; value_j++)
+        {
+          /* There is no need to have an explicit offset variable: In
+             the first round we shall have an offset of 1 and a j of
+             0.  This is achieved by incrementing SEED_PLUS here.  For
+             the next round offset is implicitly updated by using
+             SEED_PLUS again.  */
+          for (i=seedlen-1; i >= 0; i--)
+            {
+              seed_plus[i]++;
+              if (seed_plus[i])
+                break;
+            }
+          gcry_md_hash_buffer (GCRY_MD_SHA1, digest, seed_plus, seedlen);
+          
+          gcry_mpi_release (tmpval); tmpval = NULL;
+          ec = gpg_err_code (gcry_mpi_scan (&tmpval, GCRYMPI_FMT_USG,
+                                            digest, sizeof digest, NULL));
+          if (ec)
+            goto leave;
+          if (value_j == value_n)
+            mpi_clear_highbit (tmpval, value_b+1); /* (V_n mod 2^b) */
+          mpi_lshift (tmpval, tmpval, value_j*qbits);
+          mpi_add (value_w, value_w, tmpval);
+        }
+
+      /* Step 11.3: X = W + 2^{L-1}  */
+      mpi_set_ui (value_x, 0);
+      mpi_set_highbit (value_x, pbits-1);
+      mpi_add (value_x, value_x, value_w);
+
+      /* Step 11.4:  c = X mod 2q  */
+      mpi_mul_2exp (tmpval, prime_q, 1);
+      mpi_mod (tmpval, value_x, tmpval);
+
+      /* Step 11.5:  p = X - (c - 1)  */
+      mpi_sub_ui (tmpval, tmpval, 1);
+      mpi_sub (prime_p, value_x, tmpval);
+
+      /* Step 11.6: If  p < 2^{L-1}  skip the primality test.  */
+      /* Step 11.7 and 11.8: Primality test.  */
+      if (mpi_get_nbits (prime_p) >= pbits-1
+          && check_prime (prime_p, val_2, 64, NULL, NULL) )
+        break; /* Yes, P is prime, continue with Step 15.  */
+      
+      /* Step 11.9: counter = counter + 1, offset = offset + n + 1.
+                    If counter >= 4L  goto Step 5.  */
+      counter++;
+      if (counter >= 4*pbits)
+        goto restart;
+    }
+
+  /* Step 12:  Save p, q, counter and seed.  */
+  log_debug ("fips186-3 pbits p=%u q=%u counter=%d\n",
+             mpi_get_nbits (prime_p), mpi_get_nbits (prime_q), counter);
+  log_printhex("fips186-3 seed:", seed, seedlen);
+  log_mpidump ("fips186-3 prime p", prime_p);
+  log_mpidump ("fips186-3 prime q", prime_q);
+  if (r_q)
+    {
+      *r_q = prime_q;
+      prime_q = NULL;
+    }
+  if (r_p)
+    {
+      *r_p = prime_p;
+      prime_p = NULL;
+    }
+  if (r_counter)
+    *r_counter = counter;
+  if (r_seed && r_seedlen)
+    {
+      memcpy (seed_plus, seed, seedlen);
+      *r_seed = seed_plus;
+      seed_plus = NULL;
+      *r_seedlen = seedlen;
+    }
+  if (r_hashalgo)
+    *r_hashalgo = hashalgo;
+
+ leave:
+  gcry_mpi_release (tmpval);
+  gcry_mpi_release (value_x);
+  gcry_mpi_release (value_w);
+  gcry_mpi_release (prime_p);
+  gcry_mpi_release (prime_q);
+  gcry_free (seed_plus);
+  gcry_mpi_release (val_2);
+  return ec;
+}
+
index f6ae050..64e6480 100644 (file)
@@ -2759,12 +2759,19 @@ usually not required.  Note that this algorithm is implicitly used if
 either @code{derive-parms} is given or Libgcrypt is in FIPS mode.
 
 @item use-fips186
+Force the use of the FIPS 186 key generation algorithm instead of the
+default algorithm.  This flag is only meaningful for DSA and usually
+not required.  Note that this algorithm is implicitly used if either
+@code{derive-parms} is given or Libgcrypt is in FIPS mode.  As of now
+FIPS 186-2 is implemented; after the approval of FIPS 186-3 the code
+will be changed to implement 186-3.
+
+
+@item use-fips186-2
 Force the use of the FIPS 186-2 key generation algorithm instead of
-the default algorithm.  This flag is only meaningful for DSA and
-usually not required.  Note that this algorithm is implicitly used if
-either @code{derive-parms} is given or Libgcrypt is in FIPS mode.
-This implementation may be changed in future to use the forthcoming
-FIPS 186-3 algorithm.
+the default algorithm.  This algorithm has a slighlty different from
+FIPS 186-3 and allws only 1024 bit keys.  This flag is only meaningful
+for DSA and only required for FIPS testing backward compatibility.
 
 
 @end table
index 9faa26d..7deb90c 100644 (file)
@@ -185,9 +185,15 @@ gpg_err_code_t _gcry_generate_fips186_2_prime
                   gcry_mpi_t *r_q, gcry_mpi_t *r_p,
                   int *r_counter,
                   void **r_seed, size_t *r_seedlen);
+gpg_err_code_t _gcry_generate_fips186_3_prime 
+                 (unsigned int pbits, unsigned int qbits,
+                  const void *seed, size_t seedlen,
+                  gcry_mpi_t *r_q, gcry_mpi_t *r_p,
+                  int *r_counter,
+                  void **r_seed, size_t *r_seedlen, int *r_hashalgo);
 
 
-/* replacements of missing functions (missing-string.c)*/
+/* Replacements of missing functions (missing-string.c).  */
 #ifndef HAVE_STPCPY
 char *stpcpy (char *a, const char *b);
 #endif
@@ -195,7 +201,7 @@ char *stpcpy (char *a, const char *b);
 int strcasecmp (const char *a, const char *b) _GCRY_GCC_ATTR_PURE;
 #endif
 
-/* macros used to rename missing functions */
+/* Macros used to rename missing functions.  */
 #ifndef HAVE_STRTOUL
 #define strtoul(a,b,c)  ((unsigned long)strtol((a),(b),(c)))
 #endif