On Fri, Sep 4, 2015 at 8:49 AM, Niels Möller <[email protected]> wrote:
>> 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.
The issue with signatures is that you send or store the output once
calculated and that can be observed by an adversary. When decrypting I
don't think the threat model is the same. At least for the purposes of
TLS protecting decryption wouldn't add anything.
> 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).
I don't think that would be necessary (see above for the decrypt function).
>> + /* 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.
Good idea.
>> --- 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).
Would that make sense if we deprecate everything else? I thought that
everything else is deprecated first should be listed the recommended
functions, rather than trying to look for them within a very long list
of deprecated functions.
> Side-channel resistance isn't relevant for verify.
I made that clear.
> (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).
That would be indeed useful (though unrelated with this patch set).
>> +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.
That's pretty sad. It means that applications couldn't take advantage
of that without being rewritten.
In any case the attached patch set should address all your comments.
regards,
Nikos
From 9a59ad5a3d96bde3be81c9542328403a958a442d Mon Sep 17 00:00:00 2001
From: Nikos Mavrogiannopoulos <[email protected]>
Date: Thu, 3 Sep 2015 10:20:37 +0200
Subject: [PATCH 1/3] 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 | 49 ++++++++++++++++++++++++++++++++++++++++---------
1 file changed, 40 insertions(+), 9 deletions(-)
diff --git a/rsa-pkcs1-sign-tr.c b/rsa-pkcs1-sign-tr.c
index 0f3a5a2..f2b3e45 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,34 @@ 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)
+ {
+ mpz_set_ui(s, 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 363c217483f7d92e77d251317642434b5e76e9f0 Mon Sep 17 00:00:00 2001
From: Nikos Mavrogiannopoulos <[email protected]>
Date: Thu, 3 Sep 2015 10:43:13 +0200
Subject: [PATCH 2/3] testsuite: Added tests for rsa_pkcs1_sign_tr()
---
testsuite/Makefile.in | 2 +-
testsuite/rsa-sign-tr.c | 194 ++++++++++++++++++++++++++++++++++++++++++++++++
testsuite/testutils.h | 7 ++
3 files changed, 202 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..fbe8e5c
--- /dev/null
+++ b/testsuite/rsa-sign-tr.c
@@ -0,0 +1,194 @@
+#include "testutils.h"
+#include "knuth-lfib.h"
+#include "nettle-internal.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")
+
+static void
+test_rsa_sign_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);
+
+ /* Try bad private key */
+ mpz_add_ui(key->p, key->p, 2);
+
+ ASSERT(!rsa_pkcs1_sign_tr(pub, key,
+ &lfib, (nettle_random_func *) knuth_lfib_random,
+ di_length, di, signature));
+
+ mpz_sub_ui(key->p, key->p, 2);
+
+ ASSERT(!mpz_cmp_ui(signature, 0));
+
+ /* Try the good private key */
+ 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, (void*)"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_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_sign_tr(&pub, &key, sizeof(MSG1)-1, MSG1, expected);
+
+ mpz_set_str(expected,
+ "86114b62c2d22e2c9b075852df18dfb60c2f86ae8c4a852aff5db7"
+ "164984b1ca3752ae0c1174604ceb46bc72870e87687e298210b88b"
+ "48d0c5ac039c94a40349aaea1399aa60d953697916fbe5020c6751"
+ "060e114588a9ef14751326432d564863d4e11e1e73dabd1f628c6e"
+ "8866f8072d2a2dfd10d716d5d07a6ee57", 16);
+
+ test_rsa_sign_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_sign_tr(&pub, &key, sizeof(MSG1)-1, MSG1, expected);
+
+ /* Test sha1 signature */
+ mpz_set_str(expected,
+ "9f87de78ee3c6df00444b290aef88765c8367a166e3aeb7e4de0fb"
+ "94a38a48452902f6cd5ebefbd1eaa095ca855e565c1d95c4d8ef2d"
+ "3962a4c707001e1e2112028bda4c78d2d303b11b6cae33a777fd4d"
+ "96d766be5e1bff00defc7628a8a7e8a0", 16);
+
+ test_rsa_sign_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.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 f932d48c010a0b87260df8757183f6f68b32a726 Mon Sep 17 00:00:00 2001
From: Nikos Mavrogiannopoulos <[email protected]>
Date: Thu, 3 Sep 2015 11:55:19 +0200
Subject: [PATCH 3/3] doc: mention rsa_pkcs1_sign_tr() and rsa_pkcs1_verify()
---
nettle.texinfo | 10 +++++++++-
1 file changed, 9 insertions(+), 1 deletion(-)
diff --git a/nettle.texinfo b/nettle.texinfo
index 7fe2471..bdad236 100644
--- a/nettle.texinfo
+++ b/nettle.texinfo
@@ -3646,7 +3646,15 @@ 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.
+The functions with a '_tr' suffix provide a side-channel (fault and timing) resistant implementation when relevant.
+@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_decrypt_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}, uint8_t *@var{message}, const mpz_t @var{gibberish});
+@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});
+@end deftypefun
+
+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
