[email protected] (Niels Möller) writes:
> Simon Josefsson <[email protected]> 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/o4eG96rjkgYJ
http://cr.yp.to/snuffle/reoncore-20080224.pdf
/Simon
_______________________________________________
nettle-bugs mailing list
[email protected]
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
