Re: [hash2] Question about cryptographic guarantees of hash_append_unordered_range

From: Matt Borland (matt_at_[hidden])
Date: 2024-12-09 13:48:28

> > But I wonder if this preserves the cryptographic quality of original hash.
> 

> 

> It doesn't, even if you preserve the length of the hash. There are two
> attack approaches here, depending on the size of the sets you can work
> with.
> 

> On the low-data side, you can turn collision or second-preimage
> finding into a lattice problem. Suppose you have some set whose
> intermediate hashes are [a=13816517845079277968,
> b=2675547450723878905, c=18133324598626471763,
> d=10200581252073748329]. Build the lattice spanned by the rows
> 

> [K2^64, 0, 0, 0, 0]
> [Ka, 1, 0, 0, 0]
> [Kb, 0, 1, 0, 0]
> [Kc, 0, 0, 1, 0]
> [Kd, 0, 0, 0, 1]
> 

> where K is a constant large enough to force the first coordinate of
> vectors to have more weight and sum to 0. Short vectors of this
> lattice will have the form [0, x, y, z, w], which means that xa + yb
> + zc + wd = 0 (mod 2^64), or in other words the set [a,b,c,d] and
> the set [[a](x+1), [b](y+1), [c](z+1], [d]*(w+1)] have the same
> hash.
> 

> In the above case we can use K=2^32 and use LLL to obtain the vector
> [0, 2870, 27951, 8550, 46911] and thus a second-preimage for the above
> hash. Shorter second-preimages are possible by increasing the
> dimension. In particular, for 64-bit hashes it is possible to find
> lattice vectors containing coefficients only in {-1,0,1},
> corresponding to removals and additions of single elements from the
> original set, at dimension ~48.
> 

> 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
> 

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