[noise] Stateful Hash Object Proposal

[Trevor Perrin]

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?

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

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?

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