[noise] Stateful Hash Object Proposal

[Trevor Perrin]

The "SHO" API and examples were still vague.  Here's another pass.

One goal is to make this API useful for more than just Noise
transcript hashing.  For example, Noise could provide a SHO API to
public-key algorithms like postquantum KEMs that use a hash function
internally.


API
----
Same as before:

StatefulHashObject {

    Absorb(bytes)
    Squeeze(len) -> bytes
    Ratchet()

    Clone() -> StatefulHashObject

    // Below functions are optional.
    // If supported, Encrypt() must have same properties as:
    //   key = Squeeze'(32);
    //   ciphertext = Authenticated-Encryption(key, plaintext)
    //   Absorb(ciphertext)
    //   return ciphertext
    //
    //   where Squeeze' is a domain-separated version of Squeeze()
    //   and ciphertext is 16 bytes longer than plaintext

    Encrypt(bytes) -> bytes
    Decrypt(bytes) -> bytes
}


Q: Should Absorb(X),Absorb(Y) be the same as Absorb(X || Y)?

A: Yes, since we want this to be easily implemented with the
init-update-finalize API that is common for hash functions.


Q: How much output can you request from Squeeze()?

A: Initially I proposed HASHLEN, to match traditional hash functions
and not take up space in the hash-block input with an extra length
field.  However if we do HASH(HASH(input)), it costs almost nothing to
do HASH(HASH(input) || counter).  Also, for PQ KEM use, people want to
generate longer outputs from a small seed, and asking them to Clone
and increment a counter on their own is awkward.

So I think Squeeze() should be "XOF"-style: return an arbitrary-length
prefix of some "infinite" byte sequence.


Q: When can you call Squeeze()?  Once, after finished Absorbing?
Multiple times after finished Absorbing?  Interleaved with Absorbing?

A: If you can interleave Squeeze() with Absorb() then we have to
either encode the Squeeze calls into the input so that they add to the
hash input; or internally clone the state in Squeeze so that Squeeze
calls don't change it.

If the caller wants to interleave Absorb and Squeeze then they can
just clone the object doing the Absorbing, and squeeze from the clone
(as Noise would do).

So it seems like we should just define Squeeze() as a one-shot
function you call after absorbing, though people could implement it in
a streaming fashion if they wanted.


With those answers, a SHO is very close to an XOF (like SHAKE) that
supports a streaming input.

The main additions being a Ratchet capability to put its internal
state through a one-way function, and an optional Encrypt capability
to optimize the sequence: Squeeze Key / encrypt / Absorb Ciphertext.


Example SHOs
-------------
We could build a SHO from an existing hash function in different ways,
depending on:

 * Is the function already an XOF?  If not, we have to concatenate
outputs based on a counter.  We'll do this with HASH(HASH(input) ||
counter), where the counter is a varint.  This also prevents against
length-extension.

 * Is the internal function used to process each block (e.g. the
compression function or permutation; call it "f") a one-way function?
If not, we need to zeroize some of the state (e.g. the permutation's
"rate") so the block-processing function (e.g. Keccak permutation)
can't be inverted.


SHA3 (not xof, not owf):
  Absorb(data) : update(data)
  Ratchet()    : update(pad_to_block); f(); zeroize()
  Squeeze(len) : h = finalize(); return HASH(h || 0)  ||  HASH(h || 1) ...

SHA2 / BLAKE2 (not xof, owf):
  Absorb(data) : update(data)
  Ratchet()    : update(pad_to_block); f()
  Squeeze(len) : h = finalize(); return HASH(h || 0)  ||  HASH(h || 1) ...

SHAKE (xof, not owf):
  Absorb(data) : update(data)
  Ratchet()    : update(pad_to_block); f(); zeroize()
  Squeeze(len) : return finalize(len)

BLAKE2X (xof, owf):
  Absorb(data) : update(data)
  Ratchet()    : update(pad_to_block); f();
  Squeeze(len) : finalize(len)


We could also implement this with STROBE:

STROBE:
  Absorb(data) : AD(data, more=true)
  Ratchet()    : RATCHET()
  Squeeze(len) : PRF(len)
  Encrypt(data) : ENC(data), PRF(16)
  Decrypt(data) : DEC(data), PRF(16)


Trevor