Re: Salsa20 hashing

xmath <xmath.news@xxxxxxxxx> wrote:
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).

There are 2^384 outputs, so there are about 2^767 pairs of outputs, out
of which one would expect about 2^767/2^512 = 2^255 colliding pairs.
Finding those colliding pairs does seem difficult, thanks to the
diagonal constants; but the function doesn't compress, so there's no
apparent application of this difficulty.

To summarize: Collision-freeness and collision-resistance are useless
concepts for expansion functions such as Salsa20. Collision-freeness is
too strong to be satisfied, and collision-resistance is too weak to have
any helpful consequences.

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

You should apply a final Salsa20 to the 512-bit output to eliminate
extension attacks, to allow safe truncation, etc.

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

The second-order attack applies no matter what F is. Wagner

* writes down 2^172 choices of F(a);
* sorts by the bottom 172 bits, finding about 2^171 pairs a,a' with
F(a) - F(a') mod 2^172 = 0;
* sorts the list of F(a) - F(a') for those pairs;
* writes down 2^172 choices of b;
* sorts by the bottom 172 bits, finding about 2^171 pairs b,b' with
b' - b mod 2^172 = 0;
* sorts the list of b' - b for those pairs; and
* merges the lists of differences, finding a few collisions
F(a) - F(a') = b' - b, i.e., F(a) + b = F(a') + b'.

The number of bit operations here is on the scale of 2^172, certainly
far smaller than 2^256.

On the other hand, the communication costs here are huge, making the
attack no more cost-effective than a standard parallel collision search.
Furthermore, on an absolute scale, 2^172 is a ludicrous number of bit
operations for the attacker, certainly not something that concerns us.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago
.