<div dir="ltr">Good evening everyone,<div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>This all seems very nice and I hope, in case this venue is pursued, that I can be of assistance.</div><div><br></div><div>Best regards,</div><div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><br></div><div dir="ltr">Nadim Kobeissi<div>Symbolic Software <span style="color:rgb(84,84,84);font-size:small">• <a href="https://symbolic.software" target="_blank">https://symbolic.software</a></span></div><div><span style="color:rgb(84,84,84);font-size:small">Sent from office</span></div></div></div></div></div></div><br></div></div><br><div class="gmail_quote"><div dir="ltr">On Sat, Nov 17, 2018 at 11:11 AM Trevor Perrin <<a href="mailto:trevp@trevp.net">trevp@trevp.net</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">The "SHO" API and examples were still vague.  Here's another pass.<br>
<br>
One goal is to make this API useful for more than just Noise<br>
transcript hashing.  For example, Noise could provide a SHO API to<br>
public-key algorithms like postquantum KEMs that use a hash function<br>
internally.<br>
<br>
<br>
API<br>
----<br>
Same as before:<br>
<br>
StatefulHashObject {<br>
<br>
    Absorb(bytes)<br>
    Squeeze(len) -> bytes<br>
    Ratchet()<br>
<br>
    Clone() -> StatefulHashObject<br>
<br>
    // Below functions are optional.<br>
    // If supported, Encrypt() must have same properties as:<br>
    //   key = Squeeze'(32);<br>
    //   ciphertext = Authenticated-Encryption(key, plaintext)<br>
    //   Absorb(ciphertext)<br>
    //   return ciphertext<br>
    //<br>
    //   where Squeeze' is a domain-separated version of Squeeze()<br>
    //   and ciphertext is 16 bytes longer than plaintext<br>
<br>
    Encrypt(bytes) -> bytes<br>
    Decrypt(bytes) -> bytes<br>
}<br>
<br>
<br>
Q: Should Absorb(X),Absorb(Y) be the same as Absorb(X || Y)?<br>
<br>
A: Yes, since we want this to be easily implemented with the<br>
init-update-finalize API that is common for hash functions.<br>
<br>
<br>
Q: How much output can you request from Squeeze()?<br>
<br>
A: Initially I proposed HASHLEN, to match traditional hash functions<br>
and not take up space in the hash-block input with an extra length<br>
field.  However if we do HASH(HASH(input)), it costs almost nothing to<br>
do HASH(HASH(input) || counter).  Also, for PQ KEM use, people want to<br>
generate longer outputs from a small seed, and asking them to Clone<br>
and increment a counter on their own is awkward.<br>
<br>
So I think Squeeze() should be "XOF"-style: return an arbitrary-length<br>
prefix of some "infinite" byte sequence.<br>
<br>
<br>
Q: When can you call Squeeze()?  Once, after finished Absorbing?<br>
Multiple times after finished Absorbing?  Interleaved with Absorbing?<br>
<br>
A: If you can interleave Squeeze() with Absorb() then we have to<br>
either encode the Squeeze calls into the input so that they add to the<br>
hash input; or internally clone the state in Squeeze so that Squeeze<br>
calls don't change it.<br>
<br>
If the caller wants to interleave Absorb and Squeeze then they can<br>
just clone the object doing the Absorbing, and squeeze from the clone<br>
(as Noise would do).<br>
<br>
So it seems like we should just define Squeeze() as a one-shot<br>
function you call after absorbing, though people could implement it in<br>
a streaming fashion if they wanted.<br>
<br>
<br>
With those answers, a SHO is very close to an XOF (like SHAKE) that<br>
supports a streaming input.<br>
<br>
The main additions being a Ratchet capability to put its internal<br>
state through a one-way function, and an optional Encrypt capability<br>
to optimize the sequence: Squeeze Key / encrypt / Absorb Ciphertext.<br>
<br>
<br>
Example SHOs<br>
-------------<br>
We could build a SHO from an existing hash function in different ways,<br>
depending on:<br>
<br>
 * Is the function already an XOF?  If not, we have to concatenate<br>
outputs based on a counter.  We'll do this with HASH(HASH(input) ||<br>
counter), where the counter is a varint.  This also prevents against<br>
length-extension.<br>
<br>
 * Is the internal function used to process each block (e.g. the<br>
compression function or permutation; call it "f") a one-way function?<br>
If not, we need to zeroize some of the state (e.g. the permutation's<br>
"rate") so the block-processing function (e.g. Keccak permutation)<br>
can't be inverted.<br>
<br>
<br>
SHA3 (not xof, not owf):<br>
  Absorb(data) : update(data)<br>
  Ratchet()    : update(pad_to_block); f(); zeroize()<br>
  Squeeze(len) : h = finalize(); return HASH(h || 0)  ||  HASH(h || 1) ...<br>
<br>
SHA2 / BLAKE2 (not xof, owf):<br>
  Absorb(data) : update(data)<br>
  Ratchet()    : update(pad_to_block); f()<br>
  Squeeze(len) : h = finalize(); return HASH(h || 0)  ||  HASH(h || 1) ...<br>
<br>
SHAKE (xof, not owf):<br>
  Absorb(data) : update(data)<br>
  Ratchet()    : update(pad_to_block); f(); zeroize()<br>
  Squeeze(len) : return finalize(len)<br>
<br>
BLAKE2X (xof, owf):<br>
  Absorb(data) : update(data)<br>
  Ratchet()    : update(pad_to_block); f();<br>
  Squeeze(len) : finalize(len)<br>
<br>
<br>
We could also implement this with STROBE:<br>
<br>
STROBE:<br>
  Absorb(data) : AD(data, more=true)<br>
  Ratchet()    : RATCHET()<br>
  Squeeze(len) : PRF(len)<br>
  Encrypt(data) : ENC(data), PRF(16)<br>
  Decrypt(data) : DEC(data), PRF(16)<br>
<br>
<br>
Trevor<br>
_______________________________________________<br>
Noise mailing list<br>
<a href="mailto:Noise@moderncrypto.org" target="_blank">Noise@moderncrypto.org</a><br>
<a href="https://moderncrypto.org/mailman/listinfo/noise" rel="noreferrer" target="_blank">https://moderncrypto.org/mailman/listinfo/noise</a><br>
</blockquote></div>