148 reputation
6
bio website
location France
age 41
visits member for 1 year, 8 months
seen Jul 29 at 13:59

Interested in compression algorithms


Sep
24
awarded  Autobiographer
Mar
12
awarded  Popular Question
Feb
23
revised From hash to Cryptographic hash
added 753 characters in body
Feb
23
revised From hash to Cryptographic hash
added 753 characters in body
Feb
23
comment From hash to Cryptographic hash
I've edited the question to explained the proposed solution. Reading your comment, it seems you also found better solutions, which work with a better probability than 50%. I would be glad if you could give some hint how they work.
Feb
23
revised From hash to Cryptographic hash
added 360 characters in body
Feb
23
revised From hash to Cryptographic hash
added 235 characters in body
Feb
23
revised From hash to Cryptographic hash
deleted 94 characters in body
Feb
23
revised From hash to Cryptographic hash
added 354 characters in body
Feb
23
revised From hash to Cryptographic hash
added 254 characters in body
Feb
23
awarded  Editor
Feb
23
revised From hash to Cryptographic hash
added 254 characters in body
Feb
23
comment From hash to Cryptographic hash
OK, i think i have a candidate solution for collision, but it's not an easy one, it comes with many restrictions, some of which are not controllable by the attacker. Anyway, here are the candidate modifiers : at position $P$, add $0xBD1C0000$, and then at position $P+4$, add $0x80000000$. I will edit the question to present the associated restrictions (it's not working for any $P$)
Feb
22
awarded  Scholar
Feb
22
accepted From hash to Cryptographic hash
Feb
22
comment From hash to Cryptographic hash
OK, thanks, maybe i've got it now. Let's target $B$ = 0x80000000 ? This way $B$ * Prime1 = $B$. And $B + B$ = 0. In this case, $A$ = $B$ >>13 = 2^18. So the problem is reduced as finding $C$ such as $C$ * Prime2 = $A$ = 2^18.
Feb
22
comment From hash to Cryptographic hash
Yes, sure, in this case a solution would be easy. It would be possible to create a A, and then -A. The problem is, this is not the full line of operations. The full line is : v1 += XXH_LE32(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; Operations 1 alone would match your hypothesis, Operation 2 makes it more complex but i feel it would still be possible to find a solution; but operation 3 (v1 *= PRIME32_1;) seems to scramble everything. I don't see how it could be made "independant of X", which is the whole point.
Feb
21
comment From hash to Cryptographic hash
That looks like an excellent answer. The principles which make xxHash not suitable for MAC usage seem identical to those targeting MurmurHash : mainly, the claim is that it is possible to forge 2 consecutives sequences which will cancel each other, whatever the underlying internal state is, making this operation independant of the secret key. I would feel better, nonetheless, if i could find such consecutive sequences.
Feb
21
awarded  Supporter
Feb
21
comment From hash to Cryptographic hash
Thanks for clarifying, the difference between cryptographic Hash and MAC is much better now.