[noise] NXOF?

[Trevor Perrin]

So the message at [1] considered whether Noise protocols could use a
SHAKE-style XOF (eg "Noise_XX_25519_AESGCM_SHAKE256"), without
HMAC/HKDF.

It also considered whether we could provide an XOF API to public-key
algorithms that need such a thing, even implemented on top of an
existing HASH (eg "Noise_X1X1kem_PQQKEM_AESGCM_SHA256", where "PQKEM"
is some hypothetical postquantum KEM algorithm that uses an XOF
internally).

An issue that arises if we give a PQKEM algorithm access to our
hash/XOF function is making sure that the PQKEM's calls are
domain-separated from hash/XOF calls in the rest of Noise.  My post at
[1] didn't consider this, so I'll make a proposal here (at bottom).

---

First, let's consider cSHAKE.  NIST put some effort into
domain-separation with the cSHAKE framework [2].  Roughly:

 - There is a NIST-assigned "function name" for each cSHAKE variant
("TupleHash", "ParallelHash", "KMAC", etc).

 - There is a user-assigned "customization string".  NIST gives the
example of "key fingerprint" and "email signature".

As [1] points out, some PQC candidates use the cSHAKE customization
string to internally differentiate their calls (e.g. using 0, 1, and 2
for different uses).

However, none of this addresses our problem:

 - All of the PQC algorithms I looked at would share the same NIST
"function name" between the PQC agorithm and uses of these same
functions in the rest of Noise.  Perhaps NIST will assign different
function names later in the process, but relying on NIST to maintain a
globally-unique namespace seems awkward.

 - The "customization strings" mentioned in [1] are used for
domain-separation within the PQC algorithm, not for separation with
external calls to the same function, in the rest of Noise.

Also, I find it awkward that the cSHAKE framework can't be built on
top of a function like SHAKE, but instead requires lower-level access
to Keccak, which libraries are less likely to provide (I think).

---

Anyways, it seems like we want domain-separation at multiple levels:
 - Noise wants to separate its own uses of HASH/XOF functions from the
PQC algorithm's uses
 - The PQC algorithms wants to separate their internal uses.

There's a "nested" structure here, so I'll propose a convention around
"nested" scopes.

For example, imagine a "Nested XOF" or "NXOF" function which is
defined by some "scope" byte-sequence used as a prefix when hashing,
and an underlying SHAKE-like XOF.

Given an NXOF you can produce child NXOFs by appending a set of
prefix-free inputs to the scope.  For example:
 - a set of length-prefixed values, or
 - a set of fixed-length values, or
 - a set of hash values

For example, we could view Noise's MixHash() as outputing an NXOF
where the new scope "h" contains a hash value produced from the
previous NXOF.

>From this perspective, when we come to a PQKEM call, we could just
split the current scope "h" into two scopes, e.g. by
MixHash("0")/MixHash("1"), or just appending "0" and "1" to h, or
something else.  We would pass one of the new NXOFs to the PQKEM
function, and use the other as the new "h".

The PQKEM algorithm would take an NXOF as input, and could then use
this framework recursively, i.e. it could append additional
prefix-free values onto the received scope to domain-separate its
internal uses.

Does this framework make sense?  Would it be worth trying to promote
something like this, as an alternative to cSHAKE?

Trevor


[1] https://moderncrypto.org/mail-archive/noise/2018/001482.html
[2] https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf