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

[Nick Mathewson <[e-mail]>]

On Fri, Dec 6, 2013 at 8:22 AM, Nikos Mavrogiannopoulos <[e-mail]> 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