[TLS] Salsa vs. ChaCha

Zooko Wilcox-OHearn <zooko@leastauthority.com> Mon, 18 November 2013 21:34 UTC

Return-Path: <zooko@leastauthority.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 2A27D1AE53F for <tls@ietfa.amsl.com>; Mon, 18 Nov 2013 13:34:58 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.079
X-Spam-Level:
X-Spam-Status: No, score=-0.079 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, FM_FORGED_GMAIL=0.622, RCVD_IN_DNSWL_LOW=-0.7] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id dFbNlZ7zgsRI for <tls@ietfa.amsl.com>; Mon, 18 Nov 2013 13:34:56 -0800 (PST)
Received: from mail-ee0-f41.google.com (mail-ee0-f41.google.com [74.125.83.41]) by ietfa.amsl.com (Postfix) with ESMTP id E59951AE539 for <tls@ietf.org>; Mon, 18 Nov 2013 13:34:55 -0800 (PST)
Received: by mail-ee0-f41.google.com with SMTP id t10so1551463eei.14 for <tls@ietf.org>; Mon, 18 Nov 2013 13:34:49 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:date:message-id:subject:from:to :content-type:content-transfer-encoding; bh=F3YyHL5H97+ldySxeteQoc92Xzxiu+PeQzU+i2VrcKg=; b=CgL5rw7pSgpoqC24Nid1QH9xVMw7aTHxdb6/gbWhel0nsvQkoia/XPYk47mgRCV92b I16MKqdqLKgQhQSVVsqPQLGYDFU4+Tt5AoaM0088eVqkcF6Z4aujAQFoUFM4pmfPKRf8 gVBYVMDfMPNfvkqSORstrQWBiM4PVyimwC3okY3zY6IoB3NQFeotmDwGZoAORZ4CF/xg ggdkNuXCwIIIWpiYHZTJ12mLYBo7xyqIavOSfKNR+ArxuJrHuPOnvEtcERuzBm7UBu0z 0ejoxgtzggGDHAYPLQzCuwo/jsYBYoQi6U/vYRP+ghPfngZnt2I3l8klgcWDUG1NDM0I 9QVw==
X-Gm-Message-State: ALoCoQmPqO9P2VKLrIJnf9gkkHKA6aOt+kMTw0wTrPmGIbLiJShEFeB2nLJ0M1vRtMGeetoBxkd7
MIME-Version: 1.0
X-Received: by 10.14.103.69 with SMTP id e45mr6060312eeg.51.1384810489621; Mon, 18 Nov 2013 13:34:49 -0800 (PST)
Received: by 10.223.174.198 with HTTP; Mon, 18 Nov 2013 13:34:49 -0800 (PST)
X-Originating-IP: [67.173.237.98]
Date: Mon, 18 Nov 2013 21:34:49 +0000
Message-ID: <CAM_a8JzY8VGq+N-5YbDk_3EdXkKJzof1BtUTVY8pJev2HZ9U6g@mail.gmail.com>
From: Zooko Wilcox-OHearn <zooko@leastauthority.com>
To: tls@ietf.org
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: [TLS] Salsa vs. ChaCha
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 18 Nov 2013 21:34:58 -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.