On Wed, Sep 2, 2015 at 4:05 PM, Florian Weimer <[email protected]> wrote: > I strongly suggest to implement RSA-CRT hardening, by checking that RSA > signature have not been miscomputed accidentally: > <https://securityblog.redhat.com/2015/09/02/factoring-rsa-keys-with-tls-perfect-forward-secrecy/> > <https://people.redhat.com/~fweimer/rsa-crt-leaks.pdf> > We did not see any key leaks which could be attributed to Nettle, but I > think the added verification is still a reasonable precaution.
Unfortunately for most of the functions available in nettle this counter-measure cannot be implemented without changing the API. 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. I attach a small patch which verifies the output of this signing function. Niels, what about the rest of the functions? They can protect from neither timing nor fault attacks. I also attach the patch which marks them as such in the manual. regards, Nikos
From 69748c6d0aa20597b5e002983f3bed0e0c42d994 Mon Sep 17 00:00:00 2001 From: Nikos Mavrogiannopoulos <[email protected]> Date: Thu, 3 Sep 2015 10:20:37 +0200 Subject: [PATCH 1/2] Enhanced rsa_pkcs1_sign_tr() to protect against HW/software errors That verifies the output of the timing-resistant version of the signing function, to make it also fault-resistant. --- rsa-pkcs1-sign-tr.c | 46 +++++++++++++++++++++++++++++++++++++--------- 1 file changed, 37 insertions(+), 9 deletions(-) diff --git a/rsa-pkcs1-sign-tr.c b/rsa-pkcs1-sign-tr.c index 0f3a5a2..6237845 100644 --- a/rsa-pkcs1-sign-tr.c +++ b/rsa-pkcs1-sign-tr.c @@ -34,11 +34,31 @@ #if HAVE_CONFIG_H # include "config.h" #endif - #include "rsa.h" #include "pkcs1.h" +/* Checks for any errors done in the RSA computation. That avoids + * attacks which rely on faults on hardware, or even software MPI + * implementation. */ +static int +rsa_verify_res(const struct rsa_public_key *pub, + mpz_t s, mpz_t m) +{ + mpz_t t; + int res; + + mpz_init(t); + + mpz_powm(t, s, pub->e, pub->n); + + res = !mpz_cmp(m, t); + + mpz_clear(t); + return res; +} + +/* Side-channel resistant version of rsa_pkcs1_sign() */ int rsa_pkcs1_sign_tr(const struct rsa_public_key *pub, const struct rsa_private_key *key, @@ -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); } else { mpz_set_ui(s, 0); - return 0; + ret = 0; } + mpz_clear(m); + return ret; } -- 2.4.3
From 38f70b8e9f825218a9152f00db1d327b2e2ff4dd Mon Sep 17 00:00:00 2001 From: Nikos Mavrogiannopoulos <[email protected]> Date: Thu, 3 Sep 2015 10:43:13 +0200 Subject: [PATCH 2/2] testsuite: Added tests for rsa_pkcs1_sign_tr() --- testsuite/Makefile.in | 2 +- testsuite/rsa-sign-tr.c | 137 ++++++++++++++++++++++++++++++++++++++++++++++++ testsuite/testutils.c | 42 +++++++++++++++ testsuite/testutils.h | 7 +++ 4 files changed, 187 insertions(+), 1 deletion(-) create mode 100644 testsuite/rsa-sign-tr.c diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in index 426fe1a..6711628 100644 --- a/testsuite/Makefile.in +++ b/testsuite/Makefile.in @@ -35,7 +35,7 @@ TS_NETTLE_SOURCES = aes-test.c arcfour-test.c arctwo-test.c \ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \ rsa2sexp-test.c sexp2rsa-test.c \ bignum-test.c random-prime-test.c \ - pkcs1-test.c \ + pkcs1-test.c rsa-sign-tr.c \ rsa-test.c rsa-encrypt-test.c rsa-keygen-test.c \ dsa-test.c dsa-keygen-test.c \ curve25519-dh-test.c \ diff --git a/testsuite/rsa-sign-tr.c b/testsuite/rsa-sign-tr.c new file mode 100644 index 0000000..211dcde --- /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") + +void +test_main(void) +{ + struct rsa_public_key pub; + struct rsa_private_key key; + + mpz_t expected; + + mpz_init(expected); + + rsa_private_key_init(&key); + rsa_public_key_init(&pub); + + test_rsa_set_key_1(&pub, &key); + + /* Test signatures */ + mpz_set_str(expected, + "5a1d95b71a244dec17887b3fa4502439fd9d868ee12f716fbb53b2" + "e7ca60e6922bfdb893cd62dba8e16ca7a4374962d407b6137b4322" + "c76331588e087c823162349e40bb0cca762c7f253ea46141f88118" + "78788b0759e2c880a089ecbdf447ea02ffa504336cb65bd79f20e1" + "3d9af6ac5ac49656fa5cc06cae4f9df510", + 16); + + test_rsa_tr(&pub, &key, sizeof(MSG1)-1, MSG1, expected); + + mpz_set_str(expected, + "86114b62c2d22e2c9b075852df18dfb60c2f86ae8c4a852aff5db7" + "164984b1ca3752ae0c1174604ceb46bc72870e87687e298210b88b" + "48d0c5ac039c94a40349aaea1399aa60d953697916fbe5020c6751" + "060e114588a9ef14751326432d564863d4e11e1e73dabd1f628c6e" + "8866f8072d2a2dfd10d716d5d07a6ee57", 16); + + test_rsa_tr(&pub, &key, sizeof(MSG2)-1, MSG2, expected); + + /* 777-bit key, generated by + * + * lsh-keygen -a rsa -l 777 -f advanced-hex + * + * Interesting because the size of n doesn't equal the sum of the + * sizes of p and q. + * + * (private-key (rsa-pkcs1 + * (n #013b04440e3eef25 d51c738d508a7fa8 b3445180c342af0f + * 4cb5a789047300e2 cfc5c5450974cfc2 448aeaaa7f43c374 + * c9a3b038b181f2d1 0f1a2327fd2c087b a49bf1086969fd2c + * d1df3fd69f81fa4b 162cc8bbb363fc95 b7b24b9c53d0c67e + * f52b#) + * (e #3f1a012d#) + * (d #f9bae89dacca6cca c21e0412b4df8355 6fe7c5322bbae8ad + * 3f11494fd12bc076 d4a7da3050fe109d 2074db09cc6a93b4 + * 745479522558379e a0ddfa74f86c9e9e a22c3b0e93d51447 + * 0feb38105dd35395 63b91ee32776f40c 67b2a175690f7abb + * 25#) + * (p #0b73c990eeda0a2a 2c26416052c85560 0c5c0f5ce86a8326 + * 166acea91786237a 7ff884e66dbfdd3a ab9d9801414c1506 + * 8b#) + * (q #1b81c19a62802a41 9c99283331b0badb 08eb0c25ffce0fbf + * 50017850036f32f3 2132a845b91a5236 61f7b451d587383f + * e1#) + * (a #0a912fc93a6cca6b 3521725a3065b3be 3c9745e29c93303d + * 7d29316c6cafa4a2 89945f964fcdea59 1f9d248b0b6734be + * c9#) + * (b #1658eca933251813 1eb19c77aba13d73 e0b8f4ce986d7615 + * 764c6b0b03c18146 46b7f332c43e05c5 351e09006979ca5b + * 05#) + * (c #0114720dace7b27f 2bf2850c1804869f 79a0aad0ec02e6b4 + * 05e1831619db2f10 bb9b6a8fd5c95df2 eb78f303ea0c0cc8 + * 06#))) + */ + + mpz_set_str(pub.n, + "013b04440e3eef25" "d51c738d508a7fa8" "b3445180c342af0f" + "4cb5a789047300e2" "cfc5c5450974cfc2" "448aeaaa7f43c374" + "c9a3b038b181f2d1" "0f1a2327fd2c087b" "a49bf1086969fd2c" + "d1df3fd69f81fa4b" "162cc8bbb363fc95" "b7b24b9c53d0c67e" + "f52b", 16); + + mpz_set_str(pub.e, "3f1a012d", 16); + + ASSERT (rsa_public_key_prepare(&pub)); + + mpz_set_str(key.p, + "0b73c990eeda0a2a" "2c26416052c85560" "0c5c0f5ce86a8326" + "166acea91786237a" "7ff884e66dbfdd3a" "ab9d9801414c1506" + "8b", 16); + + mpz_set_str(key.q, + "1b81c19a62802a41" "9c99283331b0badb" "08eb0c25ffce0fbf" + "50017850036f32f3" "2132a845b91a5236" "61f7b451d587383f" + "e1", 16); + + mpz_set_str(key.a, + "0a912fc93a6cca6b" "3521725a3065b3be" "3c9745e29c93303d" + "7d29316c6cafa4a2" "89945f964fcdea59" "1f9d248b0b6734be" + "c9", 16); + + mpz_set_str(key.b, + "1658eca933251813" "1eb19c77aba13d73" "e0b8f4ce986d7615" + "764c6b0b03c18146" "46b7f332c43e05c5" "351e09006979ca5b" + "05", 16); + + mpz_set_str(key.c, + "0114720dace7b27f" "2bf2850c1804869f" "79a0aad0ec02e6b4" + "05e1831619db2f10" "bb9b6a8fd5c95df2" "eb78f303ea0c0cc8" + "06", 16); + + ASSERT (rsa_private_key_prepare(&key)); + ASSERT (pub.size == key.size); + + /* Test signatures */ + mpz_set_str(expected, + "63629074879115869fbe830c7cd28ac7fb87df06312572428ba412" + "f730f1f88e1f26cd60955a7ff81743bb0f8a0ebb4a05ad621544b3" + "2d189b436f753de1dcdf9d29ae048585f1408397dcf9381324498e" + "c7df9d35f7b221ec1a2a9e426e07ca8b", 16); + + test_rsa_tr(&pub, &key, sizeof(MSG1)-1, MSG1, expected); + + /* Test sha1 signature */ + mpz_set_str(expected, + "9f87de78ee3c6df00444b290aef88765c8367a166e3aeb7e4de0fb" + "94a38a48452902f6cd5ebefbd1eaa095ca855e565c1d95c4d8ef2d" + "3962a4c707001e1e2112028bda4c78d2d303b11b6cae33a777fd4d" + "96d766be5e1bff00defc7628a8a7e8a0", 16); + + test_rsa_tr(&pub, &key, sizeof(MSG2)-1, MSG2, expected); + + rsa_private_key_clear(&key); + rsa_public_key_clear(&pub); + mpz_clear(expected); +} diff --git a/testsuite/testutils.c b/testsuite/testutils.c index 1ef04c9..efbbc93 100644 --- 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)); + + mpz_clear(signature); +} + +void test_rsa_md5(struct rsa_public_key *pub, struct rsa_private_key *key, mpz_t expected) diff --git a/testsuite/testutils.h b/testsuite/testutils.h index 405f89f..c43c70b 100644 --- a/testsuite/testutils.h +++ b/testsuite/testutils.h @@ -190,6 +190,13 @@ test_rsa_set_key_1(struct rsa_public_key *pub, struct rsa_private_key *key); void +test_rsa_tr(struct rsa_public_key *pub, + struct rsa_private_key *key, + unsigned di_length, + const uint8_t *di, + mpz_t expected); + +void test_rsa_md5(struct rsa_public_key *pub, struct rsa_private_key *key, mpz_t expected); -- 2.4.3
From cb4c2839e2b2df12d6fd29fe481d7c2d688ff92d Mon Sep 17 00:00:00 2001 From: Nikos Mavrogiannopoulos <[email protected]> Date: Thu, 3 Sep 2015 11:55:19 +0200 Subject: [PATCH] doc: mention rsa_pkcs1_sign_tr() and rsa_pkcs1_verify() --- nettle.texinfo | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) diff --git a/nettle.texinfo b/nettle.texinfo index 7fe2471..2bcdb2e 100644 --- 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}); + + +Other functions are also available but cannot be used by application that require +a side-channel silent implementation. These are listed below. @deftypefun int rsa_md5_sign (const struct rsa_private_key *@var{key}, struct md5_ctx *@var{hash}, mpz_t @var{signature}) @deftypefunx int rsa_sha1_sign (const struct rsa_private_key *@var{key}, struct sha1_ctx *@var{hash}, mpz_t @var{signature}) -- 2.4.3
_______________________________________________ nettle-bugs mailing list [email protected] http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
