Hello, Attached you'll find an initial patch that adds timing resistant versions of rsa_compute_root() and rsa_decrypt().
regards, Nikos
On 04/06/2012 08:39 AM, Nikos Mavrogiannopoulos wrote:
Attached you'll find an initial patch that adds timing resistant versions of rsa_compute_root() and rsa_decrypt().
No patch was attached to the version of the message i received from the list. Maybe try it again?
--dkg
On Fri, Apr 6, 2012 at 3:12 PM, Daniel Kahn Gillmor dkg@fifthhorseman.net wrote:
No patch was attached to the version of the message i received from the list. Maybe try it again?
I can see it on my sent folder. Could it be that the list manager removed it? I've put it at: http://homes.esat.kuleuven.be/~nikos/0001-Added-timing-resistant-versions-of...
regards, Nikos
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
I can see it on my sent folder. Could it be that the list manager removed it?
Possibly. The mailman config is known to be a bit picky (and I'm not very good at configuring it), but I thought it would usually bounce messages rather than silently remove attachments.
I've put it at: http://homes.esat.kuleuven.be/~nikos/0001-Added-timing-resistant-versions-of...
Thanks! I've had a quick look. A few comments:
I'm not sure if the low-level rsa_compute_root should be aware of the blinding, or if it should be the responsibility of its callers (using _rsa_blind, _rsa_unblind helper functions, put in rsa_blind.c or so).
Support for blinding is desirable not only for rsa_decrypt, but also for the various rsa_*_sign functions, right?
The blinding function should probably use nettle_mpz_random, which provides for *almost* uniform distribution mod n by generating a few extra bits before the mpz_fdiv_r.
As for interface, I have been considering to also add some kind of deterministic dsa signatures, substituting something like HMAC(private key, message) for the random input, and if possible, it would be nice to have a consistent interface for {rsa, dsa} signatures {with, without} randomness input.
Not sure if we should have separate functions for operation with and without blidning, or a single function with an optional randomness source as argument. If we have separate functions, we have to decide on the name (I don't quite like "_timing": If the name is supposed to describe intended use, it needs to be more verbose, maybe "_timing_resistant". I think it may be more handy to rather describe what it *does*, something like "_blinding" or "_randomized" or so).
Regards, /Niels
On 04/07/2012 10:47 AM, Niels Möller wrote:
Thanks! I've had a quick look. A few comments: I'm not sure if the low-level rsa_compute_root should be aware of the blinding, or if it should be the responsibility of its callers (using _rsa_blind, _rsa_unblind helper functions, put in rsa_blind.c or so).
As a user of the library I'd prefer a low level function that provides the algorithm operation in constant time, so that I don't need to understand the details of blinding. It might be that in later version nettle doesn't use blinding but something different to achieve constant time, so it would be nice existing applications to change automatically.
Support for blinding is desirable not only for rsa_decrypt, but also for the various rsa_*_sign functions, right?
Indeed. I changed rsa_compute_root() because I don't use the *_sign() functions. They were not very flexible for my needs. I will try updating making a constant time counterpart of them, but it will expand the interface considerably.
The blinding function should probably use nettle_mpz_random, which provides for *almost* uniform distribution mod n by generating a few extra bits before the mpz_fdiv_r.
I'll update it for that.
Not sure if we should have separate functions for operation with and without blidning, or a single function with an optional randomness
source as argument. If we have separate functions, we have to decide on the name (I don't quite like "_timing": If the name is supposed to
describe intended use, it needs to be more verbose, maybe
"_timing_resistant". I think it may be more handy to rather describe what it *does*, something like "_blinding" or "_randomized" or so).
What about _ct for constant time? The _blinding is really specific on the method used to achieve constant time.
regards, Nikos
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
What about _ct for constant time? The _blinding is really specific on the method used to achieve constant time.
But it's not really constant time, is it? Rather, timing is random but independent of the inputs which are under control of the attacker. While without RSA blinding, timing depends on the secret key and on data provided by the attacker, which is a bad combination.
The function mpz_powm_sec in recent GMP is supposed to really be "constant time" (assuming the underlying multiply-instruction doesn't have data-dependent timing). I.e., the instructions executed and the memory access pattern should depend only on the sizes of the input operands, not on the actual values. Hence it should be resistant both to timing attacks, and attacks manipulating or observing the memory cache hit rate.
But RSA operations uses a couple of additional functions, which doesn't yet have constant-time counterparts, so I don't yet use that function yet.
BTW, what's a good reference for the recommendation to use RSA blinding? Is it in Handbook of applied cryptography? (I think pointers to papers on attacks have been posted previously, but that's describing the problem, not the solution...).
Regards, /Niels
lör 2012-04-07 klockan 15:30 +0200 skrev Niels Möller:
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
What about _ct for constant time? The _blinding is really specific on the method used to achieve constant time.
But it's not really constant time, is it? Rather, timing is random but independent of the inputs which are under control of the attacker. While without RSA blinding, timing depends on the secret key and on data provided by the attacker, which is a bad combination.
Maybe a better term to use is "reduced side channel" or something. Not easy to shorten though. The generic problem adressed here is side channels.
/Simon
On 04/07/2012 03:38 PM, Simon Josefsson wrote:
What about _ct for constant time? The _blinding is really specific on the method used to achieve constant time.
But it's not really constant time, is it? Rather, timing is random but independent of the inputs which are under control of the attacker. While without RSA blinding, timing depends on the secret key and on data provided by the attacker, which is a bad combination.
Maybe a better term to use is "reduced side channel" or something. Not easy to shorten though. The generic problem adressed here is side channels.
Indeed, but side channels also contain the issues due to power analysis, and I don't know if the same techniques that make an algorithm timing analysis resistant, also apply for power analysis.
regards, Nikos
lör 2012-04-07 klockan 20:30 +0200 skrev Nikos Mavrogiannopoulos:
On 04/07/2012 03:38 PM, Simon Josefsson wrote:
What about _ct for constant time? The _blinding is really specific on the method used to achieve constant time.
But it's not really constant time, is it? Rather, timing is random but independent of the inputs which are under control of the attacker. While without RSA blinding, timing depends on the secret key and on data provided by the attacker, which is a bad combination.
Maybe a better term to use is "reduced side channel" or something. Not easy to shorten though. The generic problem adressed here is side channels.
Indeed, but side channels also contain the issues due to power analysis, and I don't know if the same techniques that make an algorithm timing analysis resistant, also apply for power analysis.
Right, but maybe the API name could be general so that it could implement mitigation against power analysis as well in the future, if needed. Or some other side channel attack (cache misses, etc).
/Simon
On 04/07/2012 03:30 PM, Niels Möller wrote:
What about _ct for constant time? The _blinding is really specific on the method used to achieve constant time.
But it's not really constant time, is it? Rather, timing is random but independent of the inputs which are under control of the attacker. While without RSA blinding, timing depends on the secret key and on data provided by the attacker, which is a bad combination.
Indeed. So is _timing_resistant or _tr better?
BTW, what's a good reference for the recommendation to use RSA blinding? Is it in Handbook of applied cryptography? (I think pointers to papers on attacks have been posted previously, but that's describing the problem, not the solution...).
I've seen it there: ftp://ftp.rsasecurity.com/pub/pdfs/bull-2.pdf
regards, Nikos
On 04/07/2012 10:47 AM, Niels Möller wrote:
I'm not sure if the low-level rsa_compute_root should be aware of the blinding, or if it should be the responsibility of its callers (using _rsa_blind, _rsa_unblind helper functions, put in rsa_blind.c or so).
Support for blinding is desirable not only for rsa_decrypt, but also for the various rsa_*_sign functions, right?
The blinding function should probably use nettle_mpz_random, which
provides for *almost* uniform distribution mod n by generating a few
extra bits before the mpz_fdiv_r.
I've updated the patch to account for that and other issues. http://homes.esat.kuleuven.be/~nikos/0001-Added-timing-resistant-versions-of...
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?
As for interface, I have been considering to also add some kind of deterministic dsa signatures, substituting something like HMAC(private key, message) for the random input, and if possible, it would be nice to have a consistent interface for {rsa, dsa} signatures {with, without} randomness input.
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.
regards, Nikos
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,
nisse@lysator.liu.se (Niels Möller) writes:
I think it makes some sense to implement rsa_decrypt_tr now, with no advertised internals, and give the signature interface more time.
I've committed an rsa_decrypt_tr now, based on Nikos' code. I reordered the arguments a bit, in an attempt to be more consistent with other rsa functions, so the prototype is now
/* Timing-resistant version, using randomized RSA blinding. */ int rsa_decrypt_tr(const struct rsa_public_key *pub, const struct rsa_private_key *key, void *random_ctx, nettle_random_func *random, unsigned *length, uint8_t *message, const mpz_t gibberish);
Does this make sense? If you are using the rsa encrypt/decrypt functions, and the interface is ok, I guess we should also document them.
Regards, /Niels
On 04/09/2012 04:29 PM, Niels Möller wrote:
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.
Although the HMAC avoids the need for randomness, you need to get a key somehow, so the gain might not be much.
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.
Indeed.
I think it makes some sense to implement rsa_decrypt_tr now, with no advertised internals, and give the signature interface more time.
What about the rsa_compute_root? This is the only function I can use from nettle for RSA signatures (TLS is peculiar on its signatures thus the exported interface isn't sufficient). If there was an rsa_pkcs1_sign() and rsa_pkcs1_verify() with similar interface to encrypt/decrypt, I could use those instead.
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.
I had modified the rsa-encrypt-test.c to include a test for the timing resistant version as well. Other than that I have no other test cases.
regards, Nikos
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
Although the HMAC avoids the need for randomness, you need to get a key somehow, so the gain might not be much.
The idea is to reuse (hash of) the private RSA key as the HMAC key. And similarly for deterministic DSA.
What about the rsa_compute_root? This is the only function I can use from nettle for RSA signatures
I wasn't aware of that. That's an argument for an rsa_compute_root_tr (or alternatively, public rsa_blind and rsa_unblind helpers).
Can you explain briefly what special signatures are used by tls? (It was more then 10 years since I wrote an implementation, then it was ssl version 3).
If there was an rsa_pkcs1_sign() and rsa_pkcs1_verify() with similar interface to encrypt/decrypt, I could use those instead.
Can you propose such an interface? Currently, rsa_md5_sign calls pkcs1_rsa_md5_encode followed by rsa_compute_root. If it's easy for you to use rsa_compute_root in the same way, then I guess there's no need to introduce new low-level primitives, but maybe it could be rearranged in some better way?
Or, since tls is an important application, it may make sense to directly add tls-style signatures to Nettle.
I had modified the rsa-encrypt-test.c to include a test for the timing resistant version as well. Other than that I have no other test cases.
I see. It would really be helpful with some tools for measuring the input dependence in the timing of rsa_compute_root. GMP's mpz_powm may well behave quite differently from openssl's.
Regards, /Niels
On Mon, Apr 9, 2012 at 10:57 PM, Niels Möller nisse@lysator.liu.se wrote:
What about the rsa_compute_root? This is the only function I can use from nettle for RSA signatures
I wasn't aware of that. That's an argument for an rsa_compute_root_tr (or alternatively, public rsa_blind and rsa_unblind helpers). Can you explain briefly what special signatures are used by tls? (It was more then 10 years since I wrote an implementation, then it was ssl version 3).
Out of memory TLS 1.0 uses a concatenation of md5 and sha1. I don't think however that, this mode should be added in nettle. It would complicate the API for no real reason (if a generic pkcs1, 1.5 signing function is available).
If there was an rsa_pkcs1_sign() and rsa_pkcs1_verify() with similar interface to encrypt/decrypt, I could use those instead.
Can you propose such an interface? Currently, rsa_md5_sign calls pkcs1_rsa_md5_encode followed by rsa_compute_root. If it's easy for you to use rsa_compute_root in the same way, then I guess there's no need to introduce new low-level primitives, but maybe it could be rearranged in some better way?
I do the pkcs1 1.5 encoding in gnutls, and you also do it in the high level functions in nettle, that I cannot use. It would be nice if we can save some code and reduce error risk by having a common pkcs1 1.5 signing function. I'll try to propose one the next few days.
Or, since tls is an important application, it may make sense to directly add tls-style signatures to Nettle.
I don't think it is a good idea. What might be needed at some point later is pkcs 1 2.0 signatures. I've come across some passports signed by certificates using rsa-pss :(
regards, Nikos
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
I do the pkcs1 1.5 encoding in gnutls, and you also do it in the high level functions in nettle, that I cannot use. It would be nice if we can save some code and reduce error risk by having a common pkcs1 1.5 signing function. I'll try to propose one the next few days.
Have you looked at pkcs1_signature_prefix? It does part of the work, so maybe it's a good starting point. The reason it leaves space for the actual digest rather than copying it in place, is to avoid extra copies for the rsa_md5_sign-style functions.
If this could be simplified, to reduce the amount of duplicated code to implement signatures for each supported hash function, while keeping low overhead for applications using only a single variant, that would be nice.
Regards, /Niels
On 04/10/2012 12:23 PM, Niels Möller wrote:
I do the pkcs1 1.5 encoding in gnutls, and you also do it in the high level functions in nettle, that I cannot use. It would be nice if we can save some code and reduce error risk by having a common pkcs1 1.5 signing function. I'll try to propose one the next few days.
Have you looked at pkcs1_signature_prefix? It does part of the work, so maybe it's a good starting point. The reason it leaves space for the actual digest rather than copying it in place, is to avoid extra copies for the rsa_md5_sign-style functions.
pkcs1_signature_prefix() is very low level to be used by gnutls, as it assumes no ASN.1 encoder. The most suitable for me would be something like:
/* RSA signatures, using PKCS#1 1.5 * Input should be a BER encoded DigestInfo */ int rsa_digest_info_sign(const struct rsa_private_key *key, unsigned length, const uint8_t *digest_info, mpz_t signature);
int rsa_digest_info_verify(const struct rsa_public_key *key, unsigned length, const uint8_t *digest_info, const mpz_t signature);
Those two could also be used in place of all the individual rsa_(hash)_sign and rsa_(hash)_verify. It requires though another function is available translate from a digest to the digest_info (this is not needed for gnutls as we already have that, just a suggestion to fit those two in nettle).
E.g. digest_to_digest_info(hash_id, unsigned length, const uint8_t* digest, unsigned* digest_info_length, uint8_t* digest_info);
The cost is having a single function that will contain the OIDs for all the supported hash algorithms. The benefit is that there is no need to have separate sign and verify functions for each supported hash.
regards, Nikos
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
/* RSA signatures, using PKCS#1 1.5
- Input should be a BER encoded DigestInfo
*/ int rsa_digest_info_sign(const struct rsa_private_key *key, unsigned length, const uint8_t *digest_info, mpz_t signature);
int rsa_digest_info_verify(const struct rsa_public_key *key, unsigned length, const uint8_t *digest_info, const mpz_t signature);
That seems reasonable (if and how the implementation of nettle's other rsa sign/verify functions could be reorganized to make use of that, I'm not sure).
Minor points: It should really be DER encoded, right? And I guess you'd also want a _sign_tr variant. As for naming, maybe I'd want to have "pkcs1" int he name, not sure.
A question for all of you: Nettle currently has two flavors of sign functions for each algorithm. E.g.,
int rsa_sha1_sign(const struct rsa_private_key *key, struct sha1_ctx *hash, mpz_t signature);
int rsa_sha1_sign_digest(const struct rsa_private_key *key, const uint8_t *digest, mpz_t s);
The former could be implemented in terms of the latter (currently it's not, to avoid an unnecessary copy, which may be a pointless optimization in this context).
The point of the first function is convenience, where you can create a signature simply by
sha1_init sha1_update rsa_sha1_sign
without bothering with allocating and writing the actual digest.
Do you think this design makes sense?
Regards, /Niels
On 04/14/2012 09:28 AM, Niels Möller wrote:
/* RSA signatures, using PKCS#1 1.5
- Input should be a BER encoded DigestInfo
*/ int rsa_digest_info_sign(const struct rsa_private_key *key, unsigned length, const uint8_t *digest_info, mpz_t signature);
int rsa_digest_info_verify(const struct rsa_public_key *key, unsigned length, const uint8_t *digest_info, const mpz_t signature);
That seems reasonable (if and how the implementation of nettle's other rsa sign/verify functions could be reorganized to make use of that, I'm not sure). Minor points: It should really be DER encoded, right?
PKCS #1 1.5 says BER and there were quite some implementations that used BER for encoding instead of DER.
And I guess you'd also want a _sign_tr variant.
Indeed. I only listed the basic interface for review.
As for naming, maybe I'd want to have
"pkcs1" int he name, not sure.
I wanted to use PKCS1 but it might be misleading as PKCS #1 1.5 has a different padding method than PKCS #1 2.1 which uses OAEP. I don't know if rsa_pkcs1_1_5_sign is reasonable...
A question for all of you: Nettle currently has two flavors of sign functions for each algorithm. E.g., int rsa_sha1_sign(const struct rsa_private_key *key, struct sha1_ctx *hash, mpz_t signature);
int rsa_sha1_sign_digest(const struct rsa_private_key *key, const uint8_t *digest, mpz_t s); The former could be implemented in terms of the latter (currently it's not, to avoid an unnecessary copy, which may be a pointless optimization in this context).
The point of the first function is convenience, where you can create a
signature simply by
sha1_init sha1_update rsa_sha1_sign without bothering with allocating and writing the actual digest. Do you think this design makes sense?
IMO it makes sense, but I think the drawbacks, which are maintaining one extra function per hash, do not really outweigh the benefit which is not really noticeable in the RSA operation.
regards, Nikos
nettle-bugs@lists.lysator.liu.se
-
Daniel Kahn Gillmor -
Nikos Mavrogiannopoulos -
nisse＠lysator.liu.se -
Simon Josefsson