[Cryptography] Evaluating draft-agl-tls-chacha20poly1305

[Adam Langley]

On Tue, Sep 10, 2013 at 10:59 PM, William Allen Simpson
<william.allen.simpson at gmail.com> wrote:
> I suggest:
>
>    ChaCha20 is run with the given key and sequence number nonce and with
>
>    the two counter words set to zero.  The first 32 bytes of the 64 byte
>    output are saved to become the one-time key for Poly1305.  The next 8
>    bytes of the output are saved to become the per-record input nonce
>    for this ChaCha20 TLS record.
>
> Or you could use 16 bytes, and cover all the input fields....  There's no
> reason the counter part has to start at 1.
>
> Of course, this depends on not having a related-key attack, as mentioned
> in my previous messages

It is the case that most of the bottom row bits will be zero. However,
ChaCha20 is assumed to be secure at a 256-bit security level when used
as designed, with the bottom row being counters. If ChaCha/Salsa were
not secure in this formulation then I think they would have to be
abandoned completely.

Nobody worries that AES-CTR is weak when the counter starts at zero, right?

Taking 8 bytes from the initial block and using it as the nonce for
the plaintext encryption would mean that there would be a ~50% chance
of a collision after 2^32 blocks. This issue affects AES-GCM, which is
why the sequence number is used here.

Using 16 bytes from the initial block as the full bottom row would
work, but it still assumes that we're working around a broken cipher
and it prohibits implementations which pipeline all the ChaCha blocks,
including the initial one. That may be usefully faster, although it's
not the implementation path that I've taken so far.

There is an alternative formulation of Salsa/ChaCha that is designed
for random nonces, rather than counters: XSalsa/XChaCha. However,
since we have a sequence number already in TLS I've not used it.


Cheers

AGL