Re: Salsa20 hashing

Scott Contini wrote:
Just a few comments: According to my colleague who knows all this
foundations of cryptographry stuff, there is no known construction
which converts a one-way function into a collision resistant hash function.

I know the underlying function will definitely more than one-wayness.
But Salsa20 with appropriately chosen diagonal constants isn't just
one-way but also collision-resistant (indeed, likely to be
collision-free as it maps 48-byte strings to 64-byte strings). It also
doesn't have any fixed point or other deviations from randomness I'm
aware of. I also probably need that for given w it must be hard to
find m and m' such that H(m) - H(m') = w, which is another thing I
think I'd trust Salsa20 for.

So, my current idea is basically splitting the message m into k =
ceil(len/48) blocks of 48 bytes each (last block zero-padded, len in
bytes < 2^52), and saying:

Hash(m) = IV !+ H(48, m_1) !+ H(96, m_2) !+ ... !+ H(len, m_k)

Here H(len, m_i) is Salsa20 on an input which puts the two-word len
along with two fixed fixed words on the diagonal and m_i into the
remaining 12 words, and !+ is an operator which I construct to be
non-commutative and non-associative: a !+ b = F(a) + b for some
function F. This to avoid anything like the attack in David Wagner's
paper "A Generalized Birthday Problem".

As long as F is bijective and doesn't harmfully interact with H this is
obviously no worse than simply summing, which means some analysis done
on such schemes can be reused. This leaves the question, does anyone
know of collision attacks on the scheme above other than the one in
that paper?

Another question is how to choose F such that:
1. it's as simple as possible
2. it's bijective (to avoid losing information in the left operand)
3. it prevents (2k)-sum collision attacks
4. it doesn't harmfully interact with H like the choice F=H does

While Salsa20/8 without final round addition is simple and probably
does a great job at avoiding any "nice" properties in !+ there is still
some worry on point 4 which makes me feel I should probably construct F
in a way that's totally unrelated to Salsa20.

Any suggestions?

(I realize that the result would still be "heuristic", but ultimately
all current collision-resistant functions are)

- xmath

.