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

Nick Mathewson <> Fri, 06 December 2013 15:21 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 0D3771AE050 for <>; Fri, 6 Dec 2013 07:21:14 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.678
X-Spam-Status: No, score=-0.678 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FM_FORGED_GMAIL=0.622, FREEMAIL_FROM=0.001, J_CHICKENPOX_35=0.6, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id xJZG1gKncexv for <>; Fri, 6 Dec 2013 07:21:13 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:400d:c01::22e]) by (Postfix) with ESMTP id BDD9B1AE039 for <>; Fri, 6 Dec 2013 07:21:12 -0800 (PST)
Received: by with SMTP id n7so549255qcx.19 for <>; Fri, 06 Dec 2013 07:21:08 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=N488GWlRdiYmHYRRCaK/ab1Uvy8tEi5pvrM+nLvm7a8=; b=weN3DdHLTGPewJUXJnd2/ox2nwGn80cciRbYNOXKNEg6hK9BAviS9nbuwWFHQIxGx9 9JnxJThWunNoOiZn2pz4vxaBogHTdFNa5NIYNQpodnlJeIF77AOWWMNBYC0ZbWGPmfsC IcSVHb55LnhjkLURxo9ktfigMXUIQKEdsncJf0NheNuGtS7uYAsGCdk7zJ4DSdRGtMXT zi6xCnUqjou95DK71a4hUNuggKO6LTOJlV3Xi4ovpA3BrRZmF8yUM2sUQDgFslj87Rof rI7vjx2vgKtrdz6Y4Ss57GUVyVMPujTmDKtgyy7VYmH5ROZmEGGhjq6ZIZso7/q7mVQ0 LtHQ==
MIME-Version: 1.0
X-Received: by with SMTP id q4mr7535184qed.31.1386343268673; Fri, 06 Dec 2013 07:21:08 -0800 (PST)
Received: by with HTTP; Fri, 6 Dec 2013 07:21:08 -0800 (PST)
In-Reply-To: <>
References: <> <> <> <> <> <>
Date: Fri, 6 Dec 2013 10:21:08 -0500
X-Google-Sender-Auth: o7LGTiMHVYrjhIFaKjoF4hKTTuw
Message-ID: <>
From: Nick Mathewson <>
To: Nikos Mavrogiannopoulos <>
Content-Type: text/plain; charset=ISO-8859-1
Cc: "" <>
Subject: Re: [TLS] chacha to replace RC4 (was: Salsa vs. ChaCha)
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." <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 06 Dec 2013 15:21:14 -0000

On Fri, Dec 6, 2013 at 8:22 AM, Nikos Mavrogiannopoulos <> wrote:
> On Fri, 2013-12-06 at 04:54 -0800, Robert Ransom wrote:
>> 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.
> 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?

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.

Nick Mathewson