[noise] PSK-based resumption, postquantum, and XOFs

[Trevor Perrin]

We're closing in on designs for PSK-based resumption and
hybrid/post-quantum forward-secrecy.  These both require additional
hashing-type functions.  We've also thought about allowing XOFs (like
SHAKE128 or SHAKE256) in place of a hash function.

I'd like to discuss the resumption PSK and post-quantum designs and
their implications for our hash APIs and possible XOF suppport.


PSK-based resumption
---------------------
One missing piece is deriving resumption PSK(s) from an initial session.

We could derive an "extra derivation key" as a 3rd HKDF output from
Split(), then use this to generate a sequence of PSKs.  We only need a
PRF for this, e.g. HMAC.  This would be something like:

Split():
  temp_k1, temp_k2, extra_derivation_key = HKDF(ck, zerolen, 3)
  psk_ck = PRF(extra_derivation_key, "psk")

Deriving PSKs:
  psk_ck, psk1 = PRF(psk_ck)
  psk_ck, psk2 = PRF(psk_ck)
  psk_ck, psk3 = PRF(psk_ck)
  ...

Note that all PSKs are independent from other keys (once they're
derived, the previous psk_ck is deleted, after which the PSK can't be
derived from any other key).

Also, by passing in other strings besides "psk" to Split(), we can
generate similar "extra" key sequences for other purposes, so this is
a general mechanism for extra keys.


Hybrid forward secrecy
-----------------------
We've talked about supporting additional types of DH and KEM
functions, and then using these for hybrid forward secrecy.  For
example, here are DH and KEM examples for adding hybrid
forward-secrecy to XX:

XX+hfs (with hybrid DH, e.g. 25519+448)
  -> e, e1
  <- e, e1, ee, e1e1, s, es
  -> s, se

XX+hfs (with hybrid KEM, e.g. 25519+Kyber or 25519+RSA3072)
  -> e, e1
  <- e, ee, e1kem, s, es
  -> s, se

Some public-key algorithms, in particular for post-quantum, might
require a hash or XOF-type function.  E.g., Kyber was originally
designed on cSHAKE but recently changed to SHAKE, and the designers
have suggested they might be willing to use "callbacks" to a function
provided by the protocol, so perhaps Noise just has to provide a
similar API, based on whatever hash it's using.


XOFs
=====
Currently, Noise "takes" a HASH function and constructs an HKDF function.

In above cases, we'd also need to provide PRF and XOF functions, e.g.
PRF=HMAC and XOF=HKDF.

We might also like to "take" an XOF and provide the same set of
functions, in case people want to use functions like SHAKE128,
SHAKE256, BLAKE2Xs, or BLAKE2Xb with Noise, and avoid HMAC/HKDF.

This is not simple because "XOF" is still a young notion that is
interpreted in different ways.  For example:
 - For Keccak, SHAKE128 and SHAKE256 are unkeyed functions from
message -> byte stream.
 - For Keccak, KMACXOF128 and KMACXOF256 are keyed functions from
(message, output length|infinite, customization string) -> byte
stream.  Note that the output is diversified based on output length
(unless you request the infinite byte stream version), and
customization string.
 - For BLAKE2, BLAKE2X are keyed or unkeyed functions similar to
KMACXOF in terms of length-handling, and with a personalization string
similar to KMACXOF's customization string except of fixed length (I
think 8 or 16 bytes).

Since keyed BLAKE2X and KMACXOF are pretty close, one could argue this
represents the most "unified" API.

However SHAKE is the simpler and more widely-accepted Keccak function,
and avoids all the encoding and options in KMACXOF.  For example,
KMACXOF processes an initial hash block just to absorb the name "KMAC"
and the customization string.  You could precalculate that output, but
this complication is avoided with SHAKE.

So if we want to plug XOFs into Noise, I'd suggest adopting a simple,
SHAKE-like notion, and then constructing what we need on top of that.

Putting this together, Noise could require choosing either a HASH or
XOF.  If a HASH is chosen, these functions are constructed:
 - PRF(key, message) = HMAC(key, message)
 - KDF(key, input) = HKDF(key, input)

If an XOF is chosen, these functions are constructed:
 - HASH(message) = XOF(message)
 - PRF(key, message) = XOF(pad_to_block(key) || message)
 - KDF(key, message) = XOF(pad_to_block(key) || input)

Using SHAKE or BLAKE2X would gives a simpler, perhaps cleaner, but
less-conservative approach to hashing.  But we could keep the more
traditional HKDF/HMAC constructions using SHA3 or BLAKE2 as the
recommendation, for the time being.

Thoughts?


Trevor