Salsa20 hashing

I've been playing a bit with the thought of building a hash out of
Salsa20, for applications that already use it and don't want another
primitive...

Does anyone see an obvious problem with this particular mode of turning
Salsa20 (or any other one-way function where the input size equals the
output size) into a collision-resistant hash function on arbitrary-size
messages:

Pad and split the message into 64-byte blocks m_1 .. m_k, then:

h_0 = IV
h_1 = Salsa20(h_0 + Salsa20(m_1))
h_2 = Salsa20(h_1 + Salsa20(m_2))
h_3 = Salsa20(h_2 + Salsa20(m_3))
....
h_k = Salsa20(h_{k-1} + Salsa20(m_k))

With h_k as the hash output. (By using the same per-word addition as
Salsa20 uses to add in the original input you can save a temporary
16-word array in the implementation.)

I feel a little uncomfortable about allowing the attacker to fully
control the input to Salsa20, however if the IV is chosen properly then
none of the ways (known to me) in which Salsa20 deviates from a perfect
random function are of any utility.

In comparison, the "obvious" chaining mode (32 message bytes, 32
chaining bytes) only allows the attacker to have precise control over
half the input, but she also only needs to find a collision in half the
output. Because of that, simple chaining obviously allows a collision
to be found in about 2^128 operations, while for the mode above I see
no obvious attack faster than about 2^256 operations.

Performance of the two modes is about the same. On my G4 (PPC 7447A),
around 8 cycles/byte.

Any thoughts?

Also, what about the reduced-round versions, Salsa20/8 and /12 ?

- xmath

.

Relevant Pages

  • Re: Re-rolled Salsa20 function
    ... it's safe to build a compression function in ... Either approach produces a conservative hash ... Applying Salsa20 to each message block in parallel produces ... it seems difficult to find collisions in the 64-byte string ...
    (sci.crypt)
  • Re: Salsa20 hashing
    ... Salsa20 (or any other one-way function where the input size equals the ... output size) into a collision-resistant hash function on arbitrary-size ... With h_k as the hash output. ...
    (sci.crypt)
  • Re: Re-rolled Salsa20 function
    ... This is mentioned in the Salsa20 design document. ... You're confusing Salsa20 with a block cipher. ... 128 bits chosen by the attacker, 256 key bits, and 128 constant bits. ...
    (sci.crypt)