[noise] HASH/XOF refactoring

[Alexey Ermishkin]

Hi Trevor!
I personally used shake and blake2x and find them more useful in case you need to feed several parts of data to "hash"  before extracting, say, a pair of keys. So you can keep a single instance of XOF till the very end of your state flow. 

-----Original Message-----
From: Noise [mailto:noise-bounces at moderncrypto.org] On Behalf Of Trevor Perrin
Sent: Thursday, February 22, 2018 11:08 PM
To: noise <noise at moderncrypto.org>
Subject: [noise] HASH/XOF refactoring

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
_______________________________________________
Noise mailing list
Noise at moderncrypto.org
https://moderncrypto.org/mailman/listinfo/noise