nisse@lysator.liu.se (Niels Möller) writes:
Simon Josefsson simon@josefsson.org writes:
I'd like to understand better the properties of Salsa. As I see it, we have a complicated non-linear, but easily invertible, permutation on blocks of 64 bytes (or 512 bits). Call this function P(X). Then we construct a hash function
F(X) = X xor P(X)
There is no XOR in the Salsa20 core?
Sorry, the final operation is addition (applied independently to 32 bit pieces), not xor. But structure is the same, P(X) represents the QROUND loop, where each step is invertible, and then at the end we add together the output of the QROUNDs and the original input. Collisions are introduced in the final addition, in the sense that we have
P(x) == P(y) if and only if x = y
but F(x) = F(y) is possible for x != y. A collision means that
P(x) xor x == P(y) xor y
which can be rearrange, since P is invertible, as
x = P^{-1}(x xor y xor P(y)
Examples of such colliding pairs seem non-trivial to find (difficulty increasing wth the number of rounds).
You write that the function is not collision resistant. I'd like to know in which way it fails (ideally with either a simple argument, or a reference).
Try for example:
salsa20_core (8, dst, H("00000000000000000000000000000000" "00000000000000000000000000000000" "00000000000000000000000000000000" "00000000000000000000000000000000")); print_hex(64, dst);
salsa20_core (8, dst, H("00000080000000800000008000000080" "00000080000000800000008000000080" "00000080000000800000008000000080" "00000080000000800000008000000080")); print_hex(64, dst);
both will print the all-zero string, thus illustrating a collision. In fact, Salsa20core(x) = Salsa20core(x + c) for c = "0000000800000008...".
See also:
https://groups.google.com/forum/?fromgroups=#!msg/sci.crypt/AkQnSoO40BA/o4eG... http://cr.yp.to/snuffle/reoncore-20080224.pdf
/Simon