Cyan
Reputation
Top tag
Next privilege 250 Rep.
 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.