Subject: [TLS] ChaCha20 + Poly1305 in TLS

From: Adam Langley <[email-masked]>
Date: Tue, 10 Sep 2013 11:22:38 -0400

I've just posted a draft defining ChaCha20+Poly1305 cipher suites for
TLS: https://datatracker.ietf.org/doc/draft-agl-tls-chacha20poly1305/

(To those who might not read this mailing list all the time, this was
prompted by attacks on RC4 and CBC mode earlier this year and is not a
response to any recent press stories.)

Neither RC4 nor the current CBC modes are looking very attractive in
light of recent attacks. AES-GCM is in the process of being deployed
but both AES and GHASH are very troublesome to implement in software
in a way that is fast, secure and has good key agility.

Modern Intel chips implement AES-GCM in hardware and future, high-end
ARM chips may also. But I expect that there will always be a large
number of devices without that capability and there are currently no
good options for them in TLS.

I know that Nikos presented about using Salsa20+UMAC at the last
meeting and, although close to this proposal, I obviously made some
different choices.

I picked ChaCha20 over Salsa20. ChaCha20[1] is a tweak of Salsa20 to
achieve better diffusion. It is conjectured to be stronger than
Salsa20 and an attack against a reduced round Salsa20 in [2] broke one
fewer rounds of ChaCha20.

ChaCha20 received some positive remarks at the CFRG[3] and is slightly
faster. Salsa20 has been the target of more analysis.

Overall, I weakly preferred ChaCha20 over Salsa20.

I picked Poly1305 over UMAC/VMAC. UMAC/VMAC have a clear speed
advantage (~2x) on high-end chips when key agility isn't important and
Nikos indicated that such a scenario is important to him[4]. However,
I think that use case is likely to be met with hardware AES-GCM
implementations.

Otherwise, I like the conceptual simplicity of Poly1305, the lack of
precomputed tables, and the theoretical benefits of randomly varying
the point at which the polynomial is evaluated. It is also currently
slightly faster on ARM, although in single-key benchmarks I suspect
that advantage could be eliminated with more optimisation, based on
the x86-64 numbers.

Overall, Poly1305 over [UV]MAC was a clearer choice than ChaCha vs Salsa.

ChaCha20 is very simple and even a completely naïve implementation
will be secure. Poly1305 is somewhat more complex to implement but
again lends itself to secure implementations. Several high-quality,
optimised, public domains implementations are available of each.

I have implemented this draft in NSS and OpenSSL. No heroic
optimisation was done, but I used implementations by Andrew Moon, Ted
Krovetz, djb and Peter Schwabe.

The following numbers are encryption rates for a 1K block size with
with AES-128-GCM or ChaCha20+Poly1305. The AES-128-GCM implementation
is OpenSSL 1.0.1e compiled with gcc 4.6.3 and -O3, unless other
compiler flags are noted.

On an [email-masked] with Hyperthreading and Turboboost disabled:

AES-128-GCM, AES-NI disabled: 131 MB/s
AES-128-GCM, AES-NI enabled: 311 MB/s
AES-128-GCM, AES-NI enabled & -march=native: 308 MB/s
ChaCha20+Poly1305: 420 MB/s
ChaCha20+Poly1305, -march=native: 560 MB/s

On a Galaxy Nexus (ARM [email-masked]), gcc 4.7:

AES-128-GCM: 27 MB/s
ChaCha20+Poly1305: 78 MB/s

Note that I'm being rather unfair to ChaCha20 here: I'm comparing
128-bit AES against a 256-bit ChaCha20.

Intel suggests[5] that an E5-2690 (Sandy Bridge) should be able to do
AES-128-GCM in ~2.55 cycles/byte, giving speeds of ~1.1GB/s. Possibly
I've messed something up with OpenSSL, or the implementation in
OpenSSL 1.0.1e is underperforming, but I'm reporting what I see.

Of course, in general, one is not going to beat dedicated hardware in
software. When both parties to a TLS connection have AES-GCM hardware
implementations then AES-GCM is likely to be the most performant
option.

Cheers

AGL

[1] http://cr.yp.to/chacha/chacha-20080128.pdf
[2] http://eprint.iacr.org/2007/472.pdf, section 3.5.
[3] http://www.ietf.org/mail-archive/web/cfrg/current/msg03491.html
[4] http://www.ietf.org/mail-archive/web/tls/current/msg09712.html
[5] http://2013.diac.cr.yp.to/slides/gueron.pdf, page 17.

---

From: Yoav Nir <[email-masked]>
Date: Tue, 10 Sep 2013 16:07:53 +0000

> OpenSSL 1.0.1e is underperforming, but I'm reporting what I see.

I'm seeing 500 MB/s for AES-GCM on an Intel [email-masked], which is an older Westmere with a somewhat slower clock speed and OpenSSL 1.0.1-something. If I had to guess, you're using the MMX version of the ghash/gmult functions rather than the PCLMULQDQ version. 

Regardless, we need an alternative to AES. RC4 is out because of security, and 3DES is around a tenth the speed. Going back to 3DES means your hardware is not strong enough to handle your current load. ChaCha+poly1305 seems to be a good fallback, so I support the publication.

Yoav

---

From: Adam Langley <[email-masked]>
Date: Tue, 10 Sep 2013 18:08:25 -0400

> OpenSSL 1.0.1e is underperforming, but I'm reporting what I see.

I found what I had messed up in OpenSSL: AES-NI was in use, but only
block-by-block, not pipelined.

The AES-128-GCM speed on the E5-2690 with AES-NI enabled should be 868 MB/s.

Cheers

AGL

---

From: Dr Stephen Henson <[email-masked]>
Date: Wed, 11 Sep 2013 13:30:33 +0100

> TLS: https://datatracker.ietf.org/doc/draft-agl-tls-chacha20poly1305/

Which versions of TLS is this aimed at, TLS 1.2 (and later) only or earlier
versions too?

Would it make sense to include some DHE ciphersuites as well as the ECDH ones
for implementations which (for whatever reason) do not support or disable ECDH?

Steve.
-- 
Dr Stephen N. Henson.
Core developer of the   OpenSSL project: http://www.openssl.org/
Freelance consultant see: http://www.drh-consultancy.co.uk/
Email: [email-masked], PGP key: via homepage.

---

From: Ben Laurie <[email-masked]>
Date: Wed, 11 Sep 2013 13:47:41 +0100

> Which versions of TLS is this aimed at, TLS 1.2 (and later) only or earlier

Good point, should be explicit about that - we're aiming at all versions.

> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Adam Langley <[email-masked]>
Date: Wed, 11 Sep 2013 10:08:28 -0400

> Which versions of TLS is this aimed at, TLS 1.2 (and later) only or earlier

Since it's defined as an AEAD, technically it's only compatible with
TLS 1.2 - same as AES-GCM.

However, the reality, at least for browsers, is that we cannot depend
on TLS's version negotiation because of bugs in servers. Therefore, in
practice, I'm planning on making some or all AES-GCM and
Chacha20-Poly1305 ciphersuites work for all versions. For SSLv3,
ECDHE/ECDSA variants will implicitly indicate support for
P-{256,384,521} and uncompressed points since SSLv3 cannot carry the
EC extensions needed to indicate that.

I don't know whether, in standards land, that will be explicit.

> for implementations which (for whatever reason) do not support or disable ECDH?

I would like to support only ECDHE-ECDSA at this point but RSA has
significant inertia because of the CA system. On reflection, it does
seem reasonable that some implementations might not want the weight of
an ECC implementation given that they have to have
multiplicative-modexp for RSA anyway. So I've spun version -01 with
with a DHE_RSA ciphersuite too.

Cheers

AGL

---

From: Yoav Nir <[email-masked]>
Date: Wed, 11 Sep 2013 15:26:21 +0000

> with a DHE_RSA ciphersuite too.

Considering the performance difference, I though ECDHE-RSA would be in order. We have to have the RSA because that's what we have in the certificates, but might as well not add the extra work that is DHE. That's the reason why Google servers prefer ECDHE-RSA ciphersuites, no?

Yoav

---

From: Adam Langley <[email-masked]>
Date: Wed, 11 Sep 2013 11:28:49 -0400

> Considering the performance difference, I though ECDHE-RSA would be in order. We have to have the RSA because that's what we have in the certificates, but might as well not add the extra work that…

An ECDHE-RSA variant was included in -00 for this reason. Although I'd
*like* to only deal with ECDHE-ECDSA, we're not there yet for the
reasons that you identify.

Cheers

AGL

---

From: Dr Stephen Henson <[email-masked]>
Date: Thu, 12 Sep 2013 16:51:14 +0100

> with a DHE_RSA ciphersuite too.

Thanks. Some organisations are also ultra cautious about possible ECC patent
issues and wont use it at all.

Steve.

---

From: [email-masked] (Martin Rex)
Date: Tue, 17 Sep 2013 19:00:28 +0200 (CEST)

> EC extensions needed to indicate that.

Only those incarnations of SSLv3 that are "TLS extensions intolerant"
can not carry TLS extensions.  For all other implementations of SSLv3
(i.e. those based on the ssl302 draft that became rfc6101), support
for TLS extensions is no different from what it is in TLSv1.0 onward.

-Martin