Re: Salsa20 hashing

(since my message hasn't shown up hours after posting it, I'm assuming
it got lost somehow so I'm posting one with roughly the same content...
sorry if it ends up being a dup)


Scott Contini wrote:
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.

Salsa20 isn't just one-way but also collision-resistant. When using it
as 48-to-64-byte hash with appropriately chosen diagonal constants I
also know of no fixed point or other deviation from a random function.


Here is the most up-to-date version of my idea:

Let m be an l-byte message (l < 2^52) and n = ceil(l/48), split it into
n 48-byte blocks, m_1 .. m_n, with the last one zero-padded if
necessary. Let l_i = i * 48 for i < n and l_n = l.

Define H(l_i, m_i) as Salsa20 applied to an input whose diagonal
consists of two appropriately chosen constant words and two words
encoding l_i, and whose remaining 12 words are filled by m_i.

Define the left-assoc operator a !+ b as F(a) + b for some
appropriately chosen bijective function F (discussed later), where +
adds all 16 words elementwise (mod 2^32).

Now: Hash(m) = IV !+ H(l_1, m_1) !+ H(l_2, m_2) !+ .. !+ H(l_n, m_n)


The first thing to notice is that if H were a random oracle, no choice
of F would obviously result in a *worse* hash than picking the identity
function for F. This means that the only "harmful" choices for F are
those which badly interact with the specific choice of H. Choosing F
to be Salsa20 (ignoring that it's not bijective) is such an example.

Now using the identity function for F makes this similar to AdHash, and
opens it up to the attack in David Wagner's "A Generalized Birthday
Problem". The attack in that paper doesn't work if !+ is sufficiently
inconvenient, so that's the open issue... What's a good choice of F
such that:

1. F is bijective (to not discard information from !+'s left argument)
2. F is simple and convenient to implement
3. generalized birthday attacks are thwarted
4. F doesn't harmfully interact with H

I'm pretty sure that my most recent pick of using Salsa20/8 without
final addition as F satisfies the first three criteria, however there's
still some worry left that it might interact with H. Perhaps I should
pick F to be something quite different from Salsa20, though preferably
still working on the matrix in a similar way, to avoid messing up the
pipeline in vectorized implementations.

Any suggestions on that?

- xmath

.