Generating collisions

leventov commented

2016-02-15 04:40:54 -06:00

(Migrated from github.com)

For e. g. testing purposes I need to generate different sequences, whose XXH64 hash codes collide.

I've found this thread and applied (rather blindly) the same algorithm to XXH64, so I got

0xBA79078168D4BAF * 14029467366897019727 = 1 (mod 2^64)
-7046029288634856825 * 2^31 = 0xC2F5E54380000000 (mod 2^64)
0x9C90005B80000000 * -4417276706812531889 = -0xC2F5E54380000000 (mod 2^64)

Add 0xBA79078168D4BAF to the 64-bit value at position P (in the little-endian order)
Add 0x9C90005B80000000 to the value at P + 32.

But it doesn't work (the hash codes are different).

For e. g. testing purposes I need to generate different sequences, whose XXH64 hash codes collide. I've found [this thread](http://crypto.stackexchange.com/q/6408/8646) and applied (rather blindly) the same algorithm to XXH64, so I got ``` 0xBA79078168D4BAF * 14029467366897019727 = 1 (mod 2^64) -7046029288634856825 * 2^31 = 0xC2F5E54380000000 (mod 2^64) 0x9C90005B80000000 * -4417276706812531889 = -0xC2F5E54380000000 (mod 2^64) ``` 1. Add `0xBA79078168D4BAF` to the 64-bit value at position `P` (in the little-endian order) 2. Add `0x9C90005B80000000` to the value at `P + 32`. But it doesn't work (the hash codes are different).

Cyan4973 commented

2016-02-15 04:46:43 -06:00

(Migrated from github.com)

Hi Roman

The thread you found explain how to create a collision with xxh32.
For xxh64, similar reasoning may apply, but it nonetheless needs to be studied thoroughly. There could be a single minor difference, but it will make the solution different.

Hi Roman The thread you found explain how to create a collision with xxh32. For xxh64, similar reasoning may apply, but it nonetheless needs to be studied thoroughly. There could be a single minor difference, but it will make the solution different.

leventov commented

2016-02-15 04:50:05 -06:00

(Migrated from github.com)

Yes I see that it is for xxh32, so I applied the same reasoning with xxh64's constants (P1, P2) and multiplied offsets by 2 (16 -> 32).

Cyan4973 commented

2016-02-15 05:03:36 -06:00

(Migrated from github.com)

I see you adapted the constants to xxh64.
But since it doesn't work, it could be either :

a calculation error
another difference, which does not allow to blindly apply the same method.

I don't see where the difference could be, since both xxh32 & xxh64 internal loops are very similar,

so maybe a calculation error ?

I see you adapted the constants to xxh64. But since it doesn't work, it could be either : - a calculation error - another difference, which does not allow to blindly apply the same method. I don't see where the difference could be, since both xxh32 & xxh64 internal loops are very similar, so maybe a calculation error ?

Cyan4973 commented

2016-02-15 05:34:55 -06:00

(Migrated from github.com)

Note that I'm currently finding the same constants as you, so constants error looks less likely.

Next in the list are the test conditions.
I guess you already checked them, but just in case :

Constant 1 at position P, constant 2 at position P+32
- Ensure that P is a multiple of 8
- Each constant must be added using little convention
Segments must be full :
- Ensure that there are at least 32 more bytes of input after position P+32

Note that I'm currently finding the same constants as you, so constants error looks less likely. Next in the list are the test conditions. I guess you already checked them, but just in case : - Constant 1 at position P, constant 2 at position P+32 - Ensure that P is a multiple of 8 - Each constant must be added using little convention - Segments must be full : - Ensure that there are _at least_ 32 more bytes of input after position P+32

leventov commented

2016-02-15 05:41:14 -06:00

(Migrated from github.com)

No, I did not obey additional conditions you listed, but now with them, it works. Thank you!

BTW it would be useful to document these collision generation procedures in the repo.

No, I did not obey additional conditions you listed, but now with them, it works. Thank you! BTW it would be useful to document these collision generation procedures in the repo.

chmike commented

2018-08-18 05:35:43 -05:00

(Migrated from github.com)

I also need short byte sequences that collide with XXH64 for testing purpose. Could we have two or three samples ? My use case of to use xxHash for a map (index). Unfortunately, @leventov did not provide his results. The algorithm he used is unclear.

leventov commented

2018-08-18 08:54:18 -05:00

(Migrated from github.com)

@chmike here is the specific collision-generating code: https://github.com/OpenHFT/Zero-Allocation-Hashing/blob/master/src/test/java/net/openhft/hashing/XxHashCollisionTest.java

chmike commented

2018-08-18 09:15:31 -05:00

(Migrated from github.com)

I found out by testing. Here is the explanation with the missing information.
To generate two shortest byte sequence yielding the same XXH64 code here is the algorithm:

create two identical byte sequences s1 and s2 of 64 bytes. The content can be anything
let x be the uint64 obtained from the first 8 bytes of s2 in little endian order.
add 0x0BA79078168D4BAF to x
store back x in little endian order in the 8 first byte of s2
let y be the uint64 obtained from the 8 bytes starting at offset 32 in little endian order
add 0x9C90005B80000000 to y
store back y in little endian order in the 8 bytes of s2 starting at offset 32

The XXH64 hash of s1 and s2 will have the same value.

Here is an example to check your algorithm:

When s1 is a sequence of 64 zero bytes, and after executing the 7 steps above, the 8 first byte of s2 must have the value 0xAF, 0x4B, 0x8D, 0x16, 0x78, 0x90, 0xA7, 0x0B, and the 8 bytes at offset 32 must have the value 0x00, 0x00, 0x00, 0x80, 0x5B, 0x00, 0x90, 0x9C. The hash of s1 and s2 will be 2700762989836380697.

This was tested with github.com/cespare/xxhash, a Go version of XXH64.

I found out by testing. Here is the explanation with the missing information. To generate two shortest byte sequence yielding the same XXH64 code here is the algorithm: 1. create two identical byte sequences s1 and s2 of 64 bytes. The content can be anything 2. let x be the uint64 obtained from the first 8 bytes of s2 in little endian order. 3. add 0x0BA79078168D4BAF to x 4. store back x in little endian order in the 8 first byte of s2 5. let y be the uint64 obtained from the 8 bytes starting at offset 32 in little endian order 6. add 0x9C90005B80000000 to y 7. store back y in little endian order in the 8 bytes of s2 starting at offset 32 The XXH64 hash of s1 and s2 will have the same value. Here is an example to check your algorithm: When s1 is a sequence of 64 zero bytes, and after executing the 7 steps above, the 8 first byte of s2 must have the value `0xAF, 0x4B, 0x8D, 0x16, 0x78, 0x90, 0xA7, 0x0B`, and the 8 bytes at offset 32 must have the value `0x00, 0x00, 0x00, 0x80, 0x5B, 0x00, 0x90, 0x9C`. The hash of s1 and s2 will be 2700762989836380697. This was tested with `github.com/cespare/xxhash`, a Go version of XXH64.

👍 4

chmike commented

2018-08-18 10:49:54 -05:00

(Migrated from github.com)

Thank you very much @leventov . Your code was helpfull. With it I discovered that one can multiply the magical constants by an integer to get other collisions. Thank you very much for your impressive initial work and the code.

ThomasWaldmann commented

2024-08-16 16:18:22 -05:00

(Migrated from github.com)

Pythonic, easier to digest version of what @chmike said:

>>> hex1 = b'00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
>>> hex2 = b'af4b8d167890a70b000000000000000000000000000000000000000000000000000000805b00909c000000000000000000000000000000000000000000000000'
>>> xxh64(unhexlify(hex1)) == xxh64(unhexlify(hex2))
True

Pythonic, easier to digest version of what @chmike said: ``` >>> hex1 = b'00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000' >>> hex2 = b'af4b8d167890a70b000000000000000000000000000000000000000000000000000000805b00909c000000000000000000000000000000000000000000000000' >>> xxh64(unhexlify(hex1)) == xxh64(unhexlify(hex2)) True ```

Rows
Columns

Generating collisions #54