[noise] Stateful Hash Object Proposal

[Trevor Perrin]

On Sat, Dec 8, 2018 at 4:23 AM Peter Schwabe <peter at cryptojedi.org> wrote:
> Trevor Perrin <trevp at trevp.net> wrote:
> > On Sun, Dec 2, 2018 at 9:40 PM Peter Schwabe <peter at cryptojedi.org> wrote:
> > > I think that if you have an incremental hash API, what you're suggesting
> > > is the natural thing to do. In a non-incremental hash API, you have to
> > > do quite some copying around to put the domain separator at the
> > > beginning of the buffer; also it needs additional stack space. That's
> > > why I don't like the concatenation notation too much -- it hides those
> > > costs for moving data around.
> >
> > OK, would you prefer Absorb(separator), then Ratchet()?
>
> I would prefer
>
>   PRF = SHO("P")
>   PRF.Absorb(...)
>   PRF.Sqeeze(...)
>
>   XOF = SHO("X")
>   XOF.Absorb(...)
>   XOF .Sqeeze(...)

OK, that's a nice API.  My concern was that there's two ways to do
domain separation:

 (A) Prepend the separator *without* block padding (minimizes input size).

 (B) Prepend the separator *with* block padding (makes it easier to
store the "IV" after processing the domain-separator).

I think we could support both:

Allow a SHO to be constructed with or without a "customization string"
(which may be zero-length).

The SHO algorithm might have special support for a customization
string (e.g. cSHAKE's customization string or maybe using the
customization string as HKDF salt in an HKDF SHO).  If the SHO does
*not* have special support for a customization string, then just call
Absorb(customization) followed by Ratchet().

This design would NOT guarantee that a customized SHO will be
domain-separated from a non-customized SHO, since the non-customized
object might Absorb an initial input that collides with some
customization string, but I tentatively think that's better than
requiring an extra field be always present just to differentiate the
customized / non-customized cases, since that complicates the simple
use of a non-customized SHO.

This would support the API you prefer, but someone trying to squeeze
things into the fewest hash blocks could also do:

  PRF = SHO()
  PRF.Absorb("P" || ...)
  PRF.Sqeeze(...)

  XOF = SHO()
  XOF.Absorb("X" || ...)
  XOF .Sqeeze(...)


> > For SHAKE, Ratchet() would run the permutation and then zeroize the
> > sponge "rate".   So effectively, the sponge's "capacity" of 32 or 64
> > bytes just becomes a different constant for Kyber's XOF, PRF, G, and
> > H.
>
> > For SHA256, Ratchet() would just zero-pad to the next block boundary
> > and run the compression function, which could also be treated as
> > different IVs for Kyber's XOF, PRF, G, and H.
>
> I wouldn't expose Ratched() as a method on the SHO, but handle
> ratcheting internally.

Ratchet() is useful in a protocol like Noise which is going to use a
single SHO over some period of time, and wants to periodically ratchet
it for forward-secrecy, and perhaps to reduce the amount of state
stored between handling each message (since after Ratchet() the "rate"
would be erased, so doesn't need to be stored).

But Noise also wants to efficiently/incrementally call Absorb(), so we
don't want the cost of ratcheting for each Absorb().

So I think Ratchet() makes sense in the SHO API.  But for your case (a
PQ algorithm at a single point in time), you wouldn't need it.

Trevor