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

Nick Mathewson <nickm@torproject.org> Fri, 06 December 2013 15:21 UTC

Return-Path: <nick.a.mathewson@gmail.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 0D3771AE050 for <tls@ietfa.amsl.com>; Fri, 6 Dec 2013 07:21:14 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.678
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id xJZG1gKncexv for <tls@ietfa.amsl.com>; Fri, 6 Dec 2013 07:21:13 -0800 (PST)
Received: from mail-qc0-x22e.google.com (mail-qc0-x22e.google.com [IPv6:2607:f8b0:400d:c01::22e]) by ietfa.amsl.com (Postfix) with ESMTP id BDD9B1AE039 for <tls@ietf.org>; Fri, 6 Dec 2013 07:21:12 -0800 (PST)
Received: by mail-qc0-f174.google.com with SMTP id n7so549255qcx.19 for <tls@ietf.org>; Fri, 06 Dec 2013 07:21:08 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; 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 10.49.17.196 with SMTP id q4mr7535184qed.31.1386343268673; Fri, 06 Dec 2013 07:21:08 -0800 (PST)
Sender: nick.a.mathewson@gmail.com
Received: by 10.140.102.82 with HTTP; Fri, 6 Dec 2013 07:21:08 -0800 (PST)
In-Reply-To: <1386336151.3430.34.camel@dhcp-2-127.brq.redhat.com>
References: <CAM_a8JzY8VGq+N-5YbDk_3EdXkKJzof1BtUTVY8pJev2HZ9U6g@mail.gmail.com> <1384850165.2542.13.camel@dhcp-2-127.brq.redhat.com> <5296C6D7.2040509@dei.uc.pt> <1386332388.3430.22.camel@dhcp-2-127.brq.redhat.com> <CABqy+spiBPaGrk7ipeWvC2Z_B=MeDVZAmmEbXL-Pa2Lf-6UA2Q@mail.gmail.com> <1386336151.3430.34.camel@dhcp-2-127.brq.redhat.com>
Date: Fri, 6 Dec 2013 10:21:08 -0500
X-Google-Sender-Auth: o7LGTiMHVYrjhIFaKjoF4hKTTuw
Message-ID: <CAKDKvuw0EKJpbGxOmGGUHK3m0fOy43wwCLh3ZO-a06xrK2Mebg@mail.gmail.com>
From: Nick Mathewson <nickm@torproject.org>
To: Nikos Mavrogiannopoulos <nmav@redhat.com>
Content-Type: text/plain; charset=ISO-8859-1
Cc: "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] chacha to replace RC4 (was: 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: Fri, 06 Dec 2013 15:21:14 -0000

On Fri, Dec 6, 2013 at 8:22 AM, Nikos Mavrogiannopoulos <nmav@redhat.com> 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.



hth,
-- 
Nick Mathewson