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

Samuel Neves <sneves@dei.uc.pt> Sat, 07 December 2013 02:28 UTC

Return-Path: <sneves@dei.uc.pt>
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 0114A1AE12A for <tls@ietfa.amsl.com>; Fri, 6 Dec 2013 18:28:13 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.602
X-Spam-Level:
X-Spam-Status: No, score=-2.602 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001] 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 8Qh69sAw8-Z4 for <tls@ietfa.amsl.com>; Fri, 6 Dec 2013 18:28:10 -0800 (PST)
Received: from smtp.dei.uc.pt (smtp.dei.uc.pt [193.137.203.253]) by ietfa.amsl.com (Postfix) with ESMTP id E03401AE0F6 for <tls@ietf.org>; Fri, 6 Dec 2013 18:28:09 -0800 (PST)
Received: from [192.168.1.64] ([188.251.178.92]) (authenticated bits=0) by smtp.dei.uc.pt (8.14.4/8.14.4) with ESMTP id rB72ReoC032207 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Sat, 7 Dec 2013 02:27:46 GMT
Message-ID: <52A287A1.1030501@dei.uc.pt>
Date: Sat, 07 Dec 2013 02:27:45 +0000
From: Samuel Neves <sneves@dei.uc.pt>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.1.1
MIME-Version: 1.0
To: Robert Ransom <rransom.8774@gmail.com>, Nick Mathewson <nickm@torproject.org>
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> <CAKDKvuw0EKJpbGxOmGGUHK3m0fOy43wwCLh3ZO-a06xrK2Mebg@mail.gmail.com> <CABqy+sr2-7E1+r7d4W0H2aLT+pSBjeC7yLd9Uj0tovG=Owjogw@mail.gmail.com>
In-Reply-To: <CABqy+sr2-7E1+r7d4W0H2aLT+pSBjeC7yLd9Uj0tovG=Owjogw@mail.gmail.com>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-FCTUC-DEI-SIC-MailScanner-Information: Please contact helpdesk@dei.uc.pt for more information
X-FCTUC-DEI-SIC-MailScanner-ID: rB72ReoC032207
X-FCTUC-DEI-SIC-MailScanner: Found to be clean
X-FCTUC-DEI-SIC-MailScanner-SpamCheck: not spam, SpamAssassin (not cached, score=-60.25, required 3.252, autolearn=not spam, ALL_TRUSTED -10.00, BAYES_00 -0.25, L_SMTP_AUTH -50.00)
X-FCTUC-DEI-SIC-MailScanner-From: sneves@dei.uc.pt
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: Sat, 07 Dec 2013 02:28:13 -0000

On 06-12-2013 16:42, Robert Ransom wrote:
> On 12/6/13, Nick Mathewson <nickm@torproject.org> wrote:
>
>
>> 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.
> 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.

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