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

From: Stefan Bühler <[email-masked]>
Date: Fri, 28 Feb 2014 12:14:48 +0100

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

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Fri, 28 Feb 2014 14:26:07 +0000

Stefan:

  Will you be at Monday's meeting in London?  We could discuss this in
more depth after Yoav's presentation.

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Stefan Bühler
> Sent: Friday, February 28, 2014 6:15 AM
> To: Yoav Nir; [email-masked]
> Subject: Re: [Cfrg] I-D Action: draft-nir-cfrg-chacha20-poly1305-01.txt
> 
> Hi,
> 
> Define Q: calculates HChaCha from 64-bit nonce and 512-bit ChaCha Q(n,
> x) := P(x) - (salsaconst, n)  # subtraction on 32-bit words
> 
> 64-bit counter XChaCha20_k(n, i) = ChaCha20_k1(n2, i)
>     where
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Stefan Bühler <[email-masked]>
Date: Fri, 28 Feb 2014 16:05:22 +0100

On Fri, 28 Feb 2014 14:26:07 +0000

> more depth after Yoav's presentation.

No, sorry, I will not be at the meeting.