/*
This file is part of GNUnet
- Copyright (C) 2014 GNUnet e.V.
+ Copyright (C) 2014,2016 GNUnet e.V.
GNUnet is free software; you can redistribute it and/or modify it under the
terms of the GNU General Public License as published by the Free Software
* @brief Chaum-style Blind signatures based on RSA
* @author Sree Harsha Totakura <sreeharsha@totakura.in>
* @author Christian Grothoff
+ * @author Jeffrey Burdges <burdges@gnunet.org>
*/
#include "platform.h"
#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__)
/**
/**
* @brief RSA blinding key
*/
-struct GNUNET_CRYPTO_rsa_BlindingKey
+struct RsaBlindingKey
{
/**
* Random value used for blinding.
/**
- * Create a blinding key
+ * Test for malicious RSA key.
*
- * @param len length of the key in bits (i.e. 2048)
- * @return the newly created blinding 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
*/
-struct GNUNET_CRYPTO_rsa_BlindingKey *
-GNUNET_CRYPTO_rsa_blinding_key_create (unsigned int len)
+static int
+rsa_gcd_validate(gcry_mpi_t r, gcry_mpi_t n)
{
- struct GNUNET_CRYPTO_rsa_BlindingKey *blind;
+ gcry_mpi_t g;
+ int t;
- blind = GNUNET_new (struct GNUNET_CRYPTO_rsa_BlindingKey);
- blind->r = gcry_mpi_new (len);
- gcry_mpi_randomize (blind->r,
- len,
- GCRY_STRONG_RANDOM);
- return blind;
+ g = gcry_mpi_new (0);
+ t = gcry_mpi_gcd(g,r,n);
+ gcry_mpi_release (g);
+ return t;
}
/**
- * Compare the values of two blinding keys.
+ * Create a blinding key
*
- * @param b1 one key
- * @param b2 the other key
- * @return 0 if the two are equal
+ * @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, NULL if RSA key is malicious
*/
-int
-GNUNET_CRYPTO_rsa_blinding_key_cmp (struct GNUNET_CRYPTO_rsa_BlindingKey *b1,
- struct GNUNET_CRYPTO_rsa_BlindingKey *b2)
+static struct RsaBlindingKey *
+rsa_blinding_key_derive (const struct GNUNET_CRYPTO_RsaPublicKey *pkey,
+ const struct GNUNET_CRYPTO_RsaBlindingKeySecret *bks)
{
- return gcry_mpi_cmp (b1->r,
- b2->r);
+ char *xts = "Blinding KDF extrator HMAC key"; /* Trusts bks' randomness more */
+ struct RsaBlindingKey *blind;
+ 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,
+ n,
+ 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.
*
GNUNET_CRYPTO_rsa_public_key_len (const struct GNUNET_CRYPTO_RsaPublicKey *key)
{
gcry_mpi_t n;
- int ret;
unsigned int rval;
- ret = key_from_sexp (&n, key->sexp, "rsa", "n");
- if (0 != ret)
- {
- /* this is no public RSA key */
+ if (0 != key_from_sexp (&n, key->sexp, "rsa", "n"))
+ { /* Not an RSA public key */
GNUNET_break (0);
return 0;
}
*
* @param bkey the blinding key to destroy
*/
-void
-GNUNET_CRYPTO_rsa_blinding_key_free (struct GNUNET_CRYPTO_rsa_BlindingKey *bkey)
+static void
+rsa_blinding_key_free (struct RsaBlindingKey *bkey)
{
gcry_mpi_release (bkey->r);
GNUNET_free (bkey);
* Print an MPI to a newly created buffer
*
* @param v MPI to print.
- * @param[out] buffer set to a buffer with the result
+ * @param[out] newly allocated buffer containing the result
* @return number of bytes stored in @a buffer
*/
static size_t
-mpi_print (gcry_mpi_t v,
- char **buffer)
+numeric_mpi_alloc_n_print (gcry_mpi_t v,
+ char **buffer)
{
size_t n;
char *b;
}
-/**
- * Encode the blinding key in a format suitable for
- * storing it into a file.
- *
- * @param bkey the blinding key
- * @param[out] buffer set to a buffer with the encoded key
- * @return size of memory allocated in @a buffer
- */
-size_t
-GNUNET_CRYPTO_rsa_blinding_key_encode (const struct GNUNET_CRYPTO_rsa_BlindingKey *bkey,
- char **buffer)
-{
- return mpi_print (bkey->r, buffer);
-}
-
-
-/**
- * Decode the blinding key from the data-format back
- * to the "normal", internal format.
- *
- * @param buf the buffer where the public key data is stored
- * @param len the length of the data in @a buf
- * @return NULL on error
- */
-struct GNUNET_CRYPTO_rsa_BlindingKey *
-GNUNET_CRYPTO_rsa_blinding_key_decode (const char *buf,
- size_t len)
-{
- struct GNUNET_CRYPTO_rsa_BlindingKey *bkey;
- size_t rsize;
-
- bkey = GNUNET_new (struct GNUNET_CRYPTO_rsa_BlindingKey);
- if (0 !=
- gcry_mpi_scan (&bkey->r,
- GCRYMPI_FMT_USG,
- (const unsigned char *) buf,
- len,
- &rsize))
- {
- GNUNET_break_op (0);
- GNUNET_free (bkey);
- return NULL;
- }
- return bkey;
-}
-
-
/**
* Computes a full domain hash seeded by the given public key.
* This gives a measure of provable security to the Taler exchange
* 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 FIXME JEFF
- * @return libgcrypt error that to represent an allocation failure
+ * @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
*/
-gcry_error_t
-rsa_full_domain_hash (gcry_mpi_t *r,
- const struct GNUNET_HashCode *hash,
- const struct GNUNET_CRYPTO_RsaPublicKey *pkey,
- size_t *rsize)
+static gcry_mpi_t
+rsa_full_domain_hash (const struct GNUNET_CRYPTO_RsaPublicKey *pkey,
+ const struct GNUNET_HashCode *hash)
{
- unsigned int i;
- unsigned int nbits;
- unsigned int nhashes;
- gcry_error_t rc;
- char *buf;
- size_t buf_len;
- gcry_md_hd_t h;
- gcry_md_hd_t h0;
- struct GNUNET_HashCode *hs;
-
- /* Uncomment the following to debug without using the full domain hash */
- /*
- rc = gcry_mpi_scan (r,
- GCRYMPI_FMT_USG,
- (const unsigned char *)hash,
- sizeof(struct GNUNET_HashCode),
- rsize);
- return rc;
- */
-
- nbits = GNUNET_CRYPTO_rsa_public_key_len (pkey);
- if (nbits < 512)
- nbits = 512;
-
- /* Already almost an HMAC since we consume a hash, so no GCRY_MD_FLAG_HMAC. */
- rc = gcry_md_open (&h, GCRY_MD_SHA512, 0);
- if (0 != rc)
- return rc;
-
- // We seed with the public denomination key as a homage to RSA-PSS by
- // Mihir Bellare and Phillip Rogaway. Doing this lowers the degree
- // of the hypothetical polyomial-time attack on RSA-KTI created by a
- // polynomial-time one-more forgary attack. Yey seeding!
- buf_len = GNUNET_CRYPTO_rsa_public_key_encode (pkey, &buf);
- gcry_md_write (h, buf, buf_len);
- GNUNET_free (buf);
-
- nhashes = (nbits-1) / (8 * sizeof(struct GNUNET_HashCode)) + 1;
- hs = GNUNET_new_array (nhashes,
- struct GNUNET_HashCode);
- for (i=0; i<nhashes; i++)
- {
- gcry_md_write (h, hash, sizeof(struct GNUNET_HashCode));
- rc = gcry_md_copy (&h0, h);
- if (0 != rc)
- {
- gcry_md_close (h0);
- break;
- }
- gcry_md_putc (h0, i % 256);
- memcpy (&hs[i],
- gcry_md_read (h0, GCRY_MD_SHA512),
- sizeof(struct GNUNET_HashCode));
- gcry_md_close (h0);
- }
- gcry_md_close (h);
- if (0 != rc)
- {
- GNUNET_free (hs);
- return rc;
- }
-
- rc = gcry_mpi_scan (r,
- GCRYMPI_FMT_USG,
- (const unsigned char *) hs,
- nhashes * sizeof(struct GNUNET_HashCode),
- rsize);
- GNUNET_free (hs);
- if (0 != rc)
- return rc;
-
- // Do not allow *r to exceed n or signatures fail to verify unpredictably.
- // This happening with gcry_mpi_clear_highbit (*r, nbits-1) so maybe
- // gcry_mpi_clear_highbit is broken, but setting the highbit sounds good.
- gcry_mpi_set_highbit (*r, nbits-2);
- return rc;
+ 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 *
+ * Mihir Bellare and Phillip Rogaway. Doing this lowers the degree *
+ * of the hypothetical polyomial-time attack on RSA-KTI created by a *
+ * polynomial-time one-more forgary attack. Yey seeding! */
+ xts_len = GNUNET_CRYPTO_rsa_public_key_encode (pkey, &xts);
+
+ 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,
- struct GNUNET_CRYPTO_rsa_BlindingKey *bkey,
+ 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 rsize;
- size_t n;
- gcry_error_t rc;
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;
}
- rc = rsa_full_domain_hash (&data, hash, pkey, &rsize);
- if (0 != rc) // Allocation error in libgcrypt
- {
- GNUNET_break (0);
- gcry_mpi_release (ne[0]);
- gcry_mpi_release (ne[1]);
- *buffer = NULL;
- return 0;
+ 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);
- n = mpi_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;
data = mpi_to_sexp (value);
if (0 !=
- gcry_pk_sign (&result,
- data,
- key->sexp))
+ (rc = gcry_pk_sign (&result,
+ data,
+ key->sexp)))
{
+ LOG (GNUNET_ERROR_TYPE_WARNING,
+ _("RSA signing failed at %s:%d: %s\n"),
+ __FILE__,
+ __LINE__,
+ gcry_strerror (rc));
GNUNET_break (0);
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);
NULL));
sig = rsa_sign_mpi (key, v);
- gcry_mpi_release (value);
- return sig;
+ gcry_mpi_release (v);
+ return sig;
}
*
* @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_RsaPublicKey *pkey;
gcry_mpi_t v = NULL;
- gcry_error_t rc;
struct GNUNET_CRYPTO_RsaSignature *sig;
pkey = GNUNET_CRYPTO_rsa_private_key_get_public (key);
- rc = rsa_full_domain_hash (&v, hash, pkey, NULL);
+ v = rsa_full_domain_hash (pkey, hash);
GNUNET_CRYPTO_rsa_public_key_free (pkey);
- GNUNET_assert (0 == rc);
+ 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 (value);
- return sig;
-
+ gcry_mpi_release (v);
+ return sig;
}
* #GNUNET_CRYPTO_rsa_blind().
*
* @param sig the signature made on the blinded signature purpose
- * @param bkey the blinding key used to blind the 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,
- struct GNUNET_CRYPTO_rsa_BlindingKey *bkey,
+ const struct GNUNET_CRYPTO_RsaBlindingKeySecret *bks,
struct GNUNET_CRYPTO_RsaPublicKey *pkey)
{
+ struct RsaBlindingKey *bkey;
gcry_mpi_t n;
gcry_mpi_t s;
gcry_mpi_t r_inv;
GNUNET_break_op (0);
return NULL;
}
+
+ 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 !=
gcry_mpi_invm (r_inv,
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);
return NULL;
}
+
ubsig = gcry_mpi_new (0);
gcry_mpi_mulm (ubsig, s, r_inv, n);
gcry_mpi_release (n);
gcry_mpi_release (r_inv);
gcry_mpi_release (s);
+ rsa_blinding_key_free (bkey);
sret = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
GNUNET_assert (0 ==
/**
- * 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;
- rc = rsa_full_domain_hash (&r, hash, pkey, NULL);
- GNUNET_assert (0 == rc); // Allocation error in libgcrypt
+ 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