Re: [Cfrg] I-D Action: draft-nir-cfrg-chacha20-poly1305-01.txt

[Stefan Bühler <[e-mail]>]

Hi,

I propose using "HChaCha20" (analog to HSalsa20) to compress larger
nonces:
* supports nonce lengths of 8 and 24 bytes, and everything between by
  prefixing with zeros.
  (I can't claim to have understood the paper on XSalsa20/HSalsa20
  completely, so I'm not sure whether more than one HSalsa20 step would
  still be covered by the proof; but I guess it should work.
  This means one could support almost any nonce length >= 8 bytes)
* uses the original ChaCha20 algorithm (some implementations might not
  allow changing the length of nonce/counter; these implementations
  are still compatible with a nonce length of 8 bytes)
* compatible with draft-agl-tls-chacha20poly1305-04 (using nonce length
  of 8 bytes, plain ChaCha20)

Define P: extract 256-bit from 512-bit
P(z0, z1, z2, z3) := (z0, z3)  # z_i are 128-bit

Define HChaCha20: takes 256-bit key, 128-bit nonce
HChaCha20_k(n) := P(doublerounds^10(x))
    where
    x := (salsaconst, k, n)

Define Q: calculates HChaCha from 64-bit nonce and 512-bit ChaCha
Q(n, x) := P(x) - (salsaconst, n)  # subtraction on 32-bit words

HChaCha20_k(n) = Q(n, ChaCha20_k(n))
(Q is used in the proof: it is a public computation (salsaconst and
nonce are public) of HChaCha20_k(n) from ChaCha_k(n), and maps uniform
random strings to uniform random strings)

Define XChaCha20: takes 256-bit key, 192-bit nonce and a little-endian
64-bit counter
XChaCha20_k(n, i) = ChaCha20_k1(n2, i)
    where
    (n1, n2) := n # n1 is 128-bit, n2 64-bit
    k1 := HChaCha20_k(n1)

The proof for XSalsa20/HSalsa20 should work for XChaCha20/HChaCha20 too
afaics. (http://cr.yp.to/snuffle/xsalsa-20110204.pdf
on http://cr.yp.to/snuffle.html)

Now depending on the length of the nonce either use ChaCha20 (8 byte
nonce) or XChaCha20 (24 byte nonce).

I suggest the zero padding should be prefixed to the nonce, so the last
8 bytes of the AEAD nonce are always the 8 bytes used in the ChaCha20
stream. If only those are changed (typical nonce increment) the
key/nonce compression "k1" can be cached.

Padding nonces should be safe: if the input nonces were unique, the
padded nonces are unique too. As nonces are often counters anyway, they
already are almost 0 - adding more zeros shouldn't hurt.

regards,
Stefan