Subject: Re: [TLS] Salsa20 and Poly1305 in TLS

From: Adam Langley <[email-masked]>
Date: Tue, 6 Aug 2013 11:25:12 -0400

On Tue, Jul 30, 2013 at 10:45 AM, Adam Langley <[email-masked]> wrote:
> I will try to repeat the above benchmarks for VMAC this week. (And, hopefully, run some tests on ARM.)

Recap, to authenticate 1K of data:

UMAC96 (with AES for nonce generation, since Nikos suggested that was
the intended design previously): 9146ns
HMAC-SHA1: 3667ns
Poly1305: 561ns

On the same machine ([email-masked] with Hyperthreading and
Turboboost disabled), with VMAC code from fastcrypto.org:

VMAC (128-bit, with AES calls removed in order to better compare to
Poly1305): 270ns with 248 bytes of memory

On a Cortex-A8 (specifically a Galaxy Nexus) using Linaro GCC 4.7:

VMAC (128-bit, with AES calls removed): 13203ns with 248 bytes of memory
Poly1305 (code from SUPERCOP):  3567ns

For VMAC I used ARM optimised code provided by Ted Krovetz.

Other, random measurements:

VMAC (128-bit, AES for nonces, Intel): 368ns with 424 bytes of memory
and 1308ns one-time key schedule.
VMAC (64-bit, no AES, Intel): 138ns, 360 bytes of memory.
VMAC (64-bit, AES, Intel): 229ns, 360 bytes of memory.
VMAC (128-bit, AES, ARM): 14322ns, 424 bytes of memory

For the ARM measurements I was careful to do them with the screen on
and unlocked. Android reduces the clock speed when the phone is
`asleep'.

When measuring VMAC "with AES", I used "rijndael-alg-fst.c", not OpenSSL.

When removing AES from VMAC I just removed all AES calls and AES
related elements of the context structure. That's not intended to be a
real design, but a reasonable simulation for the purposes of timing.

Poly1305 is very fast on ARM, but VMAC is twice as fast on servers at
the cost of a bit of memory.

I think I'm still leaning towards Poly1305, but I could be persuaded
by VMAC, it's very impressive.

Cheers

AGL

---

From: Adam Langley <[email-masked]>
Date: Tue, 6 Aug 2013 12:38:18 -0400

On Tue, Aug 6, 2013 at 12:20 PM, Ted Krovetz <[email-masked]> wrote:
> I'm a bozo. When I gave you the VMAC code using ARM intrinsics I should have explicitly reminded you to enable NEON when compiling:
>
>   gcc -mcpu=cortex-a8 -mfpu=neon -mfloat-abi=hard
>
> On a modern ARM, you should always use these settings so that your compiler uses the NEON unit when possible.

Thank you! I used -O3, but I don't develop on ARM very often.

Please ignore previous measurements for VMAC on ARM.

VMAC (ARM, 128-bit, with AES calls removed): 5015.1ns with 248 bytes of memory
Poly1305 (ARM, with same flags): 3457ns

I don't believe that either can be said to be better than the other
now, which makes the call harder if anything :)

Cheers

AGL

---

From: Ben Laurie <[email-masked]>
Date: Tue, 6 Aug 2013 22:54:52 +0100

[+ekasper]

Emilia was getting some interesting results doing this kind of stuff many
times in parallel...

On 6 August 2013 17:38, Adam Langley <[email-masked]> wrote:

> > I'm a bozo. When I gave you the VMAC code using ARM intrinsics I should
> have explicitly reminded you to enable NEON when compiling:
> >
> > On a modern ARM, you should always use these settings so that your
> compiler uses the NEON unit when possible.
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Adam Langley <[email-masked]>
Date: Tue, 6 Aug 2013 18:01:00 -0400

> Emilia was getting some interesting results doing this kind of stuff many

The Poly1305 code is doing multiple terms of the polynomial concurrent
with SSE2 and NEON. I'm assuming that VMAC is doing the same.

That does bode well for the AVX2/AVX-512 future, but those chips are
widely distributed yet.

Cheers

AGL

---

From: Ted Krovetz <[email-masked]>
Date: Tue, 6 Aug 2013 09:20:32 -0700

Adam,

Thanks a lot for taking the time to do these tests.

-Ted

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 12 Aug 2013 00:18:49 +0200

Ted Krovetz <[email-masked]> writes:

> 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

Right, there is a bunch of stream ciphers that have nicer properties
than Salsa20, but Salsa20 was chosen conservatively from the set of
modern stream cipher.  Do you think the benefits of Chacha motivate
ignoring the time that went into reviewing Salsa20?  I'm assuming
Salsa20 has received more review than Chacha, but I cannot quantify it.

I would have prefered a stream cipher with builtin authentication, so we
wouldn't have to debate the choice of MAC.  Alas, I'm not aware of any
with good performance that has gone through significant review.

/Simon

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Sun, 11 Aug 2013 19:40:19 -0400

Considering the similarity between Salsa and Chacha design & construction (and the amount of analysis that went into it), IMHO Chacha advantages justify its use over Salsa.

Thanks!
--
Regards,
Uri Blumenthal                            Voice: (781) 981-1638
Cyber Systems and Technology   Fax:   (781) 981-0186
MIT Lincoln Laboratory                Cell:  (339) 223-5363
244 Wood Street                        Email: <[email-masked]>
Lexington, MA  02420-9185       

Web:  http://www.ll.mit.edu/CST/

MIT LL Root CA: 

 <https://www.ll.mit.edu/labcertificateauthority.html>

DSN:   478-5980 ask Lincoln ext.1638

----- Original Message -----
From: Simon Josefsson [mailto:[email-masked]]
Sent: Sunday, August 11, 2013 06:18 PM
To: Ted Krovetz <[email-masked]>
Cc: [email-masked] <[email-masked]>
Subject: Re: [TLS] Salsa20 and Poly1305 in TLS

/Simon

---

From: Ted Krovetz <[email-masked]>
Date: Sun, 11 Aug 2013 18:06:16 -0700

> Do you think the benefits of Chacha motivate
> ignoring the time that went into reviewing Salsa20?

The nice thing about Chacha is that most of the Salsa analysis applies. The only differences between the two algorithms is (1) the ordering of the initial and final 16 word state, and (2) two rotation distances. I believe that Dan Bernstein has said that he believes (1) has no security consequences and that (2) improves security.

If I were choosing between the two, yes, I'd be willing to transfer my confidence from Salsa to Chacha and  use that.

-Ted