[TLS] ChaCha20 + Poly1305 in TLS

Adam Langley <agl@google.com> Tue, 10 September 2013 15:23 UTC

Return-Path: <agl@google.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1500021F99DE for <tls@ietfa.amsl.com>; Tue, 10 Sep 2013 08:23:16 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.771
X-Spam-Level:
X-Spam-Status: No, score=-0.771 tagged_above=-999 required=5 tests=[AWL=-1.207, BAYES_40=-0.185, FM_FORGED_GMAIL=0.622, NO_RELAYS=-0.001]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id e9Sph7W2bGQn for <tls@ietfa.amsl.com>; Tue, 10 Sep 2013 08:23:15 -0700 (PDT)
Received: from mail-ie0-x235.google.com (mail-ie0-x235.google.com [IPv6:2607:f8b0:4001:c03::235]) by ietfa.amsl.com (Postfix) with ESMTP id 3883311E81B6 for <tls@ietf.org>; Tue, 10 Sep 2013 08:22:59 -0700 (PDT)
Received: by mail-ie0-f181.google.com with SMTP id y16so10532423ieg.26 for <tls@ietf.org>; Tue, 10 Sep 2013 08:22:58 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:from:date:message-id:subject:to:content-type :content-transfer-encoding; bh=gbJ1jkclRYxuUPI73n7pYu1KCydsHHHAVq+L8FSUUX0=; b=TW6n0dtARX9DODRZq9Jo3MPQ/r33ctt04wFH8sZtH7IA8ft31bflm1y2X+MoCicvH0 vBs/rj9pDQuox3RmsPznnDga5LcttiMav/pt85+WT0gWkmoZY/kqAJMxuq9w8nvsFYq2 EJHfwAqvGMViolMr2CPFovZJ/nF/ANWdHAg4Qu7I3s3n3w2ExJ1yrnSVMNeMPQLcws5F PpPBE8iqcK4SH6HH7L44EraR80Ue8wbnyXYvXSGs4vhy7SPcbHOclSYNeH/3fFUhChgg 9ksTIPpYGSr1WOoZTECkprmSYMpjuDiAf8SwmGq5vCaUxHUuvnADzUWRV7pWbs7/G0b+ trIQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:from:date:message-id:subject:to :content-type:content-transfer-encoding; bh=gbJ1jkclRYxuUPI73n7pYu1KCydsHHHAVq+L8FSUUX0=; b=AgigY8inHj3hNakQNrcW81Y0V9vZ2TfYrxliBNZEYGnsL0qYX/9A4AfmCle5BucfUb k19onF0utwsvVN8tYO4FOqXv5bEmnP+1M/n0TbXnZRTaAXDf/CwHwEZvv+7pP8q6IW+V 0vTcDgflCJg7tIduuRkUaAZN0ROwGao7USVma8e0u62almAmITLgjiN2UHSrOn6xEesn wUEiCpXD2CfdMk97LS/OhxTZFoKiBWYq3JbyZ2jZWwaOkehlcDsLonfbRruJjoVjEU24 Oz6sfkKTTDdJsfruyKuUtLdz6vVS/SwWQg99F3htKOWmfL9FcgIjGW//K8J1rQaNyE7F XpYg==
X-Gm-Message-State: ALoCoQlXb+DXCYFKzl4l38yC356vWigeS54qycZLvT8ZUo8iDIZVA/r+X69o46I+7Jmcztj1JxR9+Rzuy4ZyKpsp3dxpoSZ8+g3PQGUa9+6celOqUKUmKaSfFvTlB0Dv5iC5wBaPHB1ilrHEbU7SFHjCFMDf+8p0jn31cVYZ9kcx+zPteLCUwgST8hYooqJXf1HTykBQRPX7
X-Received: by 10.43.126.68 with SMTP id gv4mr16884icc.48.1378826578763; Tue, 10 Sep 2013 08:22:58 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.64.245.228 with HTTP; Tue, 10 Sep 2013 08:22:38 -0700 (PDT)
From: Adam Langley <agl@google.com>
Date: Tue, 10 Sep 2013 11:22:38 -0400
Message-ID: <CAL9PXLyLre-fySOY2H4oLAwSxiBmG+mnrJe9YiD9+OHmPVG-oA@mail.gmail.com>
To: "tls@ietf.org" <tls@ietf.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: [TLS] ChaCha20 + Poly1305 in TLS
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 10 Sep 2013 15:23:16 -0000

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 E5-2690@2.90GHz 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 Cortex-A9@1.2GHz), 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.