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, 64 insertions, 4 deletions

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 <burdges@gnunet.org>
  */
 
 #include <gcrypt.h>
@@ -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) );
+}
+
+