Subject: [TLS] Breaking 4096-bit RSA with an Acoustic Cryptanalysis attack

From: Mohamad Badra <[email-masked]>
Date: Mon, 23 Dec 2013 15:02:04 +0400

http://www.tau.ac.il/~tromer/papers/acoustic-20131218.pdf

---

From: Alyssa Rowan <[email-masked]>
Date: Mon, 23 Dec 2013 11:22:07 +0000

>http://www.tau.ac.il/~tromer/papers/acoustic-20131218.pdf

Interesting work, following up their paper from 2004.

Wonder how this impacts common TLS libraries? We should evaluate. Whatever countermeasures are good for GnuPG are probably also applicable to OpenSSL, and the like... would the attack perhaps be more practical, given TLS is online and GnuPG usually not? Or less, given the way RSA (and DHE?) is used in TLS? Thoughts?

I note some new primitives like Curve25519, its faster (but equivalent) cousin Ed25519 and the larger Curve3617 use constant-time ladders and no data-dependent branches, and would address this issue going forward if adopted.

- --
/akr

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Mon, 23 Dec 2013 12:49:12 +0100

On Mon, 2013-12-23 at 11:22 +0000, Alyssa Rowan wrote:
> Wonder how this impacts common TLS libraries? We should evaluate.
> Whatever countermeasures are good for GnuPG are probably also
> applicable to OpenSSL, and the like... would the attack perhaps be more
> practical, given TLS is online and GnuPG usually not? Or less, given
> the way RSA (and DHE?) is used in TLS? Thoughts?

As far as I understand the attack, it applies to RSA implementations
that don't involve blinding. That's why they target gnupg 1.4 (and
not the latest gnupg 2.x versions). I believe that all the TLS
implementations have RSA blinding enabled. Nevertheless the mitigation
section of the paper has some good advice (e.g., on making sure that
the encrypted value is within the expected range).

regards,
Nikos

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 26 Dec 2013 18:03:07 +0000

On 26/12/2013 17:26, Manuel Pégourié-Gonnard wrote:

> I don't agree with all of this statement: Curve25519 (and similar
> curves) come with a convenient ladder indeed, but "no
> data-dependent branches" is a property of the implementation, not
> of the curve/primitive itself.

A fair point! A better wording on my part would have been that it's
easier and faster to implement these new curves in a manner that
avoids side-channel attacks than it is older, comparable primitives.

As you correctly point out, great care is still required. There exist
possible implementations of both Montgomery and Edwards ladders that
exhibit cache and timing attacks: perhaps we should specifically point
out that these are to be avoided, in any I-D which specifies the use
of these curves.

They seem so useful that I anticipate at this stage that TLS1.3 may be
greatly benefitted by using them for EdDSA, key exchange/forward
security, and possibly ClientHello encryption - I personally can't
think of a more suitable contender.

- -- 
/akr

---

From: Samuel Neves <[email-masked]>
Date: Thu, 26 Dec 2013 18:52:42 +0000

> avoids side-channel attacks than it is older, comparable primitives.

Montgomery (and most other) ladders are agnostic of the underlying
group, and can be used in RSA, DSA, etc (cf. [1]).

The reason they are not extremely popular outside of Montgomery curves
with x-only coordinates is that they are not very fast: 2 log(e) group
operations versus log(e) + log(e)/k + 2^k for k-ary approaches.

[1] http://www.joye.site88.net/papers/JY03mont.pdf

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Thu, 26 Dec 2013 18:26:21 +0100

On 23/12/2013 12:22, Alyssa Rowan wrote:
> I note some new primitives like Curve25519, its faster (but equivalent)
> cousin Ed25519 and the larger Curve3617 use constant-time ladders and no
> data-dependent branches, and would address this issue going forward if
> adopted.
> 
I don't agree with all of this statement: Curve25519 (and similar curves) come
with a convenient ladder indeed, but "no data-dependent branches" is a property
of the implementation, not of the curve/primitive itself.

More specifically, the core of the the Montgomery ladder is:

  * for i from 0 to m do
     * if d[i] = 0 then
        * R1, R0 := R0 + R1, 2R0
     * else
        * R0, R1 := R0 + R1, 2R1

which has a branch depending directly on the bits d[i] of the secret exponent d.
It can easily be rewritten as

  * for i from 0 to m do
     * R[ 1-d[i] ], R[ d[i] ] = R0 + R1, 2R[ d[i] ]

which has no secret-data-dependent branches, but still has secret-data-dependent
memory access patterns. Additional care in the implementation (namely,
constant-time conditional swap) is required to avoid this potential source of
information leakage.

So, while it is true that Curve25519 & Co are easier to implement safely (in
PolarSSL, the code for Curve25519 is 4 times shorter and simpler that the code
for short Weierstrass curves, with comparable safety), and perform better than
short Weierstrass curves (for comparable implementations), some security
properties such as (1) "no secret-data-dependant branches" and (2) "no
secret-data-dependant memory access patterns" (and one might want to add (3)
"constant-time field arithmetic or coordinates randomisation") still do no come
for free with these curves and depend on the implementation.

Manuel.