Subject: [TLS] comparison of draft-josefsson-salsa20-tls-02 and draft-agl-tls-chacha20poly1305-02

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Wed, 23 Oct 2013 11:33:34 +0200

Hello,
 We are about to update draft-josefsson-salsa20-tls-02 by replacing
UMAC-AES with POLY1305-AES, and given the opportunity we made a
comparison of the two drafts that add a new stream cipher to TLS. That
is draft-josefsson-salsa20-tls-02 and draft-agl-tls-chacha20poly1305-02.

* Salsa20 vs Chacha

draft-josefsson-salsa20-tls-02 uses Salsa20, a winner of an
international competion of stream ciphers (eStream), which is easily
implementable without leaking information through side-channels (i.e.
timing attacks).

draft-agl-tls-chacha20poly1305-02 selects Chacha instead, a derivative
of Salsa20 that has been shown to be 7% faster in hardware and occupy
10% less space [0]. However, it only combines that cipher with a MAC
that is of questionable efficiency in hardware (according to CFRG
synopsis). This results overall, in a combination that isn't really well
suited for hardware.

Nevertheless, even if draft-agl-tls-chacha20poly1305-02 could be made
efficient in hardware, in our opinion the performance benefits don't
justify switching from a winner of an international competition to
another algorithm (even if it is a derivative of it).

* Applicability to Datagram TLS

The draft-agl-tls-chacha20poly1305-02 is only applicable to TLS and not
DTLS. That is because its combination with poly1305-chacha results to an
RC4-like effect where rearranged or lost packets result in a
desynchronization of the peers. draft-josefsson-salsa20-tls-02 applies
to both TLS and DTLS (this results from the choice of having the block
cipher AES in UMAC-AES). Having a stream cipher in DTLS was a main
reason (for me at least) for draft-josefsson-salsa20-tls-02.

* Adding a new cipher in stream or AEAD mode?

The draft-josefsson-salsa20-tls-02 draft adds a new cipher to existing
implementations and can be combined with the existing MAC algorithms in
TLS (i.e., HMAC-SHA1). That is not the case in the
draft-agl-tls-chacha20poly1305-02 draft, where a single combination is
registered (of chacha with poly1305). Adding additional combinations in
the latter draft would require defining more AEAD modes, something that
could be a significant barrier that prevents its implementation (in
contrast with just replacing a cipher in the stream setting of TLS).

While I understand that there is quite some argumentation for using the
AEAD mode in TLS for every cipher/mac combination I don't find it
particularly convincing. In this specific case the AEAD mode adds 8
bytes of explicit nonce to the TLS record packet without providing any
clear advantages compared to the original stream cipher interface.

* An interesting observation on the usage of EtA in
draft-agl-tls-chacha20poly1305-02 vs AtE.

Both drafts introduce a universal hash based MAC. However, the
chacha-poly1305 draft uses the encrypt-then-authenticate (EtA)
construction while the salsa20 draft uses TLS' authenticate-then-encrypt
(AtE) construction. When combined with ideal ciphers and MAC algorithms
both modes can be equivalent. However, the AtE construction has the
advantage of not revealing the MAC nor the authenticated data to an
adversary. Interestingly enough the only known attacks on universal hash
based MACs require access to MAC and data [1]. That is, these attacks
(the key guessing and the divide and conquer) do not directly apply to
draft-josefsson-salsa20-tls-02.

Of course these attacks are of high complexity and impractical (unless
some other weakness in the TLS protocol, or the MAC algorithm is found),
but they nevertheless reinforce the view that the AtE construction has
advantages on non-ideal MAC algorithms.

best regards,
Nikos

[0]. Henzen, Luca, et al. "VLSI hardware evaluation of the stream
ciphers Salsa20 and ChaCha, and the compression function Rumba."
Signals, Circuits and Systems, 2008. SCS 2008. 2nd International
Conference on. IEEE, 2008.

[1]. Handschuh, Helena, and Bart Preneel. "Key-recovery attacks on
universal hash function based MAC algorithms." Advances in
Cryptology–CRYPTO 2008. Springer Berlin Heidelberg, 2008. 144-161.

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 23 Oct 2013 03:49:45 -0700

> clear advantages compared to the original stream cipher interface.

I don't believe that this is correct. That is how the GCM cipher suites
are constructed, but it isn't required by RFC 5246, which says:

   Each AEAD cipher suite MUST specify how the nonce supplied to the
   AEAD operation is constructed, and what is the length of the
   GenericAEADCipher.nonce_explicit part.  In many cases, it is
   appropriate to use the partially implicit nonce technique described
   in Section 3.2.1 of [AEAD]; with record_iv_length being the length of
   the explicit part.  In this case, the implicit part SHOULD be derived
   from key_block as client_write_iv and server_write_iv (as described
   in Section 6.3), and the explicit part is included in
   GenericAEAEDCipher.nonce_explicit.

With that said, the argument for having an explicit IV is as follows: it's
desirable to have a cryptographic AEAD primitive which doesn't
accidentally enable nonce reuse. In order to do this, you need to
internally generate the nonce, which means it must be explicit.
(For FIPS purposes, this means it must be generated inside the crypto
boundary). That's why the GCM algorithms were done this way.

You may or may not subscribe to this, but it's basically
an orthogonal question to the rest of these issues.

-Ekr

---

From: Adam Langley <[email-masked]>
Date: Wed, 23 Oct 2013 09:55:42 -0400

> another algorithm (even if it is a derivative of it).

I don't think that there's much between them, but have a slight
preference for ChaCha, which mirrors the CFRG: "The RG expressed a
preference for ChaCha." [1]

[1] http://www.ietf.org/mail-archive/web/tls/current/msg10221.html

> reason (for me at least) for draft-josefsson-salsa20-tls-02.

I don't believe that this is correct. There is no state carried
between encryptions of records. Given the sequence numbers of a set of
records, they can be processed in any order.

Although the ChaCha draft doesn't mention DTLS, I don't think there's
any fundamental difference here.

> clear advantages compared to the original stream cipher interface.

This is incorrect, there is no explicit nonce in the ChaCha AEAD construction.

Chrome is conducting experiments at the moment to test the
transparency of the general Internet to TLS 1.0 and 1.2, although it
will take a few months for the results. If TLS 1.2 turns out to be
non-viable then I agree that some changes will be needed somewhere,
but I'm still awaiting that data.

> advantages on non-ideal MAC algorithms.

On the other hand, EtA allows for faster forgery rejection which,
while not so useful for TLS, is useful for DTLS.

In any case, I don't believe that the security bounds laid out in the
original Poly1305 paper[2] have been altered and I believe those
bounds are sufficient for all users of (D)TLS.

[2] http://cr.yp.to/mac/poly1305-20050329.pdf

Cheers

AGL

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Wed, 23 Oct 2013 16:51:34 +0200

> any fundamental difference here.

As far as I understand you use chacha to generate the keystream for
poly1305. Thus you carry state between records (chacha is a stream
cipher). I don't know if I have missed anything there, but I don't see
resetting chacha with a new IV per MAC calculation.

> This is incorrect, there is no explicit nonce in the ChaCha AEAD construction.

I missed that. Indeed.

> while not so useful for TLS, is useful for DTLS.

Is that really an issue? If yes, then EtA isn't also invulnerable to a
DoS attack, it is a big more lightweight.

However, as a general comment I think DTLS' resilience on forged packets
isn't that good. It makes it a perfect target to lay an attack. I think
it would be much better to have a limit by default on the allowed
packets with wrong MAC.

> bounds are sufficient for all users of (D)TLS.

Of course, these attacks require another flaw or leak to be practical.
However, my point is, that even with that additional flaw or
information, they will still not be applicable in AtE mode.

regards,
Nikos

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Wed, 23 Oct 2013 16:58:35 +0200

> are constructed, but it isn't required by RFC 5246, which says:

Indeed, and it seems the chacha draft didn't use the explicit IV anyway,
so I wasn't correct here. So I only don't get what is the advantage of
that mode. The stream interface of TLS is easier to extend with new
cipher/mac combinations without having to define again or differently
the details of a new AEAD mode (TLS stream mode defines how
authenticated-encryption is performed anyway, and there are no known
issues with that).

Thus from an implementer point of view I find the usage of the stream
mode the natural thing to do, unless something very special needs to be
done, or the cipher/mac combination is so tightly combined like GCM that
warrants the usage of the AEAD interface.

regards,
Nikos

---

From: Adam Langley <[email-masked]>
Date: Wed, 23 Oct 2013 10:58:48 -0400

> resetting chacha with a new IV per MAC calculation.

There is no state carried between records: "ChaCha20 is run with the
given key and nonce and with the two counter words set to zero. The
first 32 bytes of the 64 byte output are saved to become the one-time
key for Poly1305." (The nonce is the sequence number of the record.)

(http://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-00#section-5)

Cheers

AGL

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 23 Oct 2013 08:42:30 -0700

On Wed, Oct 23, 2013 at 7:51 AM, Nikos Mavrogiannopoulos <[email-masked]>wrote:

> as a general comment I think DTLS' resilience on forged packets

S 4.2.7 provides some guidance in this area, but it's pretty vague:

   Note that Alert messages are not retransmitted at all, even when they
   occur in the context of a handshake.  However, a DTLS implementation
   which would ordinarily issue an alert SHOULD generate a new alert
   message if the offending record is received again (e.g., as a
   retransmitted handshake message).  Implementations SHOULD detect when
   a peer is persistently sending bad messages and terminate the local
   connection state after such misbehavior is detected.

It certainly seems like it would be a good thing to document some
better guidance about how many bad MACs you should tolerate.

Do you have any thoughts about what makes sense?

-Ekr

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Wed, 23 Oct 2013 18:34:47 +0200

> (http://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-00#section-5)

I had assumed that you used the Poly1305-AES construction but with
Chacha in place of AES. Clearly this isn't the case, and even the
attacks described may not apply to your construction. I have not seen
this construction before. It looks pretty elegant. Has it been used
somewhere else?

regards,
Nikos

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Wed, 23 Oct 2013 18:40:42 +0200

> Do you have any thoughts about what makes sense?

I was thinking of disabling wrong MAC tolerance completely if the
underlying layer has checksums. UDP for example has checksums and
packets that are altered due to transmission errors will be discarded
anyway. In lower protocols such as ethernet we also have checksums.

If someone needs to transmit in raw without any checksums, he could
exceptionally allow wrong MAC tolerance.

regards,
Nikos

---

From: Adam Langley <[email-masked]>
Date: Wed, 23 Oct 2013 12:46:03 -0400

> this construction before. It looks pretty elegant. Has it been used

I lifted it from NaCl, see section 9 of
http://cr.yp.to/highspeed/naclcrypto-20090310.pdf.

The difference is that the ChaCha AEAD doesn't use HChaCha, because
the extended nonce isn't useful, and it moves the authenticator from
the beginning to the end of the output because that fits more easily
into existing code bases.

Cheers

AGL

---

From: Robert Ransom <[email-masked]>
Date: Wed, 23 Oct 2013 09:47:58 -0700

> this construction before. It looks pretty elegant. Has it been used

It's used in the 'box' and 'secretbox' operations in NaCl.  See also
section 2.5 of <http://cr.yp.to/antiforgery/pema-20071022.pdf>.

Robert Ransom

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Wed, 23 Oct 2013 22:50:08 +0200

> exceptionally allow wrong MAC tolerance.

It seems I answered hastily. I think there is an issue with what I
proposed. I see 2 things that need to be ensured here.
1. The session must be resilient to accidental transmission errors.
2. The session must be resilient to termination by someone who hasn't
access on the communication line

Do I miss something else?

[I don't think there is point being resilient to someone with access to
the communication line, as he could always cause a DoS by simply
dropping all packets.]

My proposal above handles 1, but not 2. In the UDP case anybody can
forge a DTLS packet and send it on the server port claiming to be the
client (he doesn't need to know the client port, he just sends many
packets with all possible ports). DTLS will discard packets out of
epoch, or with old sequence numbers, but sequence numbers are easy to
guess in DTLS. They are sequential and start from 0. Thus one could
"easily" avoid the window check in DTLS and pass a packet with an
invalid MAC.

So if wrong MAC tolerance is removed in a future revision of DTLS, it
has to be combined with something that ensures (2). That could be random
sequence numbers (similar to TCP), or something else.

regards,
Nikos