On Thu, Dec 19, 2013 at 11:46 AM, Niels Möller <[email protected]> wrote:
>> It seems that some guys managed to "listen" gnupg private keys. While
>> some parts of the attack are gnupg specific, similar attacks could
>> apply in nettle as well (and I guess every implementation that does
>> RSA decryption).
> I have only had a very quick look at the paper.
>> I see on their mitigation section that "ciphertext normalization",
>> i.e., c=c%n, avoids their key recovery attack,
> Wouldn't it make more sense to simply reject ciphertexts with c >= n?
> And since this condition depends on no secret information, there's no
> harm in returning failure early in this case, right?
Yes. That would also avoid the complex patch (which should be now attached).
> Or do they mean c >= q, where q is the secret factor? I think the right
> way for the CRT processing is to always zero pad c to the same size of
> n, and then reduce it mod p and mod q using a side-channel silent
> reduction algorithm. Not entirely trivial to do with the mpz interface,
> though.
My understanding was that c>=n.
> On mitigation, it also sounds like RSA blinding (which you implemented a
> while ago) is effective. It ought to be effective against any attacks
> relying on *chosen* ciphertexts.
Indeed. I realized after that gnupg's code didn't use the blinding
part (that attack
worked on the old gnupg versions, something that isn't very apparent
in the paper :)
However, checking for ciphertext validity prior to getting to the actual
operation is a good thing to have. Not as serious as I initially thought though.
regards,
Nikos
diff --git a/rsa-decrypt-tr.c b/rsa-decrypt-tr.c
index 4705137..33ea3d5 100644
--- a/rsa-decrypt-tr.c
+++ b/rsa-decrypt-tr.c
@@ -47,7 +47,7 @@ rsa_decrypt_tr(const struct rsa_public_key *pub,
mpz_init (ri);
_rsa_blind (pub, random_ctx, random, m, ri);
- rsa_compute_root(key, m, m);
+ rsa_compute_root_ar(pub, key, m, m);
_rsa_unblind (pub, m, ri);
mpz_clear (ri);
diff --git a/rsa-pkcs1-sign-tr.c b/rsa-pkcs1-sign-tr.c
index 16de2f9..31417c5 100644
--- a/rsa-pkcs1-sign-tr.c
+++ b/rsa-pkcs1-sign-tr.c
@@ -45,7 +45,7 @@ rsa_pkcs1_sign_tr(const struct rsa_public_key *pub,
mpz_init (ri);
_rsa_blind (pub, random_ctx, random, s, ri);
- rsa_compute_root(key, s, s);
+ rsa_compute_root_ar(pub, key, s, s);
_rsa_unblind (pub, s, ri);
mpz_clear (ri);
diff --git a/rsa-sign.c b/rsa-sign.c
index 56adda3..cc80faa 100644
--- a/rsa-sign.c
+++ b/rsa-sign.c
@@ -78,13 +78,20 @@ rsa_private_key_prepare(struct rsa_private_key *key)
/* Computing an rsa root. */
void
-rsa_compute_root(const struct rsa_private_key *key,
- mpz_t x, const mpz_t m)
+rsa_compute_root_ar(const struct rsa_public_key *pub,
+ const struct rsa_private_key *key,
+ mpz_t x, const mpz_t _m)
{
mpz_t xp; /* modulo p */
mpz_t xq; /* modulo q */
+ mpz_t m; /* m=_m mod n */
+
+ mpz_init(xp); mpz_init(xq); mpz_init(m);
- mpz_init(xp); mpz_init(xq);
+ if (pub != NULL)
+ mpz_fdiv_r(m, _m, pub->n);
+ else
+ mpz_set(m, _m);
/* Compute xq = m^d % q = (m%q)^b % q */
mpz_fdiv_r(xq, m, key->q);
@@ -132,5 +139,12 @@ rsa_compute_root(const struct rsa_private_key *key,
mpz_mul(x, key->q, xp);
mpz_add(x, x, xq);
- mpz_clear(xp); mpz_clear(xq);
+ mpz_clear(xp); mpz_clear(xq); mpz_clear(m);
+}
+
+void
+rsa_compute_root(const struct rsa_private_key *key,
+ mpz_t x, const mpz_t m)
+{
+ return rsa_compute_root_ar(NULL, key, x, m);
}
diff --git a/rsa.h b/rsa.h
index 38455a7..34c0992 100644
--- a/rsa.h
+++ b/rsa.h
@@ -67,6 +67,7 @@ extern "C" {
#define rsa_decrypt nettle_rsa_decrypt
#define rsa_decrypt_tr nettle_rsa_decrypt_tr
#define rsa_compute_root nettle_rsa_compute_root
+#define rsa_compute_root_ar nettle_rsa_compute_root_ar
#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
@@ -307,6 +308,12 @@ void
rsa_compute_root(const struct rsa_private_key *key,
mpz_t x, const mpz_t m);
+/* The acoustic resistant version: http://www.cs.tau.ac.il/~tromer/acoustic/ */
+void
+rsa_compute_root_ar(const struct rsa_public_key *pub,
+ const struct rsa_private_key *key,
+ mpz_t x, const mpz_t m);
+
/* Key generation */
_______________________________________________
nettle-bugs mailing list
[email protected]
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
