Verify that GCD(m,n) != 1 when n is an RSA modulus

Much thanks to CodesInChaos <codesinchaos@gmail.com> from the
cryptography@metzdowd.com list for observing this flaw!


On Tue, 2016-06-07 at 13:39 +0200, CodesInChaos wrote:
> How do you handle the case where GCD(m, n) != 1 where m is the message
> (i.e. the full domain hash) and n the modulus? Do you reject that
> message and generate a new one?


If I understand the attack you have in mind, it goes roughly :

First, an evil exchange creates a 2048 bit RSA key pq, but issues n = p
q r_1 r_2 ... r_k as say a 4096 bit RSA key where r_i is a smallish but
preferably not so obvious primes, like not 2, 3, or 5.  

Next, our evil exchange detects and records when the various r_i appear
during blinding and spending.  As m is 4096 bits, then some always do
since we took the r_i smallish. 

Each appearing r_i factor leaks I think several bits about the
customer's identity.  If enough coins are involved in a transaction,
especially say through repeated transactions, then the customer will
quickly be deanonymized. 


I could've fixed this in crypto_kdf.c but I descided it was specific
to RSA, so I did it when calling the KDF.  It should be abstracted
into a common routine probably.


Also fixes a pair of memory leaks.

1 files changed, 1 insertions, 0 deletions

diff --git a/src/util/crypto_kdf.c b/src/util/crypto_kdf.c
index 056fda529..c760ba33a 100644
--- a/src/util/crypto_kdf.c
+++ b/src/util/crypto_kdf.c
@@ -144,6 +144,7 @@ GNUNET_CRYPTO_kdf_mod_mpi (gcry_mpi_t *r,
     gcry_mpi_clear_highbit (*r, nbits);
     GNUNET_assert( 0 == gcry_mpi_test_bit (*r, nbits) );
     ++ctr;
+    /* We reject this FDH if either *r > n and retry with another ctr */
   } while ( 0 <= gcry_mpi_cmp(*r,n) );
 }