Nikos Mavrogiannopoulos nmav@gnutls.org writes:
I've updated the patch to account for that and other issues. http://homes.esat.kuleuven.be/~nikos/0001-Added-timing-resistant-versions-of...
Nice. I'm still not sure how to best do this. I've been looking at it for some time today, and I consider the below patch (with _rsa_blind and _rsa_unblind helper functions in aseparate file). But on second thought maybe it's better to do it like you do with an rsa_compute_root_tr function. In any case, I think it does make sense to have a separate pkcs1_decrypt function for the common processing of rsa_decrypt and rsa_decrypt_tr.
What I haven't done is to duplicate all the rsa_(hash)_sign functions. They are quite many and it doesn't make much sense duplicating all of them. Do you have any suggestion on compacting it?
One way may be to *always* do blinding. But I hesitate before requiring the user to setup and provide a randomness function. I note that the document you pointed to, ftp://ftp.rsasecurity.com/pub/pdfs/bull-2.pdf, suggests using something similar to HMAC(private-key, input) to generate the random number to be used for blidning. Doing that (and maybe have an *optional* randomness source) could make sense.
The needed randomness info has to go either as argument to all private key operations, or be put somewhere in the private key struct. And either way makes things more complicated.
I don't really think that the random number in DSA relates to RSA blinding. The random number in DSA is part of the signature scheme, while the RSA blinding random number is just to prevent timing attacks.
The purpose is very different, but the interface issues (assuming we do add deterministic DSA signatures) are very similar: You have a signature method were a randomness function is optional for all private key operations.
I think it makes some sense to implement rsa_decrypt_tr now, with no advertised internals, and give the signature interface more time.
BTW, do you have any test cases? It would be useful both to have test cases that check that the _tr operations give the correct result (that should ba a simple addition to testsuite/rsa-encrypt-test, I guess), and some way to quantitatively check how the timing depends on the inputs, for both rsa_compute_root and rsa_compute_root_tr.
Regard, /Niels
diff --git a/Makefile.in b/Makefile.in index 4d3c89a..bad8103 100644 --- a/Makefile.in +++ b/Makefile.in @@ -99,7 +99,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \ bignum.c bignum-next-prime.c \ bignum-random.c bignum-random-prime.c \ sexp2bignum.c \ - pkcs1.c pkcs1-rsa-md5.c pkcs1-rsa-sha1.c \ + pkcs1.c pkcs1-decrypt.c pkcs1-rsa-md5.c pkcs1-rsa-sha1.c \ pkcs1-rsa-sha256.c pkcs1-rsa-sha512.c \ rsa.c rsa-sign.c rsa-verify.c \ rsa-md5-sign.c rsa-md5-verify.c \ @@ -107,6 +107,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \ rsa-sha256-sign.c rsa-sha256-verify.c \ rsa-sha512-sign.c rsa-sha512-verify.c \ rsa-encrypt.c rsa-decrypt.c \ + rsa-blind.c rsa-decrypt-tr.c \ rsa-keygen.c rsa-compat.c \ rsa2sexp.c sexp2rsa.c \ dsa.c dsa-sign.c dsa-verify.c dsa-keygen.c \ diff --git a/pkcs1-decrypt.c b/pkcs1-decrypt.c new file mode 100644 index 0000000..bd21f88 --- /dev/null +++ b/pkcs1-decrypt.c @@ -0,0 +1,72 @@ +/* pkcs1-decrypt.c + * + */ + +/* nettle, low-level cryptographics library + * + * Copyright (C) 2001, 2012 Niels Möller + * + * The nettle library is free software; you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as published by + * the Free Software Foundation; either version 2.1 of the License, or (at your + * option) any later version. + * + * The nettle library is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY + * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public + * License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with the nettle library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <string.h> + +#include "pkcs1.h" + +#include "bignum.h" +#include "nettle-internal.h" + +int +pkcs1_decrypt (unsigned key_size, + const mpz_t m, + unsigned *length, uint8_t *message) +{ + TMP_DECL(em, uint8_t, NETTLE_MAX_BIGNUM_BITS / 8); + uint8_t *terminator; + unsigned padding; + unsigned message_length; + + TMP_ALLOC(em, key_size); + nettle_mpz_get_str_256(key_size, em, m); + + /* Check format */ + if (em[0] || em[1] != 2) + return 0; + + terminator = memchr(em + 2, 0, key_size - 2); + + if (!terminator) + return 0; + + padding = terminator - (em + 2); + if (padding < 8) + return 0; + + message_length = key_size - 3 - padding; + + if (*length < message_length) + return 0; + + memcpy(message, terminator + 1, message_length); + *length = message_length; + + return 1; +} + diff --git a/pkcs1.h b/pkcs1.h index 732d0ed..95a6a83 100644 --- a/pkcs1.h +++ b/pkcs1.h @@ -43,6 +43,7 @@ extern "C" { #define pkcs1_rsa_sha256_encode_digest nettle_pkcs1_rsa_sha256_encode_digest #define pkcs1_rsa_sha512_encode nettle_pkcs1_rsa_sha512_encode #define pkcs1_rsa_sha512_encode_digest nettle_pkcs1_rsa_sha512_encode_digest +#define pkcs1_decrypt nettle_pkcs1_decrypt
struct md5_ctx; struct sha1_ctx; @@ -57,6 +58,11 @@ pkcs1_signature_prefix(unsigned size, unsigned digest_size);
int +pkcs1_decrypt (unsigned key_size, + const mpz_t m, + unsigned *length, uint8_t *message); + +int pkcs1_rsa_md5_encode(mpz_t m, unsigned length, struct md5_ctx *hash);
int diff --git a/rsa-blind.c b/rsa-blind.c new file mode 100644 index 0000000..f66c169 --- /dev/null +++ b/rsa-blind.c @@ -0,0 +1,65 @@ +/* rsa-blind.c + * + */ + +/* nettle, low-level cryptographics library + * + * Copyright (C) 2012, Nikos Mavrogiannopoulos, Niels Möller + * + * The nettle library is free software; you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as published by + * the Free Software Foundation; either version 2.1 of the License, or (at your + * option) any later version. + * + * The nettle library is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY + * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public + * License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with the nettle library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "rsa.h" +#include "bignum.h" + +void +_rsa_blind (const mpz_t n, const mpz_t e, + void *random_ctx, nettle_random_func random, + mpz_t c, mpz_t ri) +{ + mpz_t r; + + mpz_init(r); + + /* c = c*(r^e) + * ri = r^(-1) + */ + do + { + nettle_mpz_random(r, random_ctx, random, n); + /* invert r */ + } + while (!mpz_invert (ri, r, n)); + + /* c = c*(r^e) mod n */ + mpz_powm(r, r, e, n); + mpz_mul(c, c, r); + mpz_fdiv_r(c, c, n); + + mpz_clear(r); +} + +void +_rsa_unblind (const mpz_t n, mpz_t c, const mpz_t ri) +{ + mpz_mul(c, c, ri); + mpz_fdiv_r(c, c, n); +} + diff --git a/rsa-decrypt-tr.c b/rsa-decrypt-tr.c new file mode 100644 index 0000000..5951a12 --- /dev/null +++ b/rsa-decrypt-tr.c @@ -0,0 +1,55 @@ +/* rsa-decrypt-tr.c + * + * The RSA publickey algorithm. PKCS#1 encryption. + */ + +/* nettle, low-level cryptographics library + * + * Copyright (C) 2001, 2012 Niels Möller + * + * The nettle library is free software; you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as published by + * the Free Software Foundation; either version 2.1 of the License, or (at your + * option) any later version. + * + * The nettle library is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY + * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public + * License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with the nettle library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "rsa.h" + +#include "pkcs1.h" + +int +rsa_decrypt_tr(const struct rsa_public_key *public, + const struct rsa_private_key *key, + void *random_ctx, nettle_random_func random, + unsigned *length, uint8_t *message, + const mpz_t gibberish) +{ + mpz_t m, ri; + int res; + + mpz_init_set(m, gibberish); + mpz_init (ri); + + rsa_blind (public->n, public->e, random_ctx, random, + m, ri); + rsa_compute_root(key, m, m); + rsa_unblind (public->n, m, ri); + + res = pkcs1_decrypt (key->size, m, length, message); + mpz_clear(m); + return res; +} diff --git a/rsa-decrypt.c b/rsa-decrypt.c index fe6de23..cde0d3c 100644 --- a/rsa-decrypt.c +++ b/rsa-decrypt.c @@ -1,11 +1,11 @@ -/* rsa_decrypt.c +/* rsa-decrypt.c * * The RSA publickey algorithm. PKCS#1 encryption. */
/* nettle, low-level cryptographics library * - * Copyright (C) 2001 Niels Möller + * Copyright (C) 2001, 2012 Niels Möller * * The nettle library is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by @@ -27,54 +27,22 @@ # include "config.h" #endif
-#include <assert.h> -#include <stdlib.h> -#include <string.h> - #include "rsa.h"
-#include "bignum.h" -#include "nettle-internal.h" +#include "pkcs1.h"
int rsa_decrypt(const struct rsa_private_key *key, unsigned *length, uint8_t *message, const mpz_t gibberish) { - TMP_DECL(em, uint8_t, NETTLE_MAX_BIGNUM_BITS / 8); - uint8_t *terminator; - unsigned padding; - unsigned message_length; - mpz_t m; + int res;
mpz_init(m); rsa_compute_root(key, m, gibberish);
- TMP_ALLOC(em, key->size); - nettle_mpz_get_str_256(key->size, em, m); + res = pkcs1_decrypt (key->size, m, length, message); mpz_clear(m); - - /* Check format */ - if (em[0] || em[1] != 2) - return 0; - - terminator = memchr(em + 2, 0, key->size - 2); - - if (!terminator) - return 0; - - padding = terminator - (em + 2); - if (padding < 8) - return 0; - - message_length = key->size - 3 - padding; - - if (*length < message_length) - return 0; - - memcpy(message, terminator + 1, message_length); - *length = message_length; - - return 1; + return res; } diff --git a/rsa.h b/rsa.h index a4ef835..75eaafc 100644 --- a/rsa.h +++ b/rsa.h @@ -32,9 +32,6 @@ #include "md5.h" #include "sha.h"
-/* For nettle_random_func */ -#include "nettle-meta.h" - #ifdef __cplusplus extern "C" { #endif @@ -64,7 +61,10 @@ extern "C" { #define rsa_sha512_verify_digest nettle_rsa_sha512_verify_digest #define rsa_encrypt nettle_rsa_encrypt #define rsa_decrypt nettle_rsa_decrypt +#define rsa_decrypt_tr nettle_rsa_decrypt_re #define rsa_compute_root nettle_rsa_compute_root +#define _rsa_blind _nettle_rsa_blind +#define _rsa_unblind _nettle_rsa_unblind #define rsa_generate_keypair nettle_rsa_generate_keypair #define rsa_keypair_to_sexp nettle_rsa_keypair_to_sexp #define rsa_keypair_from_sexp_alist nettle_rsa_keypair_from_sexp_alist @@ -260,7 +260,7 @@ rsa_sha512_verify_digest(const struct rsa_public_key *key, int rsa_encrypt(const struct rsa_public_key *key, /* For padding */ - void *random_ctx, nettle_random_func random, + void *random_ctx, nettle_random_func *random, unsigned length, const uint8_t *cleartext, mpz_t cipher);
@@ -274,12 +274,31 @@ rsa_decrypt(const struct rsa_private_key *key, unsigned *length, uint8_t *cleartext, const mpz_t ciphertext);
+/* Timing-resistant version, using randomized RSA blinding. */ +int +rsa_decrypt_tr(const struct rsa_public_key *public, + const struct rsa_private_key *key, + void *random_ctx, nettle_random_func random, + unsigned *length, uint8_t *message, + const mpz_t gibberish); + /* Compute x, the e:th root of m. Calling it with x == m is allowed. */ void rsa_compute_root(const struct rsa_private_key *key, mpz_t x, const mpz_t m);
+/* Blinds the c, by computing c *= r^e (mod n), for a random r. Also + returns the inverse (ri), for use by rsa_unblind. */ +void +_rsa_blind (const mpz_t n, const mpz_t e, + void *random_ctx, nettle_random_func *random, + mpz_t c, mpz_t ri); + +/* c *= ri mod n */ +void +_rsa_unblind (const mpz_t n, mpz_t c, const mpz_t ri); + /* Key generation */
/* Note that the key structs must be initialized first. */ @@ -287,8 +306,8 @@ int rsa_generate_keypair(struct rsa_public_key *pub, struct rsa_private_key *key,
- void *random_ctx, nettle_random_func random, - void *progress_ctx, nettle_progress_func progress, + void *random_ctx, nettle_random_func *random, + void *progress_ctx, nettle_progress_func *progress,
/* Desired size of modulo, in bits */ unsigned n_size,