[noise] Rekey

[Matthias-Christian Ott]

On 2017-03-15 00:24, Trevor Perrin wrote:
> Per [1] I'd like to add a "rekey" capability to Noise which replaces a
> CipherState's key with a one-way function of the key, for forward
> secrecy.
> 
> The application would decide if/when to rekey the transport
> Cipherstates, e.g. after every Noise message, or every application
> message, or when indicated by some application-layer signal.

You have to change keys after some time. See for example [1] and the
referenced literature. So for long messages the application should not
be in control of rekeying.

> This should be capable of handling a high frequency of rekeys (e.g.
> after every message).
> 
> Assume a function F(k) that returns a new key based on an input key
> (e.g. encrypting a block of zeros with k).  Some options:
> 
> (A)  k, n = F(k), 0
> 
> (B)  k, n = F(k), n
> 
> (C)  k, n = F(k) XOR n, n
> 
> 
> B and C don't reset n so the number of encryptions is still < 2^64
> across all rekeys.  I guess that puts a bound on how much entropy
> might be lost by iterating a non-injective function?

I'm assuming that n is a nonce and k is a key used for symmetric encryption.

If the nonce arithmetic wraps on overflow (like in most programming
languages), that is (2^64 - 1) + 1 = 0, and is used for less than 2^64
octets or blocks, you don't have to reset the nonce because you changed
the key to a new random and unique key. But for symmetry, I would change
it to 0. It also helps to avoid implementation mistakes for languages
that raise an error on overflow.

Alternatively you can also use an approach similar to XSalsa20 [2].

F(k) has also been discussed in the literature (see for example
[3,4,5]). If you use the serial generator from [3], you should also be
able to apply HDKF-expand to K and HKDF-extract with different info
values as F to compute K and Out. I haven't done the proof, but it seems
it would be analogous or you would have to prove that HKDF is a PRF. You
can also use HMAC as F in the serial generator [6].

> C is the sort of trick I've seen people do to protect against short
> cycles.  I've never been super-clear what analysis this is based on,
> or whether it's just superstition?

It makes little sense to me. Can you explain what you mean by "short
cycles"?

> Thoughts, from any cryptographers?

I wouldn't call myself a cryptographer but I had the same problem
recently. So please see my remarks with caution.

- Matthias-Christian

[1] https://eprint.iacr.org/2015/893
[2] https://cr.yp.to/papers.html#xsalsa
[3] https://cseweb.ucsd.edu/~mihir/papers/rekey.html
[4] https://eprint.iacr.org/2001/035
[5] http://tuprints.ulb.tu-darmstadt.de/6021/
[6] https://cseweb.ucsd.edu/~mihir/papers/hmac-new.html