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, 18 insertions, 0 deletions

diff --git a/src/util/crypto_rsa.c b/src/util/crypto_rsa.c
index ae96a99ad..c09daa412 100644
--- a/src/util/crypto_rsa.c
+++ b/src/util/crypto_rsa.c
@@ -406,6 +406,7 @@ rsa_blinding_key_derive (const struct GNUNET_CRYPTO_RsaPublicKey *pkey,
   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 @@ rsa_blinding_key_derive (const struct GNUNET_CRYPTO_RsaPublicKey *pkey,
                              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 @@ rsa_full_domain_hash (gcry_mpi_t *r,
   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_full_domain_hash (gcry_mpi_t *r,
                              "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);
 }