[TLS] Salsa20 and Poly1305 in TLS

Adam Langley <agl@google.com> Mon, 29 July 2013 19:09 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 3850E21F9D3A for <tls@ietfa.amsl.com>; Mon, 29 Jul 2013 12:09:49 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.978
X-Spam-Level:
X-Spam-Status: No, score=-1.978 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, 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 A0bmQKBcaOEe for <tls@ietfa.amsl.com>; Mon, 29 Jul 2013 12:09:48 -0700 (PDT)
Received: from mail-oa0-x231.google.com (mail-oa0-x231.google.com [IPv6:2607:f8b0:4003:c02::231]) by ietfa.amsl.com (Postfix) with ESMTP id CA62121F9A15 for <tls@ietf.org>; Mon, 29 Jul 2013 12:09:47 -0700 (PDT)
Received: by mail-oa0-f49.google.com with SMTP id n16so2510817oag.22 for <tls@ietf.org>; Mon, 29 Jul 2013 12:09:47 -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; bh=NjVL16gnYnxRjpl9r4RJPsRs3lVaN3L7a1ad7DfoTIA=; b=LmXI9b29GDB01cxNWPf/brIMJ9uJ07SB452+RVMrp0/vCNbiiaqpnwBNRJGldBWibX LpYMbVHoqA0cKqXYrb3z4srcpRXvfpdbdE6YlwZHUNP/5ga7ciO2Qzehz2Fai0QrL76k eX7Oala3OSmKBNZgi5Kqc+ecPMPJjiv3jcSEz7TOVdXiPF7iWq4R1O+g771G9aim/FoY f3wQ43fvuDSzzoeqh6lpfeSO0cts+ApeRatJ5Dw/Nv6Ljf19Hu6GuiTTSDXtbav4GwEy 3AUG2WuoCsj+FX2hDZ4GX+eRM3AIVDFgbWFSmK11814Ux9abQ6URWt86foBwKwRiy4P9 G0yw==
X-Google-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 :x-gm-message-state; bh=NjVL16gnYnxRjpl9r4RJPsRs3lVaN3L7a1ad7DfoTIA=; b=FmgqY6zGoXT3ztVpZRXVyZ9RpjTttlh8e8LjgELatSbNubQ3tEJ397OSeBvxAJ8qLO 5YHUqR8q+F3gVqMnQbEdVyXnxpoztQxxjLLBqrg8IwyOQCF2S40u4SIeNofB/4LByeF0 RB5GSIzrMwGoEBvisa56ZSpq50XqJnhgtsN9Ql0vhiHpnu2q8TJG8Bt5PxAo4Qx6E4Ql QuoaQpWXNmJ0gRoVyYCKmcz+XJ1H+lj5uOlhbyIrNF24PrDqmfq5Tpiy4QmaUr2rTX37 2JnWj1+SN//lEo898OCWpGfBo0AzeXmMrjyptnH1U2A+ksdEMQLU+lwXZQ5rH89nXzQ6 hzeg==
X-Received: by 10.182.81.41 with SMTP id w9mr16886748obx.18.1375124987195; Mon, 29 Jul 2013 12:09:47 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.182.111.66 with HTTP; Mon, 29 Jul 2013 12:09:27 -0700 (PDT)
From: Adam Langley <agl@google.com>
Date: Mon, 29 Jul 2013 15:09:27 -0400
Message-ID: <CAL9PXLySuS1gn8YisobYrbEnNpxJuYPbKB0qtkCOMnb+m90Jjg@mail.gmail.com>
To: "tls@ietf.org" <tls@ietf.org>
Content-Type: text/plain; charset=UTF-8
X-Gm-Message-State: ALoCoQmhgELriMnHxnTdxY7F2POsvHMxrCOvNQYaVB7mFJn9Q70rwnPlM8SAbqCS94BAkReH0dksZw1XAvng/Fx/z3NcmUstYJq5sD2WNDRe7ALx+Rsv8e90BmZnIcyLRHK5Il5zlSk+pgn88q5mjZv+eYHfPoWWCf49s3JDrEGeAsO+D0kCRn7zP8qFv9P7qnt58f4yfdRc
Subject: [TLS] Salsa20 and 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: Mon, 29 Jul 2013 19:09:49 -0000

I cannot make it to Berlin I'm afraid (or, indeed, any meetings until
at least IETF 91) so I'm writing my thoughts on
draft-josefsson-salsa20-tls-02, which is scheduled for discussion.

We (Google) support the addition of Salsa20 as a cipher in TLS. Having
a secure cipher which is fast and constant time on all platforms is
important. It's also good to have an alternative to AES in the wings
should that be needed in the future. At the moment I consider RC4 and
AES-CBC to be mortally wounded, even if we have to continue supporting
them for many years yet.

Salsa20/12 is something that we are currently working on supporting.

However, I believe that Poly1305 is superior to UMAC and we're looking
at Salsa20/12+Poly1305, not UMAC. (Note: that's Poly1305 with the
nonce generated directly by Salsa20/12, not via AES.)

(For the following, I used UMAC in nettle 2.7 and Andrew M's
implementation of Poly1305[1], both on a E5-2690@2.90GHz with
Hyperthreading and Turboboost disabled.)

UMAC96 (with AES for the nonce generation) takes 9146.1ns to
authenticate 1K of data, HMAC-SHA1(1K) takes 3667ns and Poly1305 takes
561.4ns.

However, that's not the whole story for UMAC because it can use 1.5KB
of memory for precomputation, after which it can authenticate 1KB of
memory in just 329ns with that in L1. That's typically the headline
speed that's advertised.

However, I consider cache pressure to be a way of cheating on
benchmarks :) Benchmarks don't show cache pressure until the algorithm
itself spills the L1 cache but, in a real system, cache costs.

With the precomputed data only in L3 cache (tested by cycling through
10,000 contexts), UMAC takes 922.16ns to authenticate 1KB.

So UMAC may give a small benefit to cases with few, busy connections,
but it's a loss in the case where there are many connections (a
server), or a few connections, intermittently used (i.e. a web
browser).

Additionally, Poly1305 can be written in a tweet(*), while UMAC is
dramatically more complex. Since they are both Wegman-Carter style
hashes I believe that they both have, fundamentally, well understood
security properties. (See [2] for a good overview.)

Thus Poly1305 is looking much more attractive to us.


(* Here's an attempt in 159 chars: "Take msg in 16 byte chunks. Append
1 to each msg chunk&0-pad to 17 bytes. Interpt little-endian. Calc
polynom in key[:16] mod 2^130-5. Add key[:16]. Mod 2^128.")

[1] https://github.com/floodyberry/poly1305-donna
[2] http://eprint.iacr.org/2013/144.pdf


Cheers

AGL