[noise] Stateful Hash Object Proposal

[Trevor Perrin]

On Wed, Dec 19, 2018 at 4:03 AM Peter Schwabe <peter at cryptojedi.org> wrote:
>
> Trevor Perrin <trevp at trevp.net> wrote:
> > 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).
>
> But this is something that can be solved differently for different hash
> functions inside the implementation of the hash object (where, in my
> opinion, it should be solved).
[...]
> I think that for every implementation of the SHO you want to have
> support for a domain-separation (or customization) string. If internally
> this string is simply absorbed without padding, that's fine, but in the
> calling code it's still clear that it's a domain-separation string and
> whoever is using the SHO does not need to care about how exactly the
> internals work for different hash functions.

I agree every SHO should support a customization label, and my
previous proposal for this wasn't great.

Let me sketch a different concrete design for SHO/SHA256, with and
without a customization label:

SHO(c: non-empty customization label)
  - SHA256(SHA256(zeroblock || uint16(len(c)) || c || zeropadding ||
input) || uint64(counter))

SHO(no customization label):
  - SHA256(SHA256(zeroblock || uint16(0) ||  input) || uint64(counter))

Explanation:
 (1) The nested SHA256 and zeroblock are for indifferentiability of
H^2 construction
 (2) The 2-byte length field allows for customization labels of max 2^16-1 bytes
 (3) If customization label is non-empty than we add "zeropadding" to
the next hash block so that the preceding values can be precalculated
into a fixed IV.
 (4) If customization label is empty than we DON'T add zeropadding.
 (5) The counter is incremented to produce XOF output.

Points 3 and 4 allow protocol designers to choose between the (A) and
(B) approaches to domain-separation (A = process the customization
label in a full block to allow precaculation, B = just prepend some
bytes to input to minimize the amount of data hashed).


> > > 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().
>
> I understand the first reason, but not so much the second one. The SHO
> can easily keep track of how many more bytes can be absorbed before it
> has to ratchet; that's quite standard in incremental hash APIs.

I haven't been clear enough what Ratchet() does and why it would be
used.  Let me explain more, and see if that clarifies the reason to
expose it to the caller:

Ratchet() would do this:
 (1) if some input has been Absorb()'d but not yet processed via a
compression function (or permutation function for sponges), it would
pad out the current block, then apply the compression function.
 (2) it would apply any other processing to make the current state
noninvertible and minimum-sized (i.e. delete the sponge's rate).

So this accomplishes making the state a 1-way function of its inputs,
if there was sufficient absorbed entropy, and also making the state
minimum-sized.

The caller would use this when it wants to keep a SHO state around for
awhile and wants this state to be small, and to be noninvertible in
case it is compromised.

Only the caller would know when this is required - e.g., after sending
a Noise handshake message the caller would Ratchet(), since it might
wait for the response handshake message for a long time so it would
prefer to store a small and noninvertible SHO state.

But this decision needs to be made by the caller based on application
logic (after each Noise handshake message), rather than after any
fixed number of bytes.

Trevor