Re: Re-rolled Salsa20 function

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 09/27/05 

Date: Mon, 26 Sep 2005 22:14:07 +0000 (UTC)

D. J. Bernstein wrote:
> For example, it seems difficult to find collisions in the 64-byte string
> Salsa20(m0,c) ^ Salsa20(m1,c^1), where m0, m1 are 48-byte message blocks
> and c is a 16-byte constant. [....]
> The final
> 64-byte output can be fed through Salsa20 again and truncated to 32
> bytes, producing a 256-bit hash with one Salsa20 invocation for each 32
> message bytes.

I'll note one can find collisions in this hash function in approximately
2^87 time and space by using the generalized birthday attack [1]. In such
an attack, one searches for values m0,m1,m0',m1' such that
  Salsa20(m0,c) ^ Salsa20(m1,c^1) ^ Salsa20(m0',c) ^ Salsa20(m1',c^1) = 0.
which can be done in something like 2^{256/3} operations.

Such an attack is clearly impractical today, but one might hope for better
security when using a 256-bit hash.

[1] David Wagner, "A Generalized Birthday Problem", CRYPTO 2002.
http://www.cs.berkeley.edu/~daw/papers/genbday.html

Relevant Pages

  • Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)
    ... > The problem with a hashed state table is that hash tables are very ... > an attack totally blow out the D$ and TLB. ... an attacker could manufacture enough collisions to push the hash table ... Couldn't that attack be frustrated by a more sophisticated hash function ...
    (Firewall-Wizards)
  • Re: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)
    ... >> The problem with a hashed state table is that hash tables are very ... >> an attack totally blow out the D$ and TLB. ... > an attacker could manufacture enough collisions to push the hash table ... > Couldn't that attack be frustrated by a more sophisticated hash function ...
    (Firewall-Wizards)
  • Re: Hash Function problem
    ... entry is a 200 characters length string). ... I want as few collisions as possible. ... If its a good hash function, it needs to output to at least about 52 ... as the bits in the quantity of your entries in order to make the ...
    (comp.programming)
  • Re: Cryptographic Hash function
    ... always produces a fixed length string as output. ... mean that the output string will always be longer than the ... The hash function generally does not care about the length ... So yes, collisions are bound to be a mathematical possibility, ...
    (sci.crypt)
  • Re: Hash Function problem
    ... entry is a 200 characters length string). ... I want as few collisions as possible. ... Assume that the hash function does a good job of spreading the bits to a 64-bit binary value, so that the chance of any two entries colliding is 2^-64. ...
    (comp.programming)
Loading