From afb40a6d7a49d2608b709d6e8863675a6a301c99 Mon Sep 17 00:00:00 2001 From: Jeff Burdges Date: Mon, 30 May 2016 15:54:56 +0000 Subject: [PATCH] Use a uniform random number mod an RSA composites for both the blinding factor and the full domain hash. This resolves an attack against the blinding factor in Taler: There was a call to GNUNET_CRYPTO_kdf in bkey = rsa_blinding_key_derive (len, bks); that gives exactly len bits where len = GNUNET_CRYPTO_rsa_public_key_len (pkey); Now r = 2^(len-1)/pkey.n is the probability that a set high bit being okay, meaning bkey < pkey.n. It follows that (1-r)/2 of the time bkey > pkey.n making the effective bkey be bkey mod pkey.n = bkey - pkey.n so the effective bkey has its high bit set with probability r/2. We expect r to be close to 1/2 if the exchange is honest, but the exchange can choose r otherwise. In blind signing, the exchange sees B = bkey * S mod pkey.n On deposit, the exchange sees S so they can compute bkey' = B/S mod pkey.n for all B they recorded to see if bkey' has it's high bit set. Also, note the exchange can compute 1/S efficiently since they know the factors of pkey.n. I suppose that happens with probability r/(1+r) if its the wrong B, not completely sure. If otoh we've the right B, then we've the probability r/2 of a set high bit in the effective bkey. Interestingly, r^2-r has a maximum at the default r=1/2 anyways, giving the wrong and right probabilities 1/3 and 1/4, respectively. I fear this gives the exchange a meaningful fraction of a bit of information per coin involved in the transaction. It sounds damaging if numerous coins were involved. And it could run across transactions in some scenarios. I suspect we need a more uniform deterministic pseudo-random number generator for blinding factors. Just fyi, our old call to gcry_mpi_randomize had this same problem. I do not believe this caused a problem for the full domain hash, but we can fix it easily enough anyways. --- src/include/gnunet_crypto_lib.h | 21 ++++ src/util/crypto_kdf.c | 68 ++++++++++++- src/util/crypto_rsa.c | 173 ++++++++------------------------ src/util/test_crypto_rsa.c | 17 +--- 4 files changed, 130 insertions(+), 149 deletions(-) diff --git a/src/include/gnunet_crypto_lib.h b/src/include/gnunet_crypto_lib.h index bd95ad3c3..32503eaf8 100644 --- a/src/include/gnunet_crypto_lib.h +++ b/src/include/gnunet_crypto_lib.h @@ -27,6 +27,7 @@ * @author Gerd Knorr * @author Ioana Patrascu * @author Tzvetan Horozov + * @author Jeffrey Burdges * * @defgroup crypto Crypto library: cryptographic operations * Provides cryptographic primitives. @@ -1014,6 +1015,26 @@ GNUNET_CRYPTO_kdf_v (void *result, va_list argp); +/** + * Deterministically generate a pseudo-random number uniformly from the + * integers modulo a libgcrypt mpi. + * + * @param[out] r MPI value set to the FDH + * @param n MPI to work modulo + * @param xts salt + * @param xts_len length of @a xts + * @param skm source key material + * @param skm_len length of @a skm + * @param ctx context string + */ +void +GNUNET_CRYPTO_kdf_mod_mpi (gcry_mpi_t *r, + gcry_mpi_t n, + const void *xts, size_t xts_len, + const void *skm, size_t skm_len, + const char *ctx); + + /** * @ingroup hash * @brief Derive key diff --git a/src/util/crypto_kdf.c b/src/util/crypto_kdf.c index 242fbf296..056fda529 100644 --- a/src/util/crypto_kdf.c +++ b/src/util/crypto_kdf.c @@ -22,6 +22,7 @@ * @file src/util/crypto_kdf.c * @brief Key derivation * @author Nils Durner + * @author Jeffrey Burdges */ #include @@ -43,8 +44,9 @@ * @return #GNUNET_YES on success */ int -GNUNET_CRYPTO_kdf_v (void *result, size_t out_len, const void *xts, - size_t xts_len, const void *skm, size_t skm_len, +GNUNET_CRYPTO_kdf_v (void *result, size_t out_len, + const void *xts, size_t xts_len, + const void *skm, size_t skm_len, va_list argp) { /* @@ -76,8 +78,9 @@ GNUNET_CRYPTO_kdf_v (void *result, size_t out_len, const void *xts, * @return #GNUNET_YES on success */ int -GNUNET_CRYPTO_kdf (void *result, size_t out_len, const void *xts, - size_t xts_len, const void *skm, size_t skm_len, ...) +GNUNET_CRYPTO_kdf (void *result, size_t out_len, + const void *xts, size_t xts_len, + const void *skm, size_t skm_len, ...) { va_list argp; int ret; @@ -88,3 +91,60 @@ GNUNET_CRYPTO_kdf (void *result, size_t out_len, const void *xts, return ret; } + + +/** + * Deterministically generate a pseudo-random number uniformly from the + * integers modulo a libgcrypt mpi. + * + * @param[out] r MPI value set to the FDH + * @param n MPI to work modulo + * @param xts salt + * @param xts_len length of @a xts + * @param skm source key material + * @param skm_len length of @a skm + * @param ctx context string + */ +void +GNUNET_CRYPTO_kdf_mod_mpi (gcry_mpi_t *r, + gcry_mpi_t n, + const void *xts, size_t xts_len, + const void *skm, size_t skm_len, + const char *ctx) +{ + gcry_error_t rc; + unsigned int nbits; + size_t rsize; + unsigned int ctr; + + nbits = gcry_mpi_get_nbits (n); + /* GNUNET_assert (nbits > 512); */ + + ctr = 0; + do { + /* Ain't clear if n is always divisible by 8 */ + uint8_t buf[ (nbits-1)/8 + 1 ]; + + rc = GNUNET_CRYPTO_kdf (buf, + sizeof (buf), + xts, xts_len, + skm, skm_len, + ctx, strlen(ctx), + &ctr, sizeof(ctr), + NULL, 0); + GNUNET_assert (GNUNET_YES == rc); + + rc = gcry_mpi_scan (r, + GCRYMPI_FMT_USG, + (const unsigned char *) buf, + sizeof (buf), + &rsize); + GNUNET_assert (0 == rc); /* Allocation erro? */ + + gcry_mpi_clear_highbit (*r, nbits); + GNUNET_assert( 0 == gcry_mpi_test_bit (*r, nbits) ); + ++ctr; + } while ( 0 <= gcry_mpi_cmp(*r,n) ); +} + + diff --git a/src/util/crypto_rsa.c b/src/util/crypto_rsa.c index ab3ce6fe7..4415f20f6 100644 --- a/src/util/crypto_rsa.c +++ b/src/util/crypto_rsa.c @@ -400,31 +400,24 @@ GNUNET_CRYPTO_rsa_public_key_decode (const char *buf, * @return the newly created blinding key */ static struct RsaBlindingKey * -rsa_blinding_key_derive (unsigned int len, +rsa_blinding_key_derive (const struct GNUNET_CRYPTO_RsaPublicKey *pkey, const struct GNUNET_CRYPTO_RsaBlindingKeySecret *bks) { + char *xts = "Blinding KDF extrator HMAC key"; /* Trusts bks' randomness more */ struct RsaBlindingKey *blind; - uint8_t buf[len / 8]; - int rc; - size_t rsize; + gcry_mpi_t n; blind = GNUNET_new (struct RsaBlindingKey); - /* FIXME: #4483: actually derive key from bks! - Jeff, - check that you're happy with this!*/ - GNUNET_assert (GNUNET_YES == - GNUNET_CRYPTO_kdf (buf, - sizeof (buf), - "blinding-kdf", - strlen ("blinding-kdf"), - bks, - sizeof (*bks), - NULL, 0)); - rc = gcry_mpi_scan (&blind->r, - GCRYMPI_FMT_USG, - (const unsigned char *) buf, - sizeof (buf), - &rsize); - GNUNET_assert (0 == rc); + + /* Extract the composite n from the RSA public key */ + GNUNET_assert( 0 == key_from_sexp (&n, pkey->sexp, "rsa", "n") ); + GNUNET_assert( 0 == gcry_mpi_get_flag(n, GCRYMPI_FLAG_OPAQUE) ); + + GNUNET_CRYPTO_kdf_mod_mpi (&blind->r, + n, + xts, strlen(xts), + bks, sizeof(*bks), + "Blinding KDF"); return blind; } @@ -538,13 +531,10 @@ unsigned int GNUNET_CRYPTO_rsa_public_key_len (const struct GNUNET_CRYPTO_RsaPublicKey *key) { gcry_mpi_t n; - int ret; unsigned int rval; - ret = key_from_sexp (&n, key->sexp, "rsa", "n"); - if (0 != ret) - { - /* this is no public RSA key */ + if (0 != key_from_sexp (&n, key->sexp, "rsa", "n")) + { /* Not an RSA public key */ GNUNET_break (0); return 0; } @@ -610,91 +600,33 @@ numeric_mpi_alloc_n_print (gcry_mpi_t v, * @param hash initial hash of the message to sign * @param pkey the public key of the signer * @param rsize If not NULL, the number of bytes actually stored in buffer - * @return libgcrypt error that to represent an allocation failure */ -/* FIXME: exported symbol without proper prefix... */ -gcry_error_t +static void rsa_full_domain_hash (gcry_mpi_t *r, - const struct GNUNET_HashCode *hash, - const struct GNUNET_CRYPTO_RsaPublicKey *pkey, - size_t *rsize) + const struct GNUNET_HashCode *hash, + const struct GNUNET_CRYPTO_RsaPublicKey *pkey) { - unsigned int i; - unsigned int nbits; - unsigned int nhashes; - gcry_error_t rc; - char *buf; - size_t buf_len; - gcry_md_hd_t h; - gcry_md_hd_t 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); - 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 = GNUNET_new_array (nhashes, - struct GNUNET_HashCode); - for (i=0; isexp, "rsa", "n") ); + GNUNET_assert( 0 == gcry_mpi_get_flag(n, GCRYMPI_FLAG_OPAQUE) ); + + /* We key 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! */ + xts_len = GNUNET_CRYPTO_rsa_public_key_encode (pkey, &xts); + + GNUNET_CRYPTO_kdf_mod_mpi (r, + n, + xts, xts_len, + hash, sizeof(*hash), + "RSA-FDA FTpsW!"); + + GNUNET_free (xts); } @@ -718,11 +650,8 @@ GNUNET_CRYPTO_rsa_blind (const struct GNUNET_HashCode *hash, gcry_mpi_t ne[2]; gcry_mpi_t r_e; gcry_mpi_t data_r_e; - size_t rsize; size_t n; - gcry_error_t rc; int ret; - unsigned int len; ret = key_from_sexp (ne, pkey->sexp, "public-key", "ne"); if (0 != ret) @@ -734,17 +663,8 @@ GNUNET_CRYPTO_rsa_blind (const struct GNUNET_HashCode *hash, return 0; } - rc = rsa_full_domain_hash (&data, hash, pkey, &rsize); - if (0 != rc) /* Allocation error in libgcrypt */ - { - GNUNET_break (0); - gcry_mpi_release (ne[0]); - gcry_mpi_release (ne[1]); - *buffer = NULL; - return 0; - } - len = GNUNET_CRYPTO_rsa_public_key_len (pkey); - bkey = rsa_blinding_key_derive (len, + rsa_full_domain_hash (&data, hash, pkey); + bkey = rsa_blinding_key_derive (pkey, bks); r_e = gcry_mpi_new (0); gcry_mpi_powm (r_e, @@ -886,13 +806,11 @@ GNUNET_CRYPTO_rsa_sign_fdh (const struct GNUNET_CRYPTO_RsaPrivateKey *key, { struct GNUNET_CRYPTO_RsaPublicKey *pkey; gcry_mpi_t v = NULL; - gcry_error_t rc; struct GNUNET_CRYPTO_RsaSignature *sig; pkey = GNUNET_CRYPTO_rsa_private_key_get_public (key); - rc = rsa_full_domain_hash (&v, hash, pkey, NULL); + rsa_full_domain_hash (&v, hash, pkey); GNUNET_CRYPTO_rsa_public_key_free (pkey); - GNUNET_assert (0 == rc); sig = rsa_sign_mpi (key, v); gcry_mpi_release (v); @@ -1034,7 +952,6 @@ GNUNET_CRYPTO_rsa_unblind (struct GNUNET_CRYPTO_RsaSignature *sig, gcry_mpi_t ubsig; int ret; struct GNUNET_CRYPTO_RsaSignature *sret; - unsigned int len; ret = key_from_sexp (&n, pkey->sexp, "public-key", "n"); if (0 != ret) @@ -1053,8 +970,7 @@ GNUNET_CRYPTO_rsa_unblind (struct GNUNET_CRYPTO_RsaSignature *sig, GNUNET_break_op (0); return NULL; } - len = GNUNET_CRYPTO_rsa_public_key_len (pkey); - bkey = rsa_blinding_key_derive (len, + bkey = rsa_blinding_key_derive (pkey, bks); r_inv = gcry_mpi_new (0); @@ -1106,8 +1022,7 @@ GNUNET_CRYPTO_rsa_verify (const struct GNUNET_HashCode *hash, gcry_mpi_t r; int rc; - rc = rsa_full_domain_hash (&r, hash, pkey, NULL); - GNUNET_assert (0 == rc); /* Allocation error in libgcrypt */ + rsa_full_domain_hash (&r, hash, pkey); data = mpi_to_sexp(r); gcry_mpi_release (r); diff --git a/src/util/test_crypto_rsa.c b/src/util/test_crypto_rsa.c index 2abb008e2..d346bdae8 100644 --- a/src/util/test_crypto_rsa.c +++ b/src/util/test_crypto_rsa.c @@ -18,6 +18,7 @@ * @file util/test_crypto_rsa.c * @brief testcase for utility functions for RSA cryptography * @author Sree Harsha Totakura + * @author Jeffrey Burdges */ #include "platform.h" #include @@ -26,13 +27,6 @@ #define KEY_SIZE 1024 -gcry_error_t -rsa_full_domain_hash (gcry_mpi_t *r, - const struct GNUNET_HashCode *hash, - const struct GNUNET_CRYPTO_RsaPublicKey *pkey, - size_t *rsize); - - int main (int argc, char *argv[]) @@ -50,7 +44,6 @@ 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, @@ -82,14 +75,6 @@ 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_fdh (priv, &hash); -- 2.25.1