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

[Samuel Neves <[e-mail]>]

On 06-12-2013 16:42, Robert Ransom wrote:
> On 12/6/13, Nick Mathewson <[e-mail]> 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