[GNUnet-SVN] r37254 - gnunet/src/util

[gnunet]

Author: burdges
Date: 2016-06-07 20:32:25 +0200 (Tue, 07 Jun 2016)
New Revision: 37254

Modified:
   gnunet/src/util/crypto_kdf.c
   gnunet/src/util/crypto_rsa.c
Log:
Verify that GCD(m,n) != 1 when n is an RSA modulus

Much thanks to CodesInChaos <address@hidden> from the
address@hidden 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.



Modified: gnunet/src/util/crypto_kdf.c
===================================================================
--- gnunet/src/util/crypto_kdf.c        2016-06-07 14:48:05 UTC (rev 37253)
+++ gnunet/src/util/crypto_kdf.c        2016-06-07 18:32:25 UTC (rev 37254)
@@ -144,6 +144,7 @@
     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) );
 }
 

Modified: gnunet/src/util/crypto_rsa.c
===================================================================
--- gnunet/src/util/crypto_rsa.c        2016-06-07 14:48:05 UTC (rev 37253)
+++ gnunet/src/util/crypto_rsa.c        2016-06-07 18:32:25 UTC (rev 37254)
@@ -406,6 +406,7 @@
   char *xts = "Blinding KDF extrator HMAC key";  /* Trusts bks' randomness 
more */
   struct RsaBlindingKey *blind;
   gcry_mpi_t n;
+  gcry_mpi_t g;
 
   blind = GNUNET_new (struct RsaBlindingKey);
 
@@ -418,6 +419,14 @@
                              xts,  strlen(xts),
                              bks,  sizeof(*bks),
                              "Blinding KDF");
+
+  /* If gcd(*r,n) != 1 then n must be a malicious fake RSA key
+     designed to deanomize the user. */
+  g = gcry_mpi_new (0);
+  GNUNET_assert( gcry_mpi_gcd(g,blind->r,n) );
+  gcry_mpi_release (g);
+
+  gcry_mpi_release (n);
   return blind;
 }
 
@@ -652,6 +661,7 @@
   gcry_mpi_t n;
   char *xts;
   size_t xts_len;
+  gcry_mpi_t g;
 
   /* Extract the composite n from the RSA public key */
   GNUNET_assert( 0 == key_from_sexp (&n, pkey->sexp, "rsa", "n") );
@@ -670,6 +680,14 @@
                              "RSA-FDA FTpsW!");
 
   GNUNET_free (xts);
+
+  /* If gcd(*r,n) != 1 then n must be a malicious fake RSA key
+     designed to deanomize the user. */
+  g = gcry_mpi_new (0);
+  GNUNET_assert( gcry_mpi_gcd(g,*r,n) );
+  gcry_mpi_release (g);
+
+  gcry_mpi_release (n);
 }