From 60de5f48cbfc3868570284e91415ca7e06c390e1 Mon Sep 17 00:00:00 2001 From: Jeff Burdges Date: Sun, 20 Mar 2016 14:44:36 +0000 Subject: [PATCH] Implement a Full Domain Hash (FDH) for RSA signatures and blind signatures This gives a measure of provable security to the Taler exchange/mint against hypothetical one-more forgery attacks. See: https://eprint.iacr.org/2001/002.pdf http://www.di.ens.fr/~pointche/Documents/Papers/2001_fcA.pdf We seed the FDH with the denomination keys as as a homage to RSA-PSS. This may slightly improves the exchanges's resistance to a violation of RSA-KTI and against insiders who can influence the choice of RSA keys but cannot actually exfiltrate them. Adopting FDH fixes a bug when using 512 bit RSA keys as well. --- src/util/Makefile.am | 2 +- src/util/crypto_rsa.c | 248 ++++++++++++++++++++++++++++--------- src/util/test_crypto_rsa.c | 33 +++-- 3 files changed, 215 insertions(+), 68 deletions(-) diff --git a/src/util/Makefile.am b/src/util/Makefile.am index 65b53b91d..c38f19c93 100644 --- a/src/util/Makefile.am +++ b/src/util/Makefile.am @@ -483,7 +483,7 @@ test_crypto_random_LDADD = \ test_crypto_rsa_SOURCES = \ test_crypto_rsa.c test_crypto_rsa_LDADD = \ - libgnunetutil.la + libgnunetutil.la -lgcrypt test_disk_SOURCES = \ test_disk.c diff --git a/src/util/crypto_rsa.c b/src/util/crypto_rsa.c index 6c58757d8..a14eff407 100644 --- a/src/util/crypto_rsa.c +++ b/src/util/crypto_rsa.c @@ -566,16 +566,15 @@ GNUNET_CRYPTO_rsa_blinding_key_free (struct GNUNET_CRYPTO_rsa_BlindingKey *bkey) /** - * Encode the blinding key in a format suitable for - * storing it into a file. + * Print an MPI to a newly created buffer * - * @param bkey the blinding key - * @param[out] buffer set to a buffer with the encoded key - * @return size of memory allocated in @a buffer + * @param v MPI to print. + * @param[out] buffer set to a buffer with the result + * @return number of bytes stored in @a buffer */ size_t -GNUNET_CRYPTO_rsa_blinding_key_encode (const struct GNUNET_CRYPTO_rsa_BlindingKey *bkey, - char **buffer) +GNUNET_CRYPTO_mpi_print (gcry_mpi_t v, + char **buffer) { size_t n; char *b; @@ -585,19 +584,35 @@ GNUNET_CRYPTO_rsa_blinding_key_encode (const struct GNUNET_CRYPTO_rsa_BlindingKe NULL, 0, &n, - bkey->r); + v); b = GNUNET_malloc (n); GNUNET_assert (0 == gcry_mpi_print (GCRYMPI_FMT_USG, (unsigned char *) b, n, &rsize, - bkey->r)); + v)); *buffer = b; return n; } +/** + * Encode the blinding key in a format suitable for + * storing it into a file. + * + * @param bkey the blinding key + * @param[out] buffer set to a buffer with the encoded key + * @return size of memory allocated in @a buffer + */ +size_t +GNUNET_CRYPTO_rsa_blinding_key_encode (const struct GNUNET_CRYPTO_rsa_BlindingKey *bkey, + char **buffer) +{ + return GNUNET_CRYPTO_mpi_print (bkey->r, buffer); +} + + /** * Decode the blinding key from the data-format back * to the "normal", internal format. @@ -629,6 +644,95 @@ GNUNET_CRYPTO_rsa_blinding_key_decode (const char *buf, } +/** + * Computes a full domain hash seeded by the given public key. + * This gives a measure of provable security to the Taler exchange + * against one-more forgery attacks. See: + * https://eprint.iacr.org/2001/002.pdf + * http://www.di.ens.fr/~pointche/Documents/Papers/2001_fcA.pdf + * + * @param hash initial hash of the message to sign + * @param pkey the public key of the signer + * @return libgcrypt error that to represent an allocation failure + */ +gcry_error_t +rsa_full_domain_hash (gcry_mpi_t *r, + const struct GNUNET_HashCode *hash, + const struct GNUNET_CRYPTO_rsa_PublicKey *pkey, + size_t *rsize) +{ + int i,nbits,nhashes; + gcry_error_t rc; + char *buf; + size_t buf_len; + gcry_md_hd_t h,h0; + struct GNUNET_HashCode *hs; + + /* Uncomment the following to debug without using the full domain hash */ + /* + rc = gcry_mpi_scan (r, + GCRYMPI_FMT_USG, + (const unsigned char *)hash, + sizeof(struct GNUNET_HashCode), + rsize); + return rc; + */ + + nbits = GNUNET_CRYPTO_rsa_public_key_len (pkey); + // calls gcry_mpi_get_nbits(.. pkey->sexp ..) + if (nbits < 512) + nbits = 512; + + // Already almost an HMAC since we consume a hash, so no GCRY_MD_FLAG_HMAC. + rc = gcry_md_open (&h,GCRY_MD_SHA512,0); + if (0 != rc) return rc; + + // We seed with the public denomination key as a homage to RSA-PSS by + // Mihir Bellare and Phillip Rogaway. Doing this lowers the degree + // of the hypothetical polyomial-time attack on RSA-KTI created by a + // polynomial-time one-more forgary attack. Yey seeding! + buf_len = GNUNET_CRYPTO_rsa_public_key_encode (pkey, &buf); + gcry_md_write (h, buf,buf_len); + GNUNET_free (buf); + + nhashes = (nbits-1) / (8 * sizeof(struct GNUNET_HashCode)) + 1; + hs = (struct GNUNET_HashCode *)GNUNET_malloc (nhashes * sizeof(struct GNUNET_HashCode)); + for (i=0; isexp, "public-key", "ne"); @@ -663,11 +766,9 @@ GNUNET_CRYPTO_rsa_blind (const struct GNUNET_HashCode *hash, *buffer = NULL; return 0; } - if (0 != (rc = gcry_mpi_scan (&data, - GCRYMPI_FMT_USG, - (const unsigned char *) hash, - sizeof (struct GNUNET_HashCode), - &rsize))) + + rc = rsa_full_domain_hash(&data, hash, pkey, &rsize); + if (0 != rc) // Allocation error in libgcrypt { GNUNET_break (0); gcry_mpi_release (ne[0]); @@ -690,75 +791,50 @@ GNUNET_CRYPTO_rsa_blind (const struct GNUNET_HashCode *hash, gcry_mpi_release (ne[1]); gcry_mpi_release (r_e); - gcry_mpi_print (GCRYMPI_FMT_USG, - NULL, - 0, - &n, - data_r_e); - b = GNUNET_malloc (n); - rc = gcry_mpi_print (GCRYMPI_FMT_USG, - (unsigned char *) b, - n, - &rsize, - data_r_e); + n = GNUNET_CRYPTO_mpi_print (data_r_e, buffer); gcry_mpi_release (data_r_e); - *buffer = b; return n; } /** - * Convert the data specified in the given purpose argument to an - * S-expression suitable for signature operations. + * Convert an MPI to an S-expression suitable for signature operations. * - * @param ptr pointer to the data to convert - * @param size the size of the data + * @param value pointer to the data to convert * @return converted s-expression */ static gcry_sexp_t -data_to_sexp (const void *ptr, size_t size) +mpi_to_sexp (gcry_mpi_t value) { - gcry_mpi_t value; - gcry_sexp_t data; + gcry_sexp_t data = NULL; - value = NULL; - data = NULL; - GNUNET_assert (0 == - gcry_mpi_scan (&value, - GCRYMPI_FMT_USG, - ptr, - size, - NULL)); GNUNET_assert (0 == gcry_sexp_build (&data, NULL, "(data (flags raw) (value %M))", value)); - gcry_mpi_release (value); return data; } /** - * Sign the given message. + * Sign and release the given MPI. * * @param key private key to use for the signing - * @param msg the message to sign - * @param msg_len number of bytes in @a msg to sign + * @param value the MPI to sign * @return NULL on error, signature on success */ struct GNUNET_CRYPTO_rsa_Signature * -GNUNET_CRYPTO_rsa_sign (const struct GNUNET_CRYPTO_rsa_PrivateKey *key, - const void *msg, - size_t msg_len) +rsa_sign_mpi (const struct GNUNET_CRYPTO_rsa_PrivateKey *key, + gcry_mpi_t value) { struct GNUNET_CRYPTO_rsa_Signature *sig; struct GNUNET_CRYPTO_rsa_PublicKey *public_key; - gcry_sexp_t result; - gcry_sexp_t data; + gcry_sexp_t data,result; + + data = mpi_to_sexp (value); + gcry_mpi_release (value); - data = data_to_sexp (msg, - msg_len); if (0 != gcry_pk_sign (&result, data, @@ -775,7 +851,7 @@ GNUNET_CRYPTO_rsa_sign (const struct GNUNET_CRYPTO_rsa_PrivateKey *key, data, public_key->sexp)) { - GNUNET_break (0); + GNUNET_break (0); GNUNET_CRYPTO_rsa_public_key_free (public_key); gcry_sexp_release (data); gcry_sexp_release (result); @@ -791,6 +867,56 @@ GNUNET_CRYPTO_rsa_sign (const struct GNUNET_CRYPTO_rsa_PrivateKey *key, } +/** + * Sign a blinded value, which must be a full domain hash of a message. + * + * @param key private key to use for the signing + * @param msg the message to sign + * @param msg_len number of bytes in @a msg to sign + * @return NULL on error, signature on success + */ +struct GNUNET_CRYPTO_rsa_Signature * +GNUNET_CRYPTO_rsa_sign_blinded (const struct GNUNET_CRYPTO_rsa_PrivateKey *key, + const void *msg, + size_t msg_len) +{ + gcry_mpi_t v = NULL; + + GNUNET_assert (0 == + gcry_mpi_scan (&v, + GCRYMPI_FMT_USG, + msg, + msg_len, + NULL)); + + return rsa_sign_mpi (key,v); +} + + +/** + * Create and sign a full domain hash of a message. + * + * @param key private key to use for the signing + * @param hash the hash of the message to sign + * @return NULL on error, signature on success + */ +struct GNUNET_CRYPTO_rsa_Signature * +GNUNET_CRYPTO_rsa_sign_fdh (const struct GNUNET_CRYPTO_rsa_PrivateKey *key, + const struct GNUNET_HashCode *hash) +{ + struct GNUNET_CRYPTO_rsa_PublicKey *pkey; + gcry_mpi_t v = NULL; + gcry_error_t rc; + + pkey = GNUNET_CRYPTO_rsa_private_key_get_public (key); + rc = rsa_full_domain_hash (&v, hash, pkey, NULL); + GNUNET_CRYPTO_rsa_public_key_free (pkey); + GNUNET_assert (0 == rc); + + return rsa_sign_mpi (key,v); +} + + /** * Free memory occupied by signature. * @@ -976,22 +1102,26 @@ GNUNET_CRYPTO_rsa_unblind (struct GNUNET_CRYPTO_rsa_Signature *sig, * * @param hash hash of the message to verify to match the @a sig * @param sig signature that is being validated - * @param public_key public key of the signer + * @param pkey public key of the signer * @returns #GNUNET_OK if ok, #GNUNET_SYSERR if invalid */ int GNUNET_CRYPTO_rsa_verify (const struct GNUNET_HashCode *hash, const struct GNUNET_CRYPTO_rsa_Signature *sig, - const struct GNUNET_CRYPTO_rsa_PublicKey *public_key) + const struct GNUNET_CRYPTO_rsa_PublicKey *pkey) { gcry_sexp_t data; + gcry_mpi_t r; int rc; - data = data_to_sexp (hash, - sizeof (struct GNUNET_HashCode)); + rc = rsa_full_domain_hash (&r, hash, pkey, NULL); + GNUNET_assert (0 == rc); // Allocation error in libgcrypt + data = mpi_to_sexp(r); + gcry_mpi_release (r); + rc = gcry_pk_verify (sig->sexp, data, - public_key->sexp); + pkey->sexp); gcry_sexp_release (data); if (0 != rc) { diff --git a/src/util/test_crypto_rsa.c b/src/util/test_crypto_rsa.c index 7580062df..9bd2e6ae5 100644 --- a/src/util/test_crypto_rsa.c +++ b/src/util/test_crypto_rsa.c @@ -20,11 +20,19 @@ * @author Sree Harsha Totakura */ #include "platform.h" +#include #include "gnunet_util_lib.h" #define KEY_SIZE 1024 +gcry_error_t +rsa_full_domain_hash (gcry_mpi_t *r, + const struct GNUNET_HashCode *hash, + const struct GNUNET_CRYPTO_rsa_PublicKey *pkey, + size_t *rsize); + + int main (int argc, char *argv[]) @@ -42,6 +50,7 @@ main (int argc, struct GNUNET_HashCode hash; char *blind_buf; size_t bsize; + gcry_mpi_t v; GNUNET_log_setup ("test-rsa", "WARNING", NULL); GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_WEAK, @@ -55,11 +64,13 @@ main (int argc, GNUNET_assert (NULL != priv_copy); GNUNET_assert (0 == GNUNET_CRYPTO_rsa_private_key_cmp (priv, priv_copy)); pub = GNUNET_CRYPTO_rsa_private_key_get_public (priv); + /* Encoding */ size_t size; char *enc; enc = NULL; size = GNUNET_CRYPTO_rsa_private_key_encode (priv, &enc); + /* Decoding */ GNUNET_CRYPTO_rsa_private_key_free (priv); priv = NULL; @@ -71,10 +82,17 @@ main (int argc, (void) fprintf (stderr, "The above warning is expected.\n"); GNUNET_free (enc); + /* test full domain hash size */ + GNUNET_assert (0 == rsa_full_domain_hash (&v, &hash, pub, NULL)); + GNUNET_assert (gcry_mpi_get_nbits(v) < KEY_SIZE); + gcry_mpi_clear_highbit (v, gcry_mpi_get_nbits(v)-1); /* clear the set high bit */ + GNUNET_assert (gcry_mpi_get_nbits(v) > 3*KEY_SIZE/4); + /* This test necessarily randomly fails with probability 2^(3 - KEY_SIZE/4) */ + gcry_mpi_release(v); + /* try ordinary sig first */ - sig = GNUNET_CRYPTO_rsa_sign (priv, - &hash, - sizeof (hash)); + sig = GNUNET_CRYPTO_rsa_sign_fdh (priv, + &hash); sig_copy = GNUNET_CRYPTO_rsa_signature_dup (sig); GNUNET_assert (NULL != sig); GNUNET_assert (0 == GNUNET_CRYPTO_rsa_signature_cmp (sig, sig_copy)); @@ -91,7 +109,6 @@ main (int argc, (void) fprintf (stderr, "The above warning is expected.\n"); GNUNET_CRYPTO_rsa_signature_free (sig); - /* test blind signing */ bkey = GNUNET_CRYPTO_rsa_blinding_key_create (KEY_SIZE); bsize = GNUNET_CRYPTO_rsa_blind (&hash, @@ -99,16 +116,16 @@ main (int argc, pub, &blind_buf); GNUNET_assert (0 != bsize); - bsig = GNUNET_CRYPTO_rsa_sign (priv, - blind_buf, - bsize); + bsig = GNUNET_CRYPTO_rsa_sign_blinded (priv, + blind_buf, + bsize); GNUNET_free (blind_buf); sig = GNUNET_CRYPTO_rsa_unblind (bsig, bkey, pub); GNUNET_CRYPTO_rsa_signature_free (bsig); GNUNET_assert (GNUNET_OK == - GNUNET_CRYPTO_rsa_verify (&hash, sig, pub)); + GNUNET_CRYPTO_rsa_verify (&hash, sig, pub)); GNUNET_CRYPTO_rsa_signature_free (sig); GNUNET_CRYPTO_rsa_signature_free (sig_copy); GNUNET_CRYPTO_rsa_private_key_free (priv); -- 2.25.1