Subject: [TLS] chacha to replace RC4 (was: Salsa vs. ChaCha)

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 06 Dec 2013 13:19:48 +0100

On Thu, 2013-11-28 at 04:30 +0000, Samuel Neves wrote:
>  - Zooko has mentioned BLAKE and its success against cryptanalysis, but
> as noted this does not translate to a useful security reduction. It is
> worth pointing out, however, that cryptographers chose to base the core
> of their algorithm in the ChaCha quarter-round rather than the Salsa
> quarter-round. This suggests equal or more confidence in ChaCha (see
> also [4]).

To speed things up, we have submitted an alternative draft that replaces
RC4 with Chacha [0] instead of Salsa20. This draft is based on the 20
round variant of chacha.

We believe there are merits in selecting a winner of cryptographic
competition, but given your comments and that Chacha was the
recommendation of the CFRG there is no need to delay things if Chacha vs
Salsa20 is only issue to replace RC4.

[0]. http://www.ietf.org/id/draft-mavrogiannopoulos-chacha-tls-00.txt

regards,
Nikos

---

From: Robert Ransom <[email-masked]>
Date: Fri, 6 Dec 2013 04:54:05 -0800

> Salsa20 is only issue to replace RC4.

The other issue in replacing RC4 with Salsa20 or ChaCha is that the
currently available efficient implementations of Salsa20 and ChaCha
encrypt a whole message at once, rather than incrementally generating
a stream as with RC4.  (And modifying them to do the latter would add
considerable complexity -- if it must be done, I would generate 3 or 4
blocks of output at a time and have some other piece of code XOR the
keystream with the data.)

Salsa20 and ChaCha are meant to be used as in Adam Langley's draft,
not as replacements for RC4.

Robert Ransom

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 06 Dec 2013 14:14:57 +0100

> keystream with the data.)

Which ones are you referring to? I have been using salsa20 with a sane
API that allows encrypting message by message (see nettle's
implementation of salsa20).

> not as replacements for RC4.

Are you suggesting that neither is good for TLS? I disagree, as if you
see my IETF88 presentation slides, Salsa20 performs much better than RC4
_in TLS_, making it suitable for a replacement.

Adam's draft proposes a novel scheme. While that this is a good scheme,
it can only be used in TLS 1.2 or later, and there will be competing
AEAD schemes coming from the CAESAR competition. We need a replacement
for RC4 now, that can (ideally) be patched in old implementations as
well.

regards,
Nikos

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 06 Dec 2013 14:22:31 +0100

On Fri, 2013-12-06 at 04:54 -0800, Robert Ransom wrote:

> encrypt a whole message at once, rather than incrementally generating a
> stream as with RC4.  (And modifying them to do the latter would add
> Salsa20 and ChaCha are meant to be used as in Adam Langley's draft, not
> as replacements for RC4.

Reading that again, I believe that what you say above doesn't make
sense. Why Chacha suits better in Adam's draft, but doesn't as a 
replacement of RC4?

regards, 
Nikos

---

From: Nick Mathewson <[email-masked]>
Date: Fri, 6 Dec 2013 10:21:08 -0500

> sense. Why Chacha suits better in Adam's draft, but doesn't as a

He's saying that the existing chacha and salsa20 implementations are
designed so that, instead of generating an arbitrary-length stream
incrementally, they generate the start of the stream each time you
invoke them with a key,nonce pair, and you are supposed to choose a
new nonce each time.

As you probably know, these stream ciphers are implemented in terms of
a block function that takes as input a 256-bit key, a 64-bit nonce,
and a 64-bit counter, and produces 512 bits of output.  To generate a
stream longer than 512 bits, you hold the key and nonce fixed and let
the counter run from 0 to N until you have generated as many 512-bit
blocks as you need.

The issue is that most implementations (all the ones I've seen,
actually, and Robert has probably looked at more than I have) have an
interface where you specify the number of bytes of output up front,
and generate.  They do not have an incremental "generate the next N
bytes of the stream" function.

That said, it's pretty trivial to adopt _any_ of the implementations
I've seen so that they would run incrementally; it's not a difficult
programming problem.  You'd need to add 512 bits of memory overhead
for each chacha instance, and you'd take a little performance overhead
from the bookkeeping, but that's not a huge deal.

And *that* said, it's also trivial to avoid the need to make any such
change, by taking the strategy Adam's draft does, and using a
different nonce for each record.

hth,
-- 
Nick Mathewson

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 06 Dec 2013 16:57:20 +0100

> from the bookkeeping, but that's not a huge deal.

I also think so.

> different nonce for each record.

A different nonce for each record is mandatory if chacha or salsa20 are
to be used with DTLS. This has been the case from the first draft we had
in salsa20. So I think the previous comment is not applicable to the
draft I posted.

regards,
Nikos

---

From: Robert Ransom <[email-masked]>
Date: Fri, 6 Dec 2013 08:42:23 -0800

> bytes of the stream" function.

Some of Dr. Bernstein's implementations in SUPERCOP do have an
incremental interface (specified by eSTREAM).  The main difficulty
with those implementations is that the interface requires callers to
encrypt an integral number of blocks with each call except the last.

Since Salsa20 and ChaCha are well known to encrypt merely by XORing
keystream into data, this could be worked around using an external
buffer, but that's an ugly piece of extra work.

> from the bookkeeping, but that's not a huge deal.

To get the performance that people expect from these stream ciphers,
one would need to buffer (at least) three or four blocks, since the
fastest implementations (Ted Krovetz's) generate three or more blocks
in parallel.

Robert Ransom

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Fri, 06 Dec 2013 17:43:57 +0100

> in salsa20. So I think the previous comment is not applicable to the
I agree, but perhaps the draft could state that more clearly.

RFC 5246 6.2.3.1 states that

    For stream ciphers that do not use a synchronization vector (such as
    RC4), the stream cipher state from the end of one record is simply
    used on the subsequent packet.

The draft may recall this to emphasize and constrast that Chacha does
use a "synchronisation vector" (the per-record nonce) so that the stream
cipher state from the end of one record is *not* used on the subsequent
packet.

Also, maybe it's just me, but maybe the draft should state explicitly
that the per-record nonce is not meant to be transmitted as part of the
GenericStreamCipher PDU, but computed as mentionned in section 2.1.

Manuel.

---

From: Samuel Neves <[email-masked]>
Date: Sat, 07 Dec 2013 02:27:45 +0000

> fastest implementations (Ted Krovetz's) generate three or more blocks

It's unclear to me what the objection here is precisely, if there is one
at all. RC4 also works by XORing keystream into data. It just so happens
to output 1 byte per call, instead of 64. I agree with Nick that
changing existing implementations to be incremental is simple, and some
good ones already exist [1].

Let's not forget that the internal state of RC4 is 258 *bytes*. Chacha
has an internal state of 48 bytes (32 + 8 + 8), which leaves plenty of
space for an additional buffer of 128 or 256 keystream bytes (2 or 4
output blocks) without going overboard compared to RC4.

Additionally, the best RC4 implementations on current x86 processors
don't seem to do better than 4 cycles per byte; even mediocre Chacha or
Salsa20 implementations are going to be a performance upgrade, and the
best-case scenario will approach 1 cycle per byte.

[1] https://github.com/floodyberry/chacha-opt

---

From: Brian Smith <[email-masked]>
Date: Fri, 6 Dec 2013 19:44:30 -0800

On Fri, Dec 6, 2013 at 5:14 AM, Nikos Mavrogiannopoulos <[email-masked]> wrote:
> AEAD schemes coming from the CAESAR competition. We need a
> replacement for RC4 now, that can (ideally) be patched in old
> implementations as well.

AFAICT, there's no technical reason to prohibit AEAD in TLS 1.0 or TLS 1.1.

Also, I don't think TLS 1.2 is that much code to add to a TLS 1.0 or
TLS 1.1 implementation, especially if you're not supporting any new
cipher suites except the new ChaCha20 ones, and if you're not trying
to support any functionality above what what TLS 1.0 and TLS 1.1
provide.

Consequently, I don't think we should consider the AEAD construction
to be too much of a burden for anybody to implement in order to
support new cipher suites.

Cheers,
Brian
-- 
Mozilla Networking/Crypto/Security (Necko/NSS/PSM)

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Sat, 07 Dec 2013 14:19:43 +0100

On Fri, 2013-12-06 at 19:44 -0800, Brian Smith wrote:

> cipher suites except the new ChaCha20 ones, and if you're not trying to
> support any functionality above what what TLS 1.0 and TLS 1.1 provide.
> Consequently, I don't think we should consider the AEAD construction to
> be too much of a burden for anybody to implement in order to support
> new cipher suites.

Hello,  
 I agree that there is no technical reason to prohibit AEAD in
TLS 1.x, x<2, but exactly for this prohibition, the old non-TLS 1.2
supporting implementations don't have support for AEAD. Their design is
often agile in the sense that a new cipher or MAC can be easily added,
but adding an AEAD cipher there is a non-trivial matter. If by AEAD you
mean Adam's draft, then there is also the question why replace
RC4-HMAC-SHA1 with AEAD-CHACHA-POLY1305 when you only need to fix RC4?
(and we have no reasons to believe that HMAC-SHA1 is broken).

If you suggestion is to make CHACHA-HMAC-SHA1 an AEAD design, I don't
think that this is needed. Unlike AEAD-CHACHA-POLY1305 which is
inherently an AEAD design, there is no advantage gained by making
CHACHA-HMAC-SHA1 an AEAD cipher - except for saying "cool it is AEAD",
and making it more difficult for old implementations to use it.

regards, 
Nikos