I'm considering the below patch, making use of the side-channel silent mpz_powm_sec function. The idea is to make the RSA and DSA code less vulnerable to side-channel attacks.
Exponentiation routines typically build a small table of powers at run time, and then look up exponent bits in the table, a few bits at the time. This table lookup may leak information about the exponent bits (which in the case of RSA and DSA are secret) to an attacker running other processes on the same physical machine.
mpz_powm_sec uses a slower table-lookup function, which for each lookup does a sequential read of the entire table. Some caveats:
* The CRT code used for RSA signing uses other functions which may leak, in particular division functions with branches depending on secret data.
* Since we still use the mpz interface rather than the mpn interface in gmp, the exponents use a normalized size field (so top limb is non-zero). This might still leak information about the top exponent bits.
* The patch drops support for GMP versions older than GMP-5.0, relased in 2010.
* Mini-gmp builds don't try to be side-channel silent, they will use a #define mpz_powm_sec mpz_powm.
* I haven't yet had time to do proper benchmarks. Signing should get a bit slower, but I don't know how much.
Despite not plugging *all* potential leaks in the RSA code, I think the simple change to use use mpz_powm_sec should make attacks using the cache side-channel considerably more difficult.
Regards, /Niels
Hi Niels--
On Mon 2016-06-20 01:30:47 -0400, Niels Möller wrote:
I'm considering the below patch, making use of the side-channel silent mpz_powm_sec function. The idea is to make the RSA and DSA code less vulnerable to side-channel attacks.
This is a good goal for Nettle to have. Thanks!
Exponentiation routines typically build a small table of powers at run time, and then look up exponent bits in the table, a few bits at the time. This table lookup may leak information about the exponent bits (which in the case of RSA and DSA are secret) to an attacker running other processes on the same physical machine.
This is increasingly relevant in today's virtualized world.
- The patch drops support for GMP versions older than GMP-5.0, relased in 2010.
I don't think this bump in dependencies is a problem.
Despite not plugging *all* potential leaks in the RSA code, I think the simple change to use use mpz_powm_sec should make attacks using the cache side-channel considerably more difficult.
I agree that this is a step in the right direction. the closer to constant time, the better.
--dkg
On Mon, 2016-06-20 at 07:30 +0200, Niels Möller wrote:
I'm considering the below patch, making use of the side-channel silent mpz_powm_sec function. The idea is to make the RSA and DSA code less vulnerable to side-channel attacks.
Exponentiation routines typically build a small table of powers at run time, and then look up exponent bits in the table, a few bits at the time. This table lookup may leak information about the exponent bits (which in the case of RSA and DSA are secret) to an attacker running other processes on the same physical machine.
mpz_powm_sec uses a slower table-lookup function, which for each lookup does a sequential read of the entire table. Some caveats:
- The CRT code used for RSA signing uses other functions which may
leak, in particular division functions with branches depending on secret data.
- Since we still use the mpz interface rather than the mpn interface
in gmp, the exponents use a normalized size field (so top limb is non-zero). This might still leak information about the top exponent bits.
- The patch drops support for GMP versions older than GMP-5.0,
relased in 2010.
- Mini-gmp builds don't try to be side-channel silent, they will use
a #define mpz_powm_sec mpz_powm.
- I haven't yet had time to do proper benchmarks. Signing should get
a bit slower, but I don't know how much. Despite not plugging *all* potential leaks in the RSA code, I think the simple change to use use mpz_powm_sec should make attacks using the cache side-channel considerably more difficult.
+1
nisse@lysator.liu.se (Niels Möller) writes:
I'm considering the below patch, making use of the side-channel silent mpz_powm_sec function. The idea is to make the RSA and DSA code less vulnerable to side-channel attacks.
Committed and pushed now, with some additional fixes.
Regards, /Niels
On Mon, Jun 20, 2016 at 7:30 AM, Niels Möller nisse@lysator.liu.se wrote:
I'm considering the below patch, making use of the side-channel silent mpz_powm_sec function. The idea is to make the RSA and DSA code less vulnerable to side-channel attacks. Exponentiation routines typically build a small table of powers at run time, and then look up exponent bits in the table, a few bits at the time. This table lookup may leak information about the exponent bits (which in the case of RSA and DSA are secret) to an attacker running other processes on the same physical machine.
I've checked the patch, and it seems to use mpz_powm_sec() in the blinding part (which uses only public parameters). Is that intentional? As far as that shouldn't affect the existing cache-exploiting attacks.
regards, Nikos
Nikos Mavrogiannopoulos n.mavrogiannopoulos@gmail.com writes:
I've checked the patch, and it seems to use mpz_powm_sec() in the blinding part (which uses only public parameters). Is that intentional?
Kind-of, I wasn't sure what to do here, but since the number r should be considered secret, it seemed safest.
Let me first recap my understanding if RSA blinding (which I find a bit questionable). When computing m^d (mod n), the point of blinding is to obscure the bits of m, not the bits if d. It adds no protection against side-channel attacks directly on the exponent bits, since they're the same before and after blinding. The point of blinding is instead to defend against attacks exploiting side-channnel leaks in the mod p reduction code, which typically depend on a chosen-ciphertect attack scenario or similar, where m is carefully chosen by the attacker. Do you agree?
Since the secret value r goes into the input that blinding tries to obscure, using powm_sec makes sme sense to me, even if it may be overkill.
Now, in recent GMP versions, powm_sec uses a reduction method which is intended to be side-channel silent. So when using it, blinding is perhaps not adding any benefit at all. But I think it's best to nevertheless keep RSA-bliding for now, as a belt-and-suspenders measure. And because I'd prefer not to have to think of the PR issues when deleting a established security feature...
Regards, /Niels
Hi,
On Mon, 20 Jun 2016 07:30:47 +0200 nisse@lysator.liu.se (Niels Möller) wrote:
I'm considering the below patch, making use of the side-channel silent mpz_powm_sec function. The idea is to make the RSA and DSA code less vulnerable to side-channel attacks.
This change introduces a security risk.
The function mpz_powm_sec() is not a drop in replacement for mpz_powm(), although it may sound like it. If you look at the docs [1] a requirement for mpz_powm_sec() is that the modulus must be odd.
If the modulus is even / divisible by 2 then mpz_powm_sec() will crash with a floating point exception. Quite frankly, I think this is bad from GMPs side as well. At the very least it shouldn't crash for invalid inputs, but return an error. (Ideally it would just work for all inputs that mathematically make sense). But nettle has to handle things with gmp as they are.
Attached is a certificate + key where I manually changed the modulus to be even (P.S.: This tool [2] fis very useful for such cases). The certificate is therefore obviously bogus, but that doesn't matter in our case.
Just try to run nettle with the mpz_powm_sec() patch and try to run gnutls with this crafted cert: gnutls-serv --x509keyfile=crashnettle.pem --x509certfile=crashnettle.pem
This crashes as expected with a floating point exception.
Now it may not be obvious that this is a security risk, because I usually control my own certificates. But there may well be situations where that's not so clear. E.g. think of a webhoster that allows his customers to set custom certificates and private keys. That doesn't mean one wants his customers to allow crashing the servers.
It may be that there are other situations where this matters.
Anyway: Changing to mpz_pown_sec() probably should only be done if the code is carefully checked to make sure that an even modulus never enters this function.
(P.S.: The autoconf gmp detection part of this patch breaks on my system and nettle gets built without gmp, so there seems to be something wrong with that, too. I have Gentoo with gmp 6.1.1. I haven't further analyzed this, I simply removed that part of the patch for my testing.)
[1] https://gmplib.org/manual/Integer-Exponentiation.html [2] https://github.com/google/der-ascii
Hanno Böck hanno@hboeck.de writes:
If the modulus is even / divisible by 2 then mpz_powm_sec() will crash with a floating point exception. Quite frankly, I think this is bad from GMPs side as well. At the very least it shouldn't crash for invalid inputs, but return an error.
I think the GMP design is to leave any easy sanity checks to the application. While for more complex conditions, like modular inversion (which fails if inputs have any non-trivial common factor), gmp checks for this and returns an error indication.
(Ideally it would just work for all inputs that mathematically make sense). But nettle has to handle things with gmp as they are.
I think it should be easy and reasonable to add code to rsa_public_key_prepare and rsa_private_key_prepare to check that the modulo is odd. What do you think? It's reasonable to have those functions do enough key validation to be able to handle the key without crashing.
Attached is a certificate + key where I manually changed the modulus to be even (P.S.: This tool [2] fis very useful for such cases). The certificate is therefore obviously bogus, but that doesn't matter in our case.
If you can transform this into a nettle testcase, that would be nice. I think it would fit best either with the high-level tests examples/rsa-sign-test and examples/rsa-verify-test, or as unit tests in testsuite/rsa-test.c.
(P.S.: The autoconf gmp detection part of this patch breaks on my system and nettle gets built without gmp,
With the patch as posted to the list, or using the master branch of the repo? I'm aware of configure bugs in the former but not the latter.
Thanks for the review, /Niels
nisse@lysator.liu.se (Niels Möller) writes:
I think it should be easy and reasonable to add code to rsa_public_key_prepare and rsa_private_key_prepare to check that the modulo is odd. What do you think? It's reasonable to have those functions do enough key validation to be able to handle the key without crashing.
Done now (or rather, added to the shared helper function _rsa_check_size).
Attached is a certificate + key where I manually changed the modulus to be even (P.S.: This tool [2] fis very useful for such cases). The certificate is therefore obviously bogus, but that doesn't matter in our case.
Any other easy checks for bogus keys that should be added? I would expect that code parsing key formats, e.g., asn.1, would check sign and range of parameters and catch bogus values early (e.g., the code in nettle's der2rsa.c does that). It's possible to add additional sanity checks to the _key_prepare functions, if desired. It's not entirely obvious where that responsibility should be placed.
Regards, /Niels
On Sun, Jul 31, 2016 at 10:44 AM, Niels Möller nisse@lysator.liu.se wrote:
Attached is a certificate + key where I manually changed the modulus to be even (P.S.: This tool [2] fis very useful for such cases). The certificate is therefore obviously bogus, but that doesn't matter in our case.
Any other easy checks for bogus keys that should be added? I would expect that code parsing key formats, e.g., asn.1, would check sign and range of parameters and catch bogus values early (e.g., the code in nettle's der2rsa.c does that). It's possible to add additional sanity checks to the _key_prepare functions, if desired. It's not entirely obvious where that responsibility should be placed.
It depends what that means. Would these values cause a crash or a function to return an error? Also unless they are well documented in the nettle API documentation, I wouldn't expect the caller to know the constraints of the underlying gmp API.
regards, Nikos
On Sun, 31 Jul 2016 10:44:01 +0200 nisse@lysator.liu.se (Niels Möller) wrote:
Done now (or rather, added to the shared helper function _rsa_check_size).
I think this is incomplete. Looking at the patch: https://git.lysator.liu.se/nettle/nettle/commit/5eb30d94f6f5f3f0cb9ba9ed24bc...
You're only checking n (for both private and public keys), I could probably still craft a private key that crashes by choosing one of p or q to be even.
Any other easy checks for bogus keys that should be added? I would expect that code parsing key formats, e.g., asn.1, would check sign and range of parameters and catch bogus values early (e.g., the code in nettle's der2rsa.c does that). It's possible to add additional sanity checks to the _key_prepare functions, if desired.
Depends on how far you want to go. Easy checks: * d, e must not be 0, 1, 2
More expensive checks: * Make sure n = p * q * p, q prime
It's not entirely obvious where that responsibility should be placed.
Yeah, I've been thinking a bit about it yesterday, I could still see problems with this approach. E.g. imagine someone does sanity checks with openssl and then assumes the key can be used with a nettle-based TLS stack. Even if we prevent it from crashing it may still prevent something from starting.
I ended up wishing that there'd be a defined standard set of key sanity checks shared among implementations... but I'm probably just dreaming here...
Hanno Böck hanno@hboeck.de writes:
You're only checking n (for both private and public keys), I could probably still craft a private key that crashes by choosing one of p or q to be even.
Nettle's private key struct doesn't include n, it's computed as the product of p and q. So if either is even, n will be even too.
Depends on how far you want to go. Easy checks:
- d, e must not be 0, 1, 2
For public keys, with this fix, _prepare_key checks that n is odd and that |n| isn't too small. I'm considering adding the checks that n > 0, and 1 < e < n. In addition, the application ought to check that n isn't unreasonably large, to avoid denial of service, but I don't think that limit belongs in nettle.
For private keys, with the fix the same checks are applied to p * q. One could also check p > 0, q > 0, and that CRT parameters are in the expected range, 0 < a < p - 1, 0 < b < q - 1, 0 < c < p.
Yeah, I've been thinking a bit about it yesterday, I could still see problems with this approach.
I guess part of the problem is that key format standards, like pkcs#1, define valid ranges for parameters. But when using Nettle's rsa_public_key_prepare, the input isn't a key blob defined by some particular standard, but a couple of (big) integers.
Not sure if gnutls uses rsa_public_key_prepare directly, or via rsa_keypair_from_der.
I ended up wishing that there'd be a defined standard set of key sanity checks shared among implementations... but I'm probably just dreaming here...
Valid ranges are defined by key format standards (fine details might differ, I imagine, e.g., one may or may not require that p > q), but there are no standards for deeper sanity checks, as far as I'm aware.
Regards, /Niels
On Sun, Jul 31, 2016 at 10:44 AM, Niels Möller nisse@lysator.liu.se wrote:
nisse@lysator.liu.se (Niels Möller) writes:
I think it should be easy and reasonable to add code to rsa_public_key_prepare and rsa_private_key_prepare to check that the modulo is odd. What do you think? It's reasonable to have those functions do enough key validation to be able to handle the key without crashing.
Done now (or rather, added to the shared helper function _rsa_check_size).
But where is this helper function used? As far as I see it is not used by rsa_pkcs1_verify() or similar functions, and it only applies if rsa_public_key_prepare() is used; otherwise the crash still applies. Gnutls for example doesn't use any of the *prepare functions.
regards, Nikos
Nikos Mavrogiannopoulos n.mavrogiannopoulos@gmail.com writes:
But where is this helper function used? As far as I see it is not used by rsa_pkcs1_verify() or similar functions, and it only applies if rsa_public_key_prepare() is used; otherwise the crash still applies.
Correct.
Gnutls for example doesn't use any of the *prepare functions.
I think it should. It's a fairly well documented requirement:
: When you have assigned values to the attributes of a key, you must : call : : -- Function: int rsa_public_key_prepare (struct rsa_public_key *PUB) : -- Function: int rsa_private_key_prepare (struct rsa_private_key *KEY) : Computes the octet size of the key (stored in the ‘size’ attribute, : and may also do other basic sanity checks. Returns one if : successful, or zero if the key can’t be used, for instance if the : modulo is smaller than the minimum size needed for RSA operations : specified by PKCS#1.
Regards, /Niels
On Mon, Aug 1, 2016 at 9:59 AM, Niels Möller nisse@lysator.liu.se wrote:
Gnutls for example doesn't use any of the *prepare functions.
I think it should. It's a fairly well documented requirement: : When you have assigned values to the attributes of a key, you must : call
That can certainly be done on future versions; however it also means that if nettle is updated without an update on gnutls, the fix for cache silence may bring more issues than it solves.
regards, Nikos
Nikos Mavrogiannopoulos n.mavrogiannopoulos@gmail.com writes:
That can certainly be done on future versions; however it also means that if nettle is updated without an update on gnutls, the fix for cache silence may bring more issues than it solves.
I guess one can add some workaround for applications, in particuar gnutls, which don't use _prepare. But please fix that before you make the next release.
Do you think it is sufficient for gnutls to add an extra check that p and q are odd in nettle's rsa_compute_root? (Used also by rsa_compute_root_tr).
Regards, /Niels
On Wed, Aug 3, 2016 at 10:53 AM, Niels Möller nisse@lysator.liu.se wrote:
I guess one can add some workaround for applications, in particuar gnutls, which don't use _prepare. But please fix that before you make the next release.
My main concern is that rsa_private_key_prepare() multiplies q and p, and for gnutls it is a temporary object, i.e., constructed on the fly from the internal format for keys that gnutls uses. Switching to this function would mean an additional multiplication per RSA operation. The equivalent public key function is fine to use.
Said that, I have already replaced the manual setting of size with a call to the prepare functions, but I'd prefer the prepare functions to come at no significant cost (especially since when calling prepare I already know the size of n).
Do you think it is sufficient for gnutls to add an extra check that p and q are odd in nettle's rsa_compute_root? (Used also by rsa_compute_root_tr).
It makes sense for sanity check reasons as well (detect broken keys early rather than late).
regards, Nikos
Nikos Mavrogiannopoulos n.mavrogiannopoulos@gmail.com writes:
My main concern is that rsa_private_key_prepare() multiplies q and p,
I don't quite like that either, but I don't think it matters much for performance. The time for that multiplication is only a tiny fraction of the time needed to create a single signature.
It's needed to get the correct octet size of n. And it's possible to get rid of it in the common cases, although I'm not sure it's worth the effort.
Say sp is the bit size of p and sq is the bit size of q. Then sn, the bit size of n, is either sp + sq, or sp + sq - 1. And the octet size is ceil (sn / 8).
Now for typical RSA keys, p and q both have the top 2 bits set, and then we know that sn = sp + sq. Furthermore, typically sp + sq is a multiple of 8, but ceil ((sp + sq - 1)/8) differs from ceil ((sp + sq)/8) only if sp + sq = 1 (mod 8).
Do you think it is sufficient for gnutls to add an extra check that p and q are odd in nettle's rsa_compute_root? (Used also by rsa_compute_root_tr).
It makes sense for sanity check reasons as well (detect broken keys early rather than late).
I'll add that then.
Regards, /Niels
On Thu, 2016-08-04 at 09:53 +0200, Niels Möller wrote:
My main concern is that rsa_private_key_prepare() multiplies q and p,
I don't quite like that either, but I don't think it matters much for performance. The time for that multiplication is only a tiny fraction of the time needed to create a single signature.
That's correct, but it still bugs me as a cost that gets added into busy servers. What about adding a version of prepare that takes both the public key and the pubkey as in the attached patch?
regards, Nikos
Nikos Mavrogiannopoulos nmav@redhat.com writes:
That's correct, but it still bugs me as a cost that gets added into busy servers.
But only once per hostkey and server restart, right?
What about adding a version of prepare that takes both the public key and the pubkey as in the attached patch?
Makes some sense. But I wonder what the failure mode is if the input keys don't match, so that the rsa_private_key struct ends up with an incorrect size field?
One could also have an rsa_keypair_prepare that takes a pair of private and public keys, instead of calling the other two prepare functions. Similar issues if keys don't match as they are supposed to.
Regards, /Niels
On Fri, 2016-08-05 at 09:56 +0200, Niels Möller wrote:
Nikos Mavrogiannopoulos nmav@redhat.com writes:
That's correct, but it still bugs me as a cost that gets added into busy servers.
But only once per hostkey and server restart, right?
As it is now I do not set the size explicitly and call the prepare function on every RSA operation (sign/decrypt).
What about adding a version of prepare that takes both the public key and the pubkey as in the attached patch?
Makes some sense. But I wonder what the failure mode is if the input keys don't match, so that the rsa_private_key struct ends up with an incorrect size field?
That's correct, but I think that's the responsibility of the caller to supply the corresponding keys.
regards, Nikos
Nikos Mavrogiannopoulos nmav@redhat.com writes:
On Fri, 2016-08-05 at 09:56 +0200, Niels Möller wrote:
Nikos Mavrogiannopoulos nmav@redhat.com writes:
That's correct, but it still bugs me as a cost that gets added into busy servers.
But only once per hostkey and server restart, right?
As it is now I do not set the size explicitly and call the prepare function on every RSA operation (sign/decrypt).
Hmm. I'd imagine that you would create and initialize nettle's struct rsa_public_key and rsa_private_key at the time you read the key files on disk, and then that's also the right time to call _prepare. Is tharre any reason it's hard to organize that way?
That's correct, but I think that's the responsibility of the caller to supply the corresponding keys.
But I think we'de want to ensure that nettle doesn't crash; an application should be able to read key files controlled by an attacker and use them with nettle without crashing (bogus outputs are of course expected).
And I feel a little uneasy about ensuring that nettle's rsa functions work without crashing if the size field is too large or too small; that violates assumptions I made when writing the code quite some time ago... It might be not too difficult, but I'd feel better about having the _prepare functions be responsible for setting the size correctly.
Regards, /Niels
On Fri, Aug 5, 2016 at 8:57 PM, Niels Möller nisse@lysator.liu.se wrote:
That's correct, but I think that's the responsibility of the caller to supply the corresponding keys.
But I think we'de want to ensure that nettle doesn't crash; an application should be able to read key files controlled by an attacker and use them with nettle without crashing (bogus outputs are of course expected). And I feel a little uneasy about ensuring that nettle's rsa functions work without crashing if the size field is too large or too small; that violates assumptions I made when writing the code quite some time ago... It might be not too difficult, but I'd feel better about having the _prepare functions be responsible for setting the size correctly.
I think that's fair. And providing an efficient variant would be an incentive for applications to use them much easier. Anyway I believe I can work-around that.
regards, Nikos
nisse@lysator.liu.se (Niels Möller) writes:
Do you think it is sufficient for gnutls to add an extra check that p and q are odd in nettle's rsa_compute_root? (Used also by rsa_compute_root_tr).
On second look, it can't be rsa_compute_root, since that function has no return value. Is it sufficient for gnutls to do this check in rsa_compute_root_tr instead?
I also note that a check is needed in dsa_sign, which otherwise would crash if the group is invalid, with an even p.
Regards, /Niels
nisse@lysator.liu.se (Niels Möller) writes:
On second look, it can't be rsa_compute_root, since that function has no return value. Is it sufficient for gnutls to do this check in rsa_compute_root_tr instead?
I also note that a check is needed in dsa_sign, which otherwise would crash if the group is invalid, with an even p.
I've comitted additional checks to dsa_sign and rsa_compute_root_tr.
I have one remaining question: Should there be additional sanity checks in the rsa_*_prepare functions, to reject keys with negative or out-of-range parameters? Out-of-range parameters will not, as far as I am aware, result in any crashes, only in bogus outputs.
Regards, /Niels
On Thu, 2016-08-04 at 10:05 +0200, Niels Möller wrote:
nisse@lysator.liu.se (Niels Möller) writes:
Do you think it is sufficient for gnutls to add an extra check that p and q are odd in nettle's rsa_compute_root? (Used also by rsa_compute_root_tr).
On second look, it can't be rsa_compute_root, since that function has no return value. Is it sufficient for gnutls to do this check in rsa_compute_root_tr instead?
Yes. Although if this is only for the versions prior to using the prepare function, this is not a significant threat (the private key computations are typically done on trusted values by the server).
What is more important for older versions of gnutls are the public key operations such as ecdsa_verify(), dsa_verify() and rsa_encrypt().
regards, Nikos
Nikos Mavrogiannopoulos nmav@redhat.com writes:
Yes. Although if this is only for the versions prior to using the prepare function, this is not a significant threat (the private key computations are typically done on trusted values by the server).
One scanario is a web hosting provider that handles private server keys provided by untrusted customers. No idea how common that is, but one wouldn't want one customer to crash the webserver also used by others.
What is more important for older versions of gnutls are the public key operations such as ecdsa_verify(), dsa_verify() and rsa_encrypt().
Now I'm confused, I hope I didn't introduce any mpz_powm_sec calls on the code paths operating on public keys only? I don't think we have to care too much about obscure use cases where the supposedly public exponent actually needs to be well protected.
Regards, /Niels
On Fri, 2016-08-05 at 10:04 +0200, Niels Möller wrote:
Nikos Mavrogiannopoulos nmav@redhat.com writes:
Yes. Although if this is only for the versions prior to using the prepare function, this is not a significant threat (the private key computations are typically done on trusted values by the server).
One scanario is a web hosting provider that handles private server keys provided by untrusted customers. No idea how common that is, but one wouldn't want one customer to crash the webserver also used by others.
right.
What is more important for older versions of gnutls are the public key operations such as ecdsa_verify(), dsa_verify() and rsa_encrypt().
Now I'm confused, I hope I didn't introduce any mpz_powm_sec calls on the code paths operating on public keys only? I don't think we have to care too much about obscure use cases where the supposedly public exponent actually needs to be well protected.
Correct, it seems I replied prior to thinking.
regards, Nikos
nettle-bugs@lists.lysator.liu.se
-
Daniel Kahn Gillmor -
Hanno Böck -
Nikos Mavrogiannopoulos -
Nikos Mavrogiannopoulos -
nisse＠lysator.liu.se