Use a uniform random number mod an RSA composites for both
authorJeff Burdges <burdges@gnunet.org>
Mon, 30 May 2016 15:54:56 +0000 (15:54 +0000)
committerJeff Burdges <burdges@gnunet.org>
Mon, 30 May 2016 15:54:56 +0000 (15:54 +0000)
commitafb40a6d7a49d2608b709d6e8863675a6a301c99
tree26c97c0217311d2313ecac5daa853d428ecf9025
parent295a7ab56564369098a12e2cc39fac0d5225c465
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
src/util/crypto_kdf.c
src/util/crypto_rsa.c
src/util/test_crypto_rsa.c