[PATCH v2] Truncate hash values for ECDSA signature scheme
Dmitry Eremin-Solenikov
dbaryshkov at gmail.com
Sun Dec 22 14:15:52 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>
---
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..2e60da9 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"
+ " (value #00112233445566778899AABBCCDDEEFF"
+ /* */ "000102030405060708090A0B0C0D0E0F"
+ /* */ "000102030405060708090A0B0C0D0E0F"
+ /* */ "00112233445566778899AABBCCDDEEFF#))";
+ /* hash2, but longer than curve length, so it will be truncated */
+ static const char hash3_string[] =
+ "(data (flags raw)\n"
+ " (value #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.1
More information about the Gcrypt-devel
mailing list