[noise] Stateful Hash Object Proposal

[Nadim Kobeissi]

Good evening everyone,

I've caught up on this SHO API discussion. I like the SHO proposal and have
nothing to add to it (although it looks like Peter may.) It's nice and it
makes sense.

>From a formal verification standpoint, it does not seem that adopting this
proposal would cause the models produced by Noise Explorer to be more
difficult or complex to verify. Which is really all I care about on my end
aside from, of course, the API's general simplicity and reasonableness.

If this SHO API is chosen to be integrated into the Noise Protocol
Framework, I pledge to integrate it, in tandem, into Noise Explorer so that
new verification results can be obtained in time for the publication of the
new Noise Protocol Framework specification revision.

This all seems very nice and I hope, in case this venue is pursued, that I
can be of assistance.

Best regards,

Nadim Kobeissi
Symbolic Software • https://symbolic.software
Sent from office


On Sat, Nov 17, 2018 at 11:11 AM Trevor Perrin <trevp at trevp.net> wrote:

> 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
> _______________________________________________
> Noise mailing list
> Noise at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/noise
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/noise/attachments/20181123/12ca15ce/attachment.html>