Subject: [TLS] Salsa20 and Poly1305 in TLS

From: Adam Langley <[email-masked]>
Date: Mon, 29 Jul 2013 15:09:27 -0400

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 [email-masked] 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

---

From: Nico Williams <[email-masked]>
Date: Mon, 29 Jul 2013 14:39:51 -0500

+1.

While we're at it, what about curve25519 for DH?

Let's make sure this time not to leave out any combination using DH
(anon and not).

Nico
--

---

From: Rene Struik <[email-masked]>
Date: Mon, 29 Jul 2013 17:06:14 -0400

Hi Adam:

Let us add (re)tweetability to the requirements for algorithm design! 
While we are at it, let us impose this to all RFCs, technical papers, 
source code, poetry, text books, and our daily news as well.  Well, with 
the latter we are already nearly there...

Darn, now I may have surpassed the tweet limit myself!

Rene

==

Additionally, Poly1305 can be written in a tweet(*), while UMAC is
dramatically more complex.

On 7/29/2013 3:09 PM, Adam Langley wrote:
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Nick Mathewson <[email-masked]>
Date: Mon, 29 Jul 2013 20:40:37 -0400

> AES-CBC to be mortally wounded, even if we have to continue supporting

Hi!  Nick Mathewson (Tor guy) here.

We at Tor also support adding Salsa20 as a TLS ciphersuite, for about
the same reasons as Adam.  (We won't be able to start using it much
till browsers start using it, of course, since it's not in our
interest to be among the first adopters of any externally detectable
TLS feature.)

I also personally concur with Adam's arguments in favor of Poly1305,
but UMAC wouldn't be a disaster.

best wishes,
-- 
Nick Mathewson

---

From: Ted Krovetz <[email-masked]>
Date: Mon, 29 Jul 2013 17:03:44 -1000

> nonce generated directly by Salsa20/12, not via AES.)

The key agility in a simple poly hash is certainly much better than that of UMAC, and I agree that UMAC is not appropriate for some usage scenarios. I don't know enough about TLS usage, however, to comment on whether UMAC is a bad choice.

A couple of alternatives that may be worth considering...

--

In an attempt to simplify from UMAC, I developed VMAC as an alternative that uses considerably less internal key and is significantly faster on 64-bit architectures. Even from L3 cache it is probably 2-3 times faster than Poly1305.

http://fastcrypto.org/vmac/
http://krovetz.net/csus/papers/vhash-revise.pdf
http://krovetz.net/csus/papers/vmac.pdf

--

I'd also suggest using Bernstein's Chacha instead of Bernstein's Salsa. It has the same core as Salsa, but Bernstein cleaned up the rough edges of its prolog and epilog, making it smaller, faster and nicer to program. Chacha is basically a better Salsa.

http://cr.yp.to/chacha.html

-Ted

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 30 Jul 2013 11:00:12 +0200

> draft-josefsson-salsa20-tls-02, which is scheduled for discussion.
[...]
> nonce generated directly by Salsa20/12, not via AES.)

Thanks. The choice between UMAC and Poly1305 is indeed an open issue right now.

> memory in just 329ns with that in L1. That's typically the headline

That is, however, an important advantage in dedicated peer-to-peer
connections (e.g., VPN), which is how I test the current ciphersuites.

btw. was Poly1305 used with salsa20/12 in this comparison or AES? If
it is salsa20, I believe that the numbers would be quite different for
UMAC if used with salsa20 as well.

In any case, whether AES is used on the MAC (UMAC or Poly1305) or the
cipher of the ciphersuite is also an issue to be addressed. The only
issue for using the cipher instead of AES, is the fact that there are
no test vectors (in an RFC or any other document), and both of these
variants were defined using AES so by combining the MAC with another
cipher TLS will be quite unique. Nevertheless that idea of combining
them with the actual cipher in use is quite nice and has advantages in
a number of systems.

> security properties. (See [2] for a good overview.)

Complexity is indeed an issue, but tweetocity doesn't seem to be a
clear advantage :)

> Thus Poly1305 is looking much more attractive to us.

While I like UMAC, but I also see the advantages of Poly1305. In any
case, I think it would be a good idea to add them to the list (or even
replace umac if there are no clear advantages) if that draft proceeds.

regards,
Nikos

---

From: Ben Laurie <[email-masked]>
Date: Tue, 30 Jul 2013 10:40:27 +0100

Also, defining ciphersuites for SSL 3, TLS 1.0/1.1 would be good, so we can
use them despite downgrade attacks.

---

From: Adam Langley <[email-masked]>
Date: Tue, 30 Jul 2013 10:45:05 -0400

> http://krovetz.net/csus/papers/vmac.pdf

I agree that VMAC has considerably less memory footprint, around 168
bytes in total, and is faster. I will try to repeat the above
benchmarks for VMAC this week. (And, hopefully, run some tests on
ARM.)

> http://cr.yp.to/chacha.html

I do like ChaCha more than Salsa. However, in this case we don't have
the theoretical foundations of polynomial authenticators to stand on.
Salsa is what gets reviewed, ChaCha has had relatively little
attention. The improvement from Salsa to ChaCha doesn't seem to be
large enough to justify switching.

Having said that, I'm fine with either.

Cheers

AGL

---

From: Adam Langley <[email-masked]>
Date: Tue, 30 Jul 2013 10:52:46 -0400

> UMAC if used with salsa20 as well.

I measured UMAC with AES as you had previously indicated that was what
you were aiming at. (I measured Poly1305's raw speed as the difference
is small.)

If UMAC were measured without the AES operation then I think ~20ns
could be removed, although I'm using tables from bench.cr.yp.to due to
time.

> Complexity is indeed an issue, but tweetocity doesn't seem to be a

The simplicity is of some value, although I'll admit that the tweet
left some things under specified :)

Cheers

AGL

---

From: Geoffrey Keating <[email-masked]>
Date: 30 Jul 2013 11:26:16 -0700

> use them despite downgrade attacks.

Surely if you discover that the remote end appears to support only SSL
3 but yet somehow supports Salsa, you should stop trying to
communicate because you're under a downgrade attack?

---

From: Adam Langley <[email-masked]>
Date: Tue, 30 Jul 2013 18:08:57 -0400

> communicate because you're under a downgrade attack?

Unfortunately there exist middleboxes that prevent > SSLv3 from being
used, but which don't interfere with the encrypted traffic itself.
Breaking these is costly, and fundamentally ineffective because the
users will switch to a client that `works'. Ideally we would be able
to support secure connections in the broadest range of situations.

Cheers

AGL