Subject: [TLS] Salsa vs. ChaCha

From: Zooko Wilcox-OHearn <[email-masked]>
Date: Mon, 18 Nov 2013 21:34:49 +0000

Folks:

draft-josefsson-salsa20-tls-03 makes it sound as though choosing
ChaCha over Salsa would be trading off security (at least as reflected
by Salsa being an eSTREAM finalist) for performance (at least in
hardware). I don't think this reflects typical beliefs about the
relative merits of these two ciphers.

Instead, I think ChaCha is generally considered to be slightly
stronger than Salsa, in addition to slightly faster (in both software
and hardware).

I hasten to add that in my opinion both Salsa20 and ChaCha20 are very
secure and very efficient and either one would be a fine choice.

However, the best known attacks on ChaCha ¹ are more effective against
Salsa than against ChaCha, breaking 8 rounds (out of 20) of Salsa and
7 rounds (out of 20) of ChaCha.

draft-josefsson-salsa20-tls-03 emphasizes that Salsa was a finalist in
an international competition, and I agree that this is a good point
and a point in Salsa's favor.

It is worth noting that ChaCha serves as the core of the BLAKE hash
function, which was a finalist in the SHA-3 competition. The final
report from NIST stated that BLAKE was studied even more thoroughly
during that competition than the ultimate winner, Keccak, was:

"Grøstl, Skein, and BLAKE have a large number of attack papers
reflecting considerable depth of analysis, and Keccak has somewhat
less, but still received considerable cryptanalytic attention." (see
section 4.2.1 of ²)

Here's a quick sketch of the relationship between BLAKE and ChaCha, to
show why the cryptanalytic attention lavished on BLAKE during the
SHA-3 competition should increase our confidence in the security of
the ChaCha stream cipher.

ChaCha (and Salsa) have at their core a fixed-input-length hash
function, called "G()". To use ChaCha (or Salsa) as a stream cipher,
you put in your secret key, a nonce, and a counter-value as the input
to G(), take the fixed-length (e.g. 64-byte) output from G() and use
that as a "keystream" by XOR'ing the next 64 bytes of your plaintext
with it to produce the next 64 bytes of your ciphertext.

BLAKE takes the G() function from ChaCha, lets the input to G() be the
"chaining value", and tweaks G by adding-in the words of the next
chunk of the message during the computation of G.

So, unfortunately there is no "provable security" reduction by which
we can show that *any* attack on BLAKE must necessarily lead to an
attack on ChaCha, or vice versa.

However, they are so closely related that in my opinion the copious
cryptanalysis of BLAKE during the SHA-3 contest would probably have
revealed weaknesses in ChaCha at the same time as it revealed any
weaknesses in BLAKE.

Disclosure: I was so impressed with BLAKE when I saw it in the SHA-3
contest, that I later collaborated in the definition of "BLAKE2", a
successor algorithm: https://blake2.net/

¹ http://eprint.iacr.org/2007/472

² http://nvlpubs.nist.gov/nistpubs/ir/2012/NIST.IR.7896.pdf

Regards,

Zooko Wilcox-O'Hearn

Founder, CEO, and Customer Support Rep
https://LeastAuthority.com
Freedom matters.

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 19 Nov 2013 09:36:05 +0100

> stronger than Salsa, in addition to slightly faster (in both software

Hello Zooko,
 This was not our intention (and if there is some text that needs to be
changed to prevent that, please let us know). Mainly what we want to say
there, is that we do not want to evaluate any new cipher (we are not
experts in cipher design). We select what is considered secure from the
existing cryptographic competitions in order to replace RC4. 

If we follow the path to chacha, which is not the outcome of a cipher
competition there can be arguments why not consider some other XXX
stream cipher as well which could be better than ChaCha in some aspect.
Such arguments would then be hard to confront.

> revealed weaknesses in ChaCha at the same time as it revealed any

You provide some good arguments in favor of chacha, although as you say
the results cannot be directly related to Chacha as a cipher. In any
case our decision for the cipher is not written in stone.

regards,
Nikos

---

From: Samuel Neves <[email-masked]>
Date: Thu, 28 Nov 2013 04:30:15 +0000

> existing cryptographic competitions in order to replace RC4.

Section 7 does seem to focus a lot on the performance aspect of ChaCha.
In reality, ChaCha was designed to improve diffusion, which would
hopefully translate to more security per round. The speed advantages
were (mostly) incidental.

> Such arguments would then be hard to confront.

I certainly understand the rationale of picking a co-winner (along with
Rabbit, HC-128, and SOSEMANUK) of a cryptographic competition. Nobody
ever got fired for that!

A few comments, though:

 - The most successful cryptanalysis performed on Salsa20 also analyzed
ChaCha [1, 2]. In each case, ChaCha withstood attacks with one fewer
round than its predecessor. ChaCha does seem to deliver on its goal of
more diffusion per round.

 - 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]).

 - There is a concurrent proposal to integrate Chacha20 + Poly1305 as a
TLS AEAD mode [3]. Implementors are unlikely to appreciate the
redundancy in having two separate, but very similar ciphers, in TLS (I
do realize that it makes just as much sense to ask Adam Langley to
change to Salsa20).

Ultimately, whatever variant ends up being chosen, I believe it's the
overwhelming consensus that it beats RC4.

[1] http://eprint.iacr.org/2007/472
[2] http://link.springer.com/chapter/10.1007%2F978-3-642-37682-5_24
[3] http://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04#page-14
[4] http://www.ietf.org/mail-archive/web/cfrg/current/msg03491.html

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Thu, 28 Nov 2013 17:08:20 +0100

> do realize that it makes just as much sense to ask Adam Langley to

I agree with your last point that the drafts should match to reduce the
number of algorithms needed in a TLS implementation. There is no point
to have both salsa20 and chacha.

To me it is pretty inexplicable why one would not want the winner of a
recent crypto competition in TLS but rather a modification of it (e.g.,
I haven't seen anyone arguing for another cipher in TLS when RIJNDAEL
was the winner of the NIST competition).

Nevertheless, if the TLS WG consensus is to use Chacha20/20 (or
Chacha20/12?) to replace RC4 instead of the estream's salsa20, it would
be very simple to draft a new text with it. What I didn't understand,
however, from the IETF88-TLS notes is whether it is planned to replace
RC4 at all (with a non-AEAD cipher that is).

regards,
Nikos