[noise] Stateful Hash Object Proposal

[Samuel Neves]

On Wed, Nov 28, 2018 at 7:23 AM Trevor Perrin <trevp at trevp.net> wrote:
>
> On Mon, Nov 26, 2018 at 3:45 PM Samuel Neves <samuel.c.p.neves at gmail.com> wrote:
> > >
> > > Length-extension attacks are a good point. It's probably not too hard to
> > > prove, but is there a proof that your construction is secure for secret
> > > input as a PRG?
> >
> > I imagine that Kasuda's H^2-MAC proof [1] would be easy to modify to
> > accomplish this. Dodis et al. [2] have pointed out some minor issues
> > with the H^2 structure under unkeyed settings, which I think would be
> > fixed if the input is padded with a 0-block beforehand, as done in the
> > HMAC-but-not-really-HMAC of [3, §3.5].
>
> Good references, thanks!  I suppose Dodis's points are worth
> considering and "indifferentiability" is good to have.  Hopefully
> padding with a zero-block, per HMAC-but-not-really-HMAC from ([1],
> more complete paper) would get us there?
>

It seems like it would. H(H(m)) is not completely broken, but its
indifferentiability scales as (qp)^2/2^n, where q and p are queries to
the RO/simulator instead of something like (q + p)^2/2^n you'd expect
from a usual indifferentiable hash.

>
> Incorporating that plus replacing varints with simpler uint64 would
> give us candidate constructions like below.

Replacing varint with uint64 seems like a good idea regardless of anything else.

>
> Note that this proposal runs SHA3 and BLAKE2 through the same
> nested-hashed plus zero-block thing as SHA2.  Is that silly - because
> they don't have length-extension problems - or still worth doing
> because it's simpler, and you could use the more optimized BLAKE2X or
> SHAKE if you wanted?

BLAKE2X is essentially this scheme already, except it acts as H(pad(0)
|| h) ... by changing the IV of each call. In BLAKE2's case, I suppose
you can do as below. It's not silly, but it's a bit suboptimal, since
you can change the IV directly. The simplicity of the overall spec
might well be worth it.

Best,
Samuel Neves

>
> SHA3 (not xof, not owf):
>   Init()       : init(zero_block)
>   Absorb(data) : update(data)
>   Ratchet()    : update(pad_to_block); f(); zeroize_rate()
>   Squeeze(len) : h = finalize(); return HASH(h || uint64(0))  ||
> HASH(h || uint64(1)) ...
>
> SHA2 / BLAKE2 (not xof, owf):
>   Init()       : init(zero_block)
>   Absorb(data) : update(data)
>   Ratchet()    : update(pad_to_block); f()
>   Squeeze(len) : h = finalize(); return HASH(h || uint64(0))  ||
> HASH(h || uint64(1)) ...
>
> SHAKE (xof, not owf):
>   Absorb(data) : update(data)
>   Ratchet()    : update(pad_to_block); f(); zeroize_rate()
>   Squeeze(len) : return finalize(len)
>
> BLAKE2X (xof, owf):
>   Absorb(data) : update(data)
>   Ratchet()    : update(pad_to_block); f();
>   Squeeze(len) : finalize(len)
>
> Trevor
>
> [1] https://cs.nyu.edu/~dodis/ps/merkle.pdf