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.

1 files changed, 1 insertions, 16 deletions

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 <sreeharsha@totakura.in>
+ * @author Jeffrey Burdges <burdges@gnunet.org>
  */
 #include "platform.h"
 #include <gcrypt.h>
@@ -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);