[PATCH v3] Truncate hash values for ECDSA signature scheme

Dmitry Eremin-Solenikov dbaryshkov at gmail.com
Mon Dec 30 21:38:37 CET 2013


* cipher/dsa-common (_gcry_dsa_normalize_hash): New. Truncate opaque
  mpis as required for DSA and ECDSA signature schemas.
* cipher/dsa.c (verify): Return gpg_err_code_t value from verify() to
  behave like the rest of internal sign/verify functions.
* cipher/dsa.c (sign, verify, dsa_verify): Factor out hash truncation.
* cipher/ecc-ecdsa.c (_gcry_ecc_ecdsa_sign): Factor out hash truncation.
* cipher/ecc-ecdsa.c (_gcry_ecc_ecdsa_verify):
  as required by ECDSA scheme, truncate hash values to bitlength of
  used curve.
* tests/pubkey.c (check_ecc_sample_key): add a testcase for hash
  truncation.

Signed-off-by: Dmitry Eremin-Solenikov <dbaryshkov at gmail.com>
---

* Change in V3 - fix testcases to use (hash sha1 ... ) S-exp instead of
(value ...) - otherwise it will not be converted to an opaque MPI.

 cipher/dsa-common.c      | 33 ++++++++++++++++++++
 cipher/dsa.c             | 81 ++++++++++++++++++++----------------------------
 cipher/ecc-ecdsa.c       | 28 ++++++++---------
 cipher/pubkey-internal.h |  3 ++
 tests/pubkey.c           | 47 +++++++++++++++++++++++++++-
 5 files changed, 129 insertions(+), 63 deletions(-)

diff --git a/cipher/dsa-common.c b/cipher/dsa-common.c
index d251eae..a5e42a2 100644
--- a/cipher/dsa-common.c
+++ b/cipher/dsa-common.c
@@ -359,3 +359,36 @@ _gcry_dsa_gen_rfc6979_k (gcry_mpi_t *r_k,
     *r_k = k;
   return rc;
 }
+
+/*
+ * Truncate opaque hash value to qbits for DSA.
+ * Non-opaque input is not truncated, in hope that user
+ * knows what is passed. It is not possible to correctly
+ * trucate non-opaque inputs.
+ */
+gpg_err_code_t
+_gcry_dsa_normalize_hash (gcry_mpi_t input,
+                          gcry_mpi_t *out,
+                          unsigned int qbits)
+{
+  gpg_err_code_t rc = 0;
+  const void *abuf;
+  unsigned int abits;
+  gcry_mpi_t hash;
+
+  if (mpi_is_opaque (input))
+    {
+      abuf = mpi_get_opaque (input, &abits);
+      rc = _gcry_mpi_scan (&hash, GCRYMPI_FMT_USG, abuf, (abits+7)/8, NULL);
+      if (rc)
+        return rc;
+      if (abits > qbits)
+        mpi_rshift (hash, hash, abits - qbits);
+    }
+  else
+    hash = input;
+
+  *out = hash;
+
+  return rc;
+}
diff --git a/cipher/dsa.c b/cipher/dsa.c
index 50bdab1..1707d8c 100644
--- a/cipher/dsa.c
+++ b/cipher/dsa.c
@@ -115,7 +115,7 @@ static gpg_err_code_t generate (DSA_secret_key *sk,
                                 gcry_mpi_t **ret_factors);
 static gpg_err_code_t sign (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
                             DSA_secret_key *skey, int flags, int hashalgo);
-static int verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
+static gpg_err_code_t verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
                    DSA_public_key *pkey);
 static unsigned int dsa_get_nbits (gcry_sexp_t parms);
 
@@ -165,12 +165,12 @@ test_keys (DSA_secret_key *sk, unsigned int qbits)
   sign (sig_a, sig_b, data, sk, 0, 0);
 
   /* Verify the signature using the public key.  */
-  if ( !verify (sig_a, sig_b, data, &pk) )
+  if ( verify (sig_a, sig_b, data, &pk) )
     goto leave; /* Signature does not match.  */
 
   /* Modify the data and check that the signing fails.  */
   mpi_add_ui (data, data, 1);
-  if ( verify (sig_a, sig_b, data, &pk) )
+  if ( !verify (sig_a, sig_b, data, &pk) )
     goto leave; /* Signature matches but should not.  */
 
   result = 0; /* The test succeeded.  */
@@ -573,20 +573,9 @@ sign (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input, DSA_secret_key *skey,
   qbits = mpi_get_nbits (skey->q);
 
   /* Convert the INPUT into an MPI.  */
-  if (mpi_is_opaque (input))
-    {
-      abuf = mpi_get_opaque (input, &abits);
-      rc = _gcry_mpi_scan (&hash, GCRYMPI_FMT_USG, abuf, (abits+7)/8, NULL);
-      if (rc)
-        return rc;
-      if (abits > qbits)
-        mpi_rshift (hash, hash, abits - qbits);
-    }
-  else
-    {
-      mpi_normalize (input);
-      hash = input;
-    }
+  rc = _gcry_dsa_normalize_hash (input, &hash, qbits);
+  if (rc)
+    return rc;
 
  again:
   /* Create the K value.  */
@@ -651,18 +640,25 @@ sign (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input, DSA_secret_key *skey,
 /*
    Returns true if the signature composed from R and S is valid.
  */
-static int
-verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_public_key *pkey )
+static gpg_err_code_t
+verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input, DSA_public_key *pkey )
 {
-  int rc;
+  gpg_err_code_t rc = 0;
   gcry_mpi_t w, u1, u2, v;
   gcry_mpi_t base[3];
   gcry_mpi_t ex[3];
+  gcry_mpi_t hash;
+  unsigned int nbits;
 
   if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
-    return 0; /* assertion	0 < r < q  failed */
+    return GPG_ERR_BAD_SIGNATURE; /* Assertion	0 < r < n  failed.  */
   if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
-    return 0; /* assertion	0 < s < q  failed */
+    return GPG_ERR_BAD_SIGNATURE; /* Assertion	0 < s < n  failed.  */
+
+  nbits = mpi_get_nbits (pkey->q);
+  rc = _gcry_dsa_normalize_hash (input, &hash, nbits);
+  if (rc)
+    return rc;
 
   w  = mpi_alloc( mpi_get_nlimbs(pkey->q) );
   u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
@@ -685,12 +681,25 @@ verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_public_key *pkey )
   mpi_mulpowm( v, base, ex, pkey->p );
   mpi_fdiv_r( v, v, pkey->q );
 
-  rc = !mpi_cmp( v, r );
+  if (mpi_cmp( v, r ))
+    {
+      if (DBG_CIPHER)
+        {
+          log_mpidump ("     i", input);
+          log_mpidump ("     h", hash);
+          log_mpidump ("     v", v);
+          log_mpidump ("     r", r);
+          log_mpidump ("     s", s);
+        }
+      rc = GPG_ERR_BAD_SIGNATURE;
+    }
 
   mpi_free(w);
   mpi_free(u1);
   mpi_free(u2);
   mpi_free(v);
+  if (hash != input)
+    mpi_free (hash);
 
   return rc;
 }
@@ -1090,31 +1099,7 @@ dsa_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
     }
 
   /* Verify the signature.  */
-  if (mpi_is_opaque (data))
-    {
-      const void *abuf;
-      unsigned int abits, qbits;
-      gcry_mpi_t a;
-
-      qbits = mpi_get_nbits (pk.q);
-
-      abuf = mpi_get_opaque (data, &abits);
-      rc = _gcry_mpi_scan (&a, GCRYMPI_FMT_USG, abuf, (abits+7)/8, NULL);
-      if (!rc)
-        {
-          if (abits > qbits)
-            mpi_rshift (a, a, abits - qbits);
-
-          if (!verify (sig_r, sig_s, a, &pk))
-            rc = GPG_ERR_BAD_SIGNATURE;
-          _gcry_mpi_release (a);
-        }
-    }
-  else
-    {
-      if (!verify (sig_r, sig_s, data, &pk))
-        rc = GPG_ERR_BAD_SIGNATURE;
-    }
+  rc = verify (sig_r, sig_s, data, &pk);
 
  leave:
   _gcry_mpi_release (pk.p);
diff --git a/cipher/ecc-ecdsa.c b/cipher/ecc-ecdsa.c
index b4bbe2c..1484830 100644
--- a/cipher/ecc-ecdsa.c
+++ b/cipher/ecc-ecdsa.c
@@ -57,18 +57,9 @@ _gcry_ecc_ecdsa_sign (gcry_mpi_t input, ECC_secret_key *skey,
   qbits = mpi_get_nbits (skey->E.n);
 
   /* Convert the INPUT into an MPI if needed.  */
-  if (mpi_is_opaque (input))
-    {
-      abuf = mpi_get_opaque (input, &abits);
-      rc = _gcry_mpi_scan (&hash, GCRYMPI_FMT_USG, abuf, (abits+7)/8, NULL);
-      if (rc)
-        return rc;
-      if (abits > qbits)
-        mpi_rshift (hash, hash, abits - qbits);
-    }
-  else
-    hash = input;
-
+  rc = _gcry_dsa_normalize_hash (input, &hash, qbits);
+  if (rc)
+    return rc;
 
   k = NULL;
   dr = mpi_alloc (0);
@@ -161,15 +152,21 @@ _gcry_ecc_ecdsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
                         gcry_mpi_t r, gcry_mpi_t s)
 {
   gpg_err_code_t err = 0;
-  gcry_mpi_t h, h1, h2, x;
+  gcry_mpi_t hash, h, h1, h2, x;
   mpi_point_struct Q, Q1, Q2;
   mpi_ec_t ctx;
+  unsigned int nbits;
 
   if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
     return GPG_ERR_BAD_SIGNATURE; /* Assertion	0 < r < n  failed.  */
   if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
     return GPG_ERR_BAD_SIGNATURE; /* Assertion	0 < s < n  failed.  */
 
+  nbits = mpi_get_nbits (pkey->E.n);
+  err = _gcry_dsa_normalize_hash (input, &hash, nbits);
+  if (err)
+    return err;
+
   h  = mpi_alloc (0);
   h1 = mpi_alloc (0);
   h2 = mpi_alloc (0);
@@ -184,7 +181,7 @@ _gcry_ecc_ecdsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
   /* h  = s^(-1) (mod n) */
   mpi_invm (h, s, pkey->E.n);
   /* h1 = hash * s^(-1) (mod n) */
-  mpi_mulm (h1, input, h, pkey->E.n);
+  mpi_mulm (h1, hash, h, pkey->E.n);
   /* Q1 = [ hash * s^(-1) ]G  */
   _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx);
   /* h2 = r * s^(-1) (mod n) */
@@ -230,5 +227,8 @@ _gcry_ecc_ecdsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
   mpi_free (h2);
   mpi_free (h1);
   mpi_free (h);
+  if (hash != input)
+    mpi_free (hash);
+
   return err;
 }
diff --git a/cipher/pubkey-internal.h b/cipher/pubkey-internal.h
index 96fe0e4..b8167c7 100644
--- a/cipher/pubkey-internal.h
+++ b/cipher/pubkey-internal.h
@@ -92,6 +92,9 @@ gpg_err_code_t _gcry_dsa_gen_rfc6979_k (gcry_mpi_t *r_k,
                                         int halgo,
                                         unsigned int extraloops);
 
+gpg_err_code_t _gcry_dsa_normalize_hash (gcry_mpi_t input,
+                                         gcry_mpi_t *out,
+                                         unsigned int qbits);
 
 /*-- ecc.c --*/
 gpg_err_code_t _gcry_pk_ecc_get_sexp (gcry_sexp_t *r_sexp, int mode,
diff --git a/tests/pubkey.c b/tests/pubkey.c
index 4e12dfd..ae5eea2 100644
--- a/tests/pubkey.c
+++ b/tests/pubkey.c
@@ -980,9 +980,23 @@ check_ecc_sample_key (void)
     "(data (flags raw)\n"
     " (value #00112233445566778899AABBCCDDEEFF"
     /* */    "000102030405060708090A0B0C0D0E0F#))";
+  static const char hash2_string[] =
+    "(data (flags raw)\n"
+    " (hash sha1 #00112233445566778899AABBCCDDEEFF"
+    /* */    "000102030405060708090A0B0C0D0E0F"
+    /* */    "000102030405060708090A0B0C0D0E0F"
+    /* */    "00112233445566778899AABBCCDDEEFF#))";
+  /* hash2, but longer than curve length, so it will be truncated */
+  static const char hash3_string[] =
+    "(data (flags raw)\n"
+    " (hash sha1 #00112233445566778899AABBCCDDEEFF"
+    /* */    "000102030405060708090A0B0C0D0E0F"
+    /* */    "000102030405060708090A0B0C0D0E0F"
+    /* */    "00112233445566778899AABBCCDDEEFF"
+    /* */    "000102030405060708090A0B0C0D0E0F#))";
 
   gpg_error_t err;
-  gcry_sexp_t key, hash, sig;
+  gcry_sexp_t key, hash, hash2, hash3, sig, sig2;
 
   if (verbose)
     fprintf (stderr, "Checking sample ECC key.\n");
@@ -990,6 +1004,12 @@ check_ecc_sample_key (void)
   if ((err = gcry_sexp_new (&hash, hash_string, 0, 1)))
     die ("line %d: %s", __LINE__, gpg_strerror (err));
 
+  if ((err = gcry_sexp_new (&hash2, hash2_string, 0, 1)))
+    die ("line %d: %s", __LINE__, gpg_strerror (err));
+
+  if ((err = gcry_sexp_new (&hash3, hash3_string, 0, 1)))
+    die ("line %d: %s", __LINE__, gpg_strerror (err));
+
   if ((err = gcry_sexp_new (&key, ecc_private_key, 0, 1)))
     die ("line %d: %s", __LINE__, gpg_strerror (err));
 
@@ -1003,6 +1023,28 @@ check_ecc_sample_key (void)
   if ((err = gcry_pk_verify (sig, hash, key)))
     die ("gcry_pk_verify failed: %s", gpg_strerror (err));
 
+  /* Verify hash truncation */
+  gcry_sexp_release (key);
+  if ((err = gcry_sexp_new (&key, ecc_private_key, 0, 1)))
+    die ("line %d: %s", __LINE__, gpg_strerror (err));
+
+  if ((err = gcry_pk_sign (&sig2, hash2, key)))
+    die ("gcry_pk_sign failed: %s", gpg_strerror (err));
+
+  gcry_sexp_release (sig);
+  if ((err = gcry_pk_sign (&sig, hash3, key)))
+    die ("gcry_pk_sign failed: %s", gpg_strerror (err));
+
+  gcry_sexp_release (key);
+  if ((err = gcry_sexp_new (&key, ecc_public_key, 0, 1)))
+    die ("line %d: %s", __LINE__, gpg_strerror (err));
+
+  if ((err = gcry_pk_verify (sig, hash2, key)))
+    die ("gcry_pk_verify failed: %s", gpg_strerror (err));
+
+  if ((err = gcry_pk_verify (sig2, hash3, key)))
+    die ("gcry_pk_verify failed: %s", gpg_strerror (err));
+
   /* Now try signing without the Q parameter.  */
 
   gcry_sexp_release (key);
@@ -1021,8 +1063,11 @@ check_ecc_sample_key (void)
     die ("gcry_pk_verify signed without Q failed: %s", gpg_strerror (err));
 
   gcry_sexp_release (sig);
+  gcry_sexp_release (sig2);
   gcry_sexp_release (key);
   gcry_sexp_release (hash);
+  gcry_sexp_release (hash2);
+  gcry_sexp_release (hash3);
 }
 
 
-- 
1.8.5.2




More information about the Gcrypt-devel mailing list