Re: RSA-CRT hardening

Nikos Mavrogiannopoulos n.mavrogiannopoulos@gmail.com writes:

Said that, there is rsa_pkcs1_sign_tr() which is supposed to be the side-channel resistant version of rsa_pkcs1_sign() and can have this additional check with no changes.

What about rsa_decrypt_tr? Does it also need this check? Attacks are a bit harder since even with known plaintext, there's padding that is supposed to be random. But I imagine it's possible with improved attacks that either work with partial knowledge, or exploit weeknesses in the randomness used for padding.

I attach a small patch which verifies the output of this signing function.

Thanks. Some comments below.

Niels, what about the rest of the functions?

Not sure, maybe we can try to deprecate the signing functions. I guess it's possible to "fix" them by recomputing the public key from the private key, but that's a bit awkward, and if the point is to guard against incorrect computations using secret data, maybe one shouldn't trust that computation either.

@@ -46,23 +66,31 @@ rsa_pkcs1_sign_tr(const struct rsa_public_key *pub, size_t length, const uint8_t *digest_info, mpz_t s) {

• mpz_t ri;

• mpz_t ri, m;
• int ret;
• mpz_init(m);

• if (pkcs1_rsa_digest_encode (s, key->size, length, digest_info))

• if (pkcs1_rsa_digest_encode (m, key->size, length, digest_info)) { mpz_init (ri);

•  _rsa_blind (pub, random_ctx, random, s, ri);
  

•  rsa_compute_root(key, s, s);
  

•  _rsa_unblind (pub, s, ri);
  

•  _rsa_blind (pub, random_ctx, random, m, ri);
  

•  rsa_compute_root(key, s, m);
  
  

•  mpz_clear (ri);
  

•  if (rsa_verify_res(pub, s, m) == 0)
  

•    ret = 0;
  

•  else
  

•    ret = 1;
  
  

•  return 1;
  

•  _rsa_unblind (pub, s, ri);
  

•  mpz_clear (ri);
  

  }

Maybe factor out a function rsa_compute_root_tr (in particular, that would be useful if we want the same check in rsa_decrypt_tr). And as Florian pointed out, it seems reasonable to set s = 0 on all failure cases.

I've consided if maybe we can just abort() if the check fails, but since we do have a return value, we can just as well use that. And the check can trigger also for an invalid private key, and in that case, an abort() is maybe a bit too unfriendly.

--- /dev/null +++ b/testsuite/rsa-sign-tr.c @@ -0,0 +1,137 @@ +#include "testutils.h"

+#define MSG1 ((uint8_t*)"None so blind as those who will not see") +#define MSG2 ((uint8_t*)"Fortune knocks once at every man's door")

[...]

• test_rsa_tr(&pub, &key, sizeof(MSG1)-1, MSG1, expected);

If this is the only use of test_rsa_tr, maybe put it directly in this file. And it's not obvious from the name if it tests signing or encryption or both.

--- a/testsuite/testutils.c +++ b/testsuite/testutils.c @@ -765,6 +765,48 @@ test_rsa_set_key_1(struct rsa_public_key *pub, }

void +test_rsa_tr(struct rsa_public_key *pub,

•     struct rsa_private_key *key,
  

•     unsigned di_length,
  

•     const uint8_t *di,
  

•     mpz_t expected)
  

+{

• mpz_t signature;
• struct knuth_lfib_ctx lfib;
• knuth_lfib_init(&lfib, 1111);
• mpz_init(signature);
• ASSERT(rsa_pkcs1_sign_tr(pub, key,

•     &lfib, (nettle_random_func *) knuth_lfib_random,
  

•     di_length, di, signature));
  

• if (verbose)
• {

•  fprintf(stderr, "rsa-pkcs1-tr signature: ");
  

•  mpz_out_str(stderr, 16, signature);
  

•  fprintf(stderr, "\nrsa-pkcs1-tr expected: ");
  

•  mpz_out_str(stderr, 16, expected);
  

•  fprintf(stderr, "\n");
  

• }
• ASSERT (mpz_cmp(signature, expected) == 0);
• /* Try bad data */
• ASSERT (!rsa_pkcs1_verify(pub, 16, "The magick words", signature));
• /* Try correct data */
• ASSERT (rsa_pkcs1_verify(pub, di_length, di, signature));
• /* Try bad signature */
• mpz_combit(signature, 17);
• ASSERT (!rsa_pkcs1_verify(pub, di_length, di, signature));

It would be good to also do a test with an invalid private key, e.g, using p+2 instead of p. That should trigger the new check, so that rsa_pkcs1_sign_tr returns failure and sets s == 0.

--- a/nettle.texinfo +++ b/nettle.texinfo @@ -3646,7 +3646,14 @@ There is currently no support for using SHA224 or SHA384 with @acronym{RSA} signatures, since there's no gain in either computation time nor message size compared to using SHA256 and SHA512, respectively.

-Creation and verification of signatures is done with the following functions: +Creation and verification of signatures is recommended to be done with the following functions. +They provide a side-channel (fault and timing) resistant implementation. +@deftypefun int rsa_pkcs1_sign_tr(const struct rsa_public_key *@var{pub}, const struct rsa_private_key *@var{key}, void *@var{random_ctx}, nettle_random_func *@var{random}, size_t @var{length}, const uint8_t *@var{digest_info}, mpz_t @var{s}); +@deftypefunx int rsa_pkcs1_verify(const struct rsa_public_key *@var{key}, size_t @var{length}, const uint8_t *digest_info, const mpz_t @var{signature});

I wasn't aware that these functions lacked documentation. Good catch. I think we need to say something about the digest_info argument.

I think the rsa_pkcs1_verify function should move to the other verify functions (and be at the top of that list, if it's the recommended one). Side-channel resistance isn't relevant for verify.

And there's an @end deftypefun missing, isn't it?

(We may also need some public functions for constructing digest_infos, a bit like pkcs1_rsa_sha256_encode. But the current internal functions don't fit well with rsa_pkcs1_sign_tr. So the "CRT-hardening" fixes shouldn't block on that).

+Other functions are also available but cannot be used by application that require +a side-channel silent implementation. These are listed below.

For improved side-channel silence, one could also let rsa_compute_root use mpz_powm_sec if available. But the current GMP plans are to not try to provide side-schannel silent functions on the mpz level (mpz_powm_sec is an exception), so to really take advantage of GMP improvements in side-channel silence, one would need to move to using the lower-level mpn interface.

Regards, /Niels