Re: [hash2] Question about cryptographic guarantees of hash_append_unordered_range

From: Peter Dimov (pdimov_at_[hidden])
Date: 2024-12-09 14:23:35

Matt Borland wrote:
...
> > Note that while finding shortest vectors in a lattice is a very hard
> > problem as the dimension grows, here we don't really have to find
> > exceedingly short vectors; they must instead have either -1 (removal)
> > or positive coefficients. For collision-finding, where we control both
> > inputs, we can start with many repetitions of the same element to make
> > the problem easier and allow reasonably small negative coefficients as
> > well. See also [2, Appendix B].
> >
> 
> > For larger sets, the generalized birthday attacks from Wagner [1,
> > Section 4] also should apply here with minimal modifications, and
> > reduces the security of an n-bit sum to O(2^{2sqrt(n)}).
> >
> 
> > As far as I can tell the only successful multiset hashes either
> > require enormous moduli or use elliptic curves.
> >
> 
> > [1] https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf
> > [2] https://arxiv.org/pdf/1601.06502

Thanks Samuel, very informative.

> This is the correct answer. See also section 5.1 of NIST SP 800-107[1].
> 
> Matt
> 
> [1] https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-107r1.pdf

I'm not sure why hash truncation applies here; what Samuel is saying is
that this scheme for multiset hashing is insecure even if the original hash
is not truncated.

A 256 bit hash, for instance, would only provide (at most) 32 bit security.

For 64 bit security one would need a 1024 bit source hash, which seems
like an overkill to me.