diff options
author | Jeff Burdges <burdges@gnunet.org> | 2016-06-07 18:32:25 +0000 |
---|---|---|
committer | Jeff Burdges <burdges@gnunet.org> | 2016-06-07 18:32:25 +0000 |
commit | 8459cba759d85ef512c8400ba7622332cf5ed652 (patch) | |
tree | 90fd91347337293d582f4b05120980f38acaa1ef /src | |
parent | 5bf0312a61434d78dec08859bf986bf5e1faa751 (diff) | |
download | gnunet-8459cba759d85ef512c8400ba7622332cf5ed652.tar.gz gnunet-8459cba759d85ef512c8400ba7622332cf5ed652.zip |
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.
Diffstat (limited to 'src')
-rw-r--r-- | src/util/crypto_kdf.c | 1 | ||||
-rw-r--r-- | src/util/crypto_rsa.c | 18 |
2 files changed, 19 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, | |||
144 | gcry_mpi_clear_highbit (*r, nbits); | 144 | gcry_mpi_clear_highbit (*r, nbits); |
145 | GNUNET_assert( 0 == gcry_mpi_test_bit (*r, nbits) ); | 145 | GNUNET_assert( 0 == gcry_mpi_test_bit (*r, nbits) ); |
146 | ++ctr; | 146 | ++ctr; |
147 | /* We reject this FDH if either *r > n and retry with another ctr */ | ||
147 | } while ( 0 <= gcry_mpi_cmp(*r,n) ); | 148 | } while ( 0 <= gcry_mpi_cmp(*r,n) ); |
148 | } | 149 | } |
149 | 150 | ||
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, | |||
406 | char *xts = "Blinding KDF extrator HMAC key"; /* Trusts bks' randomness more */ | 406 | char *xts = "Blinding KDF extrator HMAC key"; /* Trusts bks' randomness more */ |
407 | struct RsaBlindingKey *blind; | 407 | struct RsaBlindingKey *blind; |
408 | gcry_mpi_t n; | 408 | gcry_mpi_t n; |
409 | gcry_mpi_t g; | ||
409 | 410 | ||
410 | blind = GNUNET_new (struct RsaBlindingKey); | 411 | blind = GNUNET_new (struct RsaBlindingKey); |
411 | 412 | ||
@@ -418,6 +419,14 @@ rsa_blinding_key_derive (const struct GNUNET_CRYPTO_RsaPublicKey *pkey, | |||
418 | xts, strlen(xts), | 419 | xts, strlen(xts), |
419 | bks, sizeof(*bks), | 420 | bks, sizeof(*bks), |
420 | "Blinding KDF"); | 421 | "Blinding KDF"); |
422 | |||
423 | /* If gcd(*r,n) != 1 then n must be a malicious fake RSA key | ||
424 | designed to deanomize the user. */ | ||
425 | g = gcry_mpi_new (0); | ||
426 | GNUNET_assert( gcry_mpi_gcd(g,blind->r,n) ); | ||
427 | gcry_mpi_release (g); | ||
428 | |||
429 | gcry_mpi_release (n); | ||
421 | return blind; | 430 | return blind; |
422 | } | 431 | } |
423 | 432 | ||
@@ -652,6 +661,7 @@ rsa_full_domain_hash (gcry_mpi_t *r, | |||
652 | gcry_mpi_t n; | 661 | gcry_mpi_t n; |
653 | char *xts; | 662 | char *xts; |
654 | size_t xts_len; | 663 | size_t xts_len; |
664 | gcry_mpi_t g; | ||
655 | 665 | ||
656 | /* Extract the composite n from the RSA public key */ | 666 | /* Extract the composite n from the RSA public key */ |
657 | GNUNET_assert( 0 == key_from_sexp (&n, pkey->sexp, "rsa", "n") ); | 667 | GNUNET_assert( 0 == key_from_sexp (&n, pkey->sexp, "rsa", "n") ); |
@@ -670,6 +680,14 @@ rsa_full_domain_hash (gcry_mpi_t *r, | |||
670 | "RSA-FDA FTpsW!"); | 680 | "RSA-FDA FTpsW!"); |
671 | 681 | ||
672 | GNUNET_free (xts); | 682 | GNUNET_free (xts); |
683 | |||
684 | /* If gcd(*r,n) != 1 then n must be a malicious fake RSA key | ||
685 | designed to deanomize the user. */ | ||
686 | g = gcry_mpi_new (0); | ||
687 | GNUNET_assert( gcry_mpi_gcd(g,*r,n) ); | ||
688 | gcry_mpi_release (g); | ||
689 | |||
690 | gcry_mpi_release (n); | ||
673 | } | 691 | } |
674 | 692 | ||
675 | 693 | ||