#include <gcrypt.h>
#include "gnunet_crypto_lib.h"
-#define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
+#define LOG(kind,...) GNUNET_log_from (kind, "util-crypto-rsa", __VA_ARGS__)
/**
}
+/**
+ * Test for malicious RSA key.
+ *
+ * Assuming n is an RSA modulous and r is generated using a call to
+ * GNUNET_CRYPTO_kdf_mod_mpi, if gcd(r,n) != 1 then n must be a
+ * malicious RSA key designed to deanomize the user.
+ *
+ * @param r KDF result
+ * @param n RSA modulus
+ * @return True if gcd(r,n) = 1, False means RSA key is malicious
+ */
+static int
+rsa_gcd_validate(gcry_mpi_t r, gcry_mpi_t n)
+{
+ gcry_mpi_t g;
+ int t;
+
+ g = gcry_mpi_new (0);
+ t = gcry_mpi_gcd(g,r,n);
+ gcry_mpi_release (g);
+ return t;
+}
+
+
/**
* Create a blinding key
*
* @param len length of the key in bits (i.e. 2048)
* @param bks pre-secret to use to derive the blinding key
- * @return the newly created blinding key
+ * @return the newly created blinding key, NULL if RSA key is malicious
*/
static struct RsaBlindingKey *
rsa_blinding_key_derive (const struct GNUNET_CRYPTO_RsaPublicKey *pkey,
gcry_mpi_t n;
blind = GNUNET_new (struct RsaBlindingKey);
+ GNUNET_assert( NULL != blind );
/* Extract the composite n from the RSA public key */
GNUNET_assert( 0 == key_from_sexp (&n, pkey->sexp, "rsa", "n") );
+ /* Assert that it at least looks like an RSA key */
GNUNET_assert( 0 == gcry_mpi_get_flag(n, GCRYMPI_FLAG_OPAQUE) );
GNUNET_CRYPTO_kdf_mod_mpi (&blind->r,
xts, strlen(xts),
bks, sizeof(*bks),
"Blinding KDF");
+ if (0 == rsa_gcd_validate(blind->r, n)) {
+ GNUNET_free (blind);
+ blind = NULL;
+ }
+
+ gcry_mpi_release (n);
return blind;
}
+/*
+We originally added GNUNET_CRYPTO_kdf_mod_mpi for the benifit of the
+previous routine.
+
+There was previously 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 feared 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.
+
+We fixed this by using a more uniform deterministic pseudo-random number
+generator for blinding factors. I do not believe this to be a problem
+for the rsa_full_domain_hash routine, but better safe than sorry.
+*/
+
+
/**
* Compare the values of two signatures.
*
* https://eprint.iacr.org/2001/002.pdf
* http://www.di.ens.fr/~pointche/Documents/Papers/2001_fcA.pdf
*
- * @param[out] r MPI value set to the FDH
* @param hash initial hash of the message to sign
* @param pkey the public key of the signer
* @param rsize If not NULL, the number of bytes actually stored in buffer
+ * @return MPI value set to the FDH, NULL if RSA key is malicious
*/
-static void
-rsa_full_domain_hash (gcry_mpi_t *r,
- const struct GNUNET_HashCode *hash,
- const struct GNUNET_CRYPTO_RsaPublicKey *pkey)
+static gcry_mpi_t
+rsa_full_domain_hash (const struct GNUNET_CRYPTO_RsaPublicKey *pkey,
+ const struct GNUNET_HashCode *hash)
{
- gcry_mpi_t n;
+ gcry_mpi_t r,n;
char *xts;
size_t xts_len;
+ int ok;
/* Extract the composite n from the RSA public key */
GNUNET_assert( 0 == key_from_sexp (&n, pkey->sexp, "rsa", "n") );
+ /* Assert that it at least looks like an RSA key */
GNUNET_assert( 0 == gcry_mpi_get_flag(n, GCRYMPI_FLAG_OPAQUE) );
/* We key with the public denomination key as a homage to RSA-PSS by *
* polynomial-time one-more forgary attack. Yey seeding! */
xts_len = GNUNET_CRYPTO_rsa_public_key_encode (pkey, &xts);
- GNUNET_CRYPTO_kdf_mod_mpi (r,
+ GNUNET_CRYPTO_kdf_mod_mpi (&r,
n,
xts, xts_len,
hash, sizeof(*hash),
"RSA-FDA FTpsW!");
-
GNUNET_free (xts);
+
+ ok = rsa_gcd_validate(r,n);
+ gcry_mpi_release (n);
+ if (ok)
+ return r;
+ gcry_mpi_release (r);
+ return NULL;
}
* @param hash hash of the message to sign
* @param bkey the blinding key
* @param pkey the public key of the signer
- * @param[out] buffer set to a buffer with the blinded message to be signed
- * @return number of bytes stored in @a buffer
+ * @param[out] buf set to a buffer with the blinded message to be signed
+ * @param[out] buf_size number of bytes stored in @a buf
+ * @return GNUNET_YES if successful, GNUNET_NO if RSA key is malicious
*/
-size_t
+int
GNUNET_CRYPTO_rsa_blind (const struct GNUNET_HashCode *hash,
const struct GNUNET_CRYPTO_RsaBlindingKeySecret *bks,
struct GNUNET_CRYPTO_RsaPublicKey *pkey,
- char **buffer)
+ char **buf, size_t *buf_size)
{
struct RsaBlindingKey *bkey;
gcry_mpi_t data;
gcry_mpi_t ne[2];
gcry_mpi_t r_e;
gcry_mpi_t data_r_e;
- size_t n;
int ret;
+ GNUNET_assert (buf != NULL && buf_size != NULL);
ret = key_from_sexp (ne, pkey->sexp, "public-key", "ne");
if (0 != ret)
ret = key_from_sexp (ne, pkey->sexp, "rsa", "ne");
if (0 != ret)
{
GNUNET_break (0);
- *buffer = NULL;
+ *buf = NULL;
+ *buf_size = 0;
return 0;
}
- rsa_full_domain_hash (&data, hash, pkey);
- bkey = rsa_blinding_key_derive (pkey,
- bks);
+ data = rsa_full_domain_hash (pkey, hash);
+ if (NULL == data)
+ goto rsa_gcd_validate_failure;
+
+ bkey = rsa_blinding_key_derive (pkey, bks);
+ if (NULL == bkey) {
+ gcry_mpi_release (data);
+ goto rsa_gcd_validate_failure;
+ }
+
r_e = gcry_mpi_new (0);
gcry_mpi_powm (r_e,
bkey->r,
gcry_mpi_release (ne[0]);
gcry_mpi_release (ne[1]);
gcry_mpi_release (r_e);
- rsa_blinding_key_free (bkey);
+ rsa_blinding_key_free (bkey);
- n = numeric_mpi_alloc_n_print (data_r_e, buffer);
+ *buf_size = numeric_mpi_alloc_n_print (data_r_e, buf);
gcry_mpi_release (data_r_e);
- return n;
+ return GNUNET_YES;
+
+rsa_gcd_validate_failure:
+ /* We know the RSA key is malicious here, so warn the wallet. */
+ /* GNUNET_break_op (0); */
+ gcry_mpi_release (ne[0]);
+ gcry_mpi_release (ne[1]);
+ *buf = NULL;
+ *buf_size = 0;
+ return GNUNET_NO;
}
gcry_mpi_t value)
{
struct GNUNET_CRYPTO_RsaSignature *sig;
- struct GNUNET_CRYPTO_RsaPublicKey *public_key;
gcry_sexp_t data;
gcry_sexp_t result;
int rc;
return NULL;
}
+ /* Lenstra protection was first added to libgcrypt 1.6.4
+ * with commit c17f84bd02d7ee93845e92e20f6ddba814961588.
+ */
+#if GCRYPT_VERSION_NUMBER < 0x010604
/* verify signature (guards against Lenstra's attack with fault injection...) */
- public_key = GNUNET_CRYPTO_rsa_private_key_get_public (key);
+ struct GNUNET_CRYPTO_RsaPublicKey *public_key = GNUNET_CRYPTO_rsa_private_key_get_public (key);
if (0 !=
gcry_pk_verify (result,
data,
return NULL;
}
GNUNET_CRYPTO_rsa_public_key_free (public_key);
+#endif
/* return signature */
gcry_sexp_release (data);
*
* @param key private key to use for the signing
* @param hash the hash of the message to sign
- * @return NULL on error, signature on success
+ * @return NULL on error, including a malicious RSA key, signature on success
*/
struct GNUNET_CRYPTO_RsaSignature *
GNUNET_CRYPTO_rsa_sign_fdh (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
struct GNUNET_CRYPTO_RsaSignature *sig;
pkey = GNUNET_CRYPTO_rsa_private_key_get_public (key);
- rsa_full_domain_hash (&v, hash, pkey);
+ v = rsa_full_domain_hash (pkey, hash);
GNUNET_CRYPTO_rsa_public_key_free (pkey);
+ if (NULL == v) /* rsa_gcd_validate failed meaning */
+ return NULL; /* our *own* RSA key is malicious. */
sig = rsa_sign_mpi (key, v);
gcry_mpi_release (v);
return sig;
-
}
* @param sig the signature made on the blinded signature purpose
* @param bks the blinding key secret used to blind the signature purpose
* @param pkey the public key of the signer
- * @return unblinded signature on success, NULL on error
+ * @return unblinded signature on success, NULL if RSA key is bad or malicious.
*/
struct GNUNET_CRYPTO_RsaSignature *
GNUNET_CRYPTO_rsa_unblind (struct GNUNET_CRYPTO_RsaSignature *sig,
GNUNET_break_op (0);
return NULL;
}
- bkey = rsa_blinding_key_derive (pkey,
- bks);
+
+ bkey = rsa_blinding_key_derive (pkey, bks);
+ if (NULL == bkey)
+ {
+ /* RSA key is malicious since rsa_gcd_validate failed here.
+ * It should have failed during GNUNET_CRYPTO_rsa_blind too though,
+ * so the exchange is being malicious in an unfamilair way, maybe
+ * just trying to crash us. */
+ GNUNET_break_op (0);
+ gcry_mpi_release (n);
+ gcry_mpi_release (s);
+ return NULL;
+ }
r_inv = gcry_mpi_new (0);
if (1 !=
bkey->r,
n))
{
+ /* We cannot find r mod n, so gcd(r,n) != 1, which should get *
+ * caught above, but we handle it the same here. */
GNUNET_break_op (0);
- gcry_mpi_release (n);
gcry_mpi_release (r_inv);
+ rsa_blinding_key_free (bkey);
+ gcry_mpi_release (n);
gcry_mpi_release (s);
- rsa_blinding_key_free (bkey);
return NULL;
}
+
ubsig = gcry_mpi_new (0);
gcry_mpi_mulm (ubsig, s, r_inv, n);
gcry_mpi_release (n);
/**
- * Verify whether the given hash corresponds to the given signature and the
- * signature is valid with respect to the given public key.
+ * Verify whether the given hash corresponds to the given signature and
+ * the signature is valid with respect to the given public key.
*
* @param hash hash of the message to verify to match the @a sig
* @param sig signature that is being validated
* @param pkey public key of the signer
- * @returns #GNUNET_OK if ok, #GNUNET_SYSERR if invalid
+ * @returns #GNUNET_YES if ok, #GNUNET_NO if RSA key is malicious, #GNUNET_SYSERR if signature is invalid
*/
int
GNUNET_CRYPTO_rsa_verify (const struct GNUNET_HashCode *hash,
gcry_mpi_t r;
int rc;
- rsa_full_domain_hash (&r, hash, pkey);
+ r = rsa_full_domain_hash (pkey, hash);
+ if (NULL == r) {
+ GNUNET_break_op (0);
+ /* RSA key is malicious since rsa_gcd_validate failed here.
+ * It should have failed during GNUNET_CRYPTO_rsa_blind too though,
+ * so the exchange is being malicious in an unfamilair way, maybe
+ * just trying to crash us. Arguably, we've only an internal error
+ * though because we should've detected this in our previous call
+ * to GNUNET_CRYPTO_rsa_unblind. */
+ return GNUNET_NO;
+ }
+
data = mpi_to_sexp(r);
gcry_mpi_release (r);
projects / oweals / gnunet.git / blobdiff