[noise] HASH/XOF refactoring

[Trevor Perrin]

For the next spec revision, let's consider if we want any refactoring
of our HASH concepts to prepare for XOFs, Postquantum KEMs, and/or PSK
derivation.

This was discussed in [1], but I'll re-summarize and look at new data
from the NIST PQ competition.

(There's a proposal at the bottom, if you want to skip to it.)


Motivating points:

 * There are "Extensible Output Functions" like SHAKE, cSHAKE,
KMACXOF, and BLAKE2X that someone might prefer instead of a "HASH"
function.  In particular, these might be a better use of Keccak than
the "SHA3" hash functions.

 * Post-quantum KEMs are generally being defined on top of XOFs like
SHAKE or cSHAKE.  It's unclear whether the hash/XOF is best treated as
an internal part of the PQ algorithm, or should be supplied by an
external API.  But for the latter case, maybe we should be prepared to
supply an XOF-style API, even on top of a HASH function like SHA2.

 * We've talked about being able to derive additional keys from a
handshake, e.g. for PSK-based resumption.  The construction we choose
might be PRF-based instead of needing a full KDF.

---

Here's what a sample of NIST submissions do wrt hashes and XOFs.  For
the cSHAKE users, I also listed how they're using the "customization"
value.

HILA5 (SHA3-256 and SHAKE-256)
Kyber (SHAKE-128, SHAKE-256, SHA3-256, SHA3-512)
LUOV (SHAKE-128, SHAKE-256)
NTRUEncrypt (SHA-512, SHA3-512, SHAKE-256)

FrodoKem (cSHAKE128 or cSHAKE256)
 - customization = 16-bit integer

Three Bears (cSHAKE256)
 - doesn't use customization (parameter block as prefix)
 - parameter block as prefix

SIKE
 - customization = 0, 1, or 2


Observations:
  - NIST KMAC/KMACXOF and TupleHash/TupleHashXOF don't seem popular?
  - The "customization strings" in use are small and fixed-length, so
could easily be fixed-length prefixes to the input, and don't seem
that important as an API.
  - There's a lot of slightly-different choices being made (cSHAKE vs
SHAKE vs SHA3), not sure this is going to resolve to a common approach
any time soon.

An approach we could take:
  (1) If the public-key algorithm has strong opinions about
XOF/hashing, it can define them internally, and it's not our problem.
  (2) We could provide a simple SHAKE-style XOF API, and PQ algorithms
that can be built on SHAKE can use that.

Most algorithms focus on (1), which is a natural result of
cryptographers focusing on their algorithm in isolation.  But I think
(2) would be more convenient in many systems, where you'd rather have
everything use the same hash-type algorithm.

So if we designed for (2), maybe we could steer people towards
thinking about this more.

It's debatable whether a SHAKE or cSHAKE API is the best, but if this
is early enough for us to influence things, we could push for SHAKE,
and try to get people to ignore/kill cSHAKE and its over-complexity...

(Of course, that would be an opinionated stance, NIST seems to think
cSHAKE was a good idea).

---

The other motivating use-case is deriving extra keys after the
handshake, as discussed in [1].  We already have a good key at this
point (e.g. an additional output from Split), so we don't need a full
HKDF.

We only need a PRF like HMAC, but for generality maybe this should
support arbitrary-length output so perhaps a "keyed XOF" ("KXOF"?) is
a better way to think about this, which could be synthesized via, say,
HKDF-Expand (just using the Expand part of HKDF, not the Extract).

---

Anyways, I'm imagining the spec taking an input function (HASH or
XOF), and transforming it into several output functions.

HASH is transformed via HMAC and HKDF.  The XOF is transformed via a
prefix-keyed version, that just processes a key in an initial block.

Input:
    HASH or (SHAKE-style) XOF

Outputs (and how they are constructed from inputs, in parentheses):
    HASH (XOF)
    KDF  (HKDF-HASH or Prefix-XOF)
    XOF  (HKDF-HASH with empty salt)
    KXOF (HKDF-EXPAND-HASH or Prefix-XOF)

Thoughts?

Trevor

[1] https://moderncrypto.org/mail-archive/noise/2017/001402.html