[TLS] Salsa20 and Poly1305 in TLS

[Adam Langley <[e-mail]>]

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