collisions due to overlapping loads

svpv commented

2019-09-27 17:13:15 -05:00

(Migrated from github.com)

There are massive collisions on ELF symbols (which are functions names found in binaries and shared libraries).

05c3bcfaf53bd8d1816832569ec6482f        imdi_k488_gentab
05c3bcfaf53bd8d1816832569ec6482f        imdi_k48_gentab
075c7212a88df56ff9390d0bb4098e23        elput_init
075c7212a88df56ff9390d0bb4098e23        elput_input_init

I pushed the full list along with the data set (elfsym0u.zst, about 9 million strings).

There are massive collisions on ELF symbols (which are functions names found in binaries and shared libraries). ``` 05c3bcfaf53bd8d1816832569ec6482f imdi_k488_gentab 05c3bcfaf53bd8d1816832569ec6482f imdi_k48_gentab 075c7212a88df56ff9390d0bb4098e23 elput_init 075c7212a88df56ff9390d0bb4098e23 elput_input_init ``` I pushed the [full list](https://raw.githubusercontent.com/svpv/xxh3-collisions/master/collisions.list) along with the [data set](https://github.com/svpv/xxh3-collisions) (`elfsym0u.zst`, about 9 million strings).

👍 1

Cyan4973 commented

2019-09-27 18:49:12 -05:00

(Migrated from github.com)

Thanks for these tests and feedback @svpv .
It seems to happen in the 9-16 input range, which gives a clear target to analyze.

Thanks for these tests and feedback @svpv . It seems to happen in the 9-16 input range, which gives a clear target to analyze.

Cyan4973 commented

2019-09-27 18:59:37 -05:00

(Migrated from github.com)

Come on ....
There is a clear mistake in this module : it doesn't count the contribution of input length anywhere in the formula. This is clearly an oversight. I'll fix it, I expect it to solve the reported collision issue.

An associated issue is: how could this mistake manage to pass the tests ? I must have another look at the test suite, it should catch these cases.

Come on .... There is a clear mistake in this module : it doesn't count the contribution of input length anywhere in the formula. This is clearly an oversight. I'll fix it, I expect it to solve the reported collision issue. An associated issue is: how could this mistake manage to pass the tests ? I must have another look at the test suite, it should catch these cases.

easyaspi314 commented

2019-09-27 20:02:37 -05:00

(Migrated from github.com)

Ouch.

Yup, that's a blooper.

static XXH128_hash_t XXH3_len_9to16_128b(BYTE const *XXH_RESTRICT input,
                                      size_t len,
                                      BYTE const *XXH_RESTRICT secret,
                                      XXH64_hash_t seed)
{
    U128 acc = 
        (U128)(XXH_readLE64(secret) + seed)
      | ((U128)(XXH_readLE64(secret + 8) - seed) << 64);
    acc ^=
        (XXH_readLE64(input)
       |((U128)XXH_readLE64(input + len - 8) << 64));
    acc ^= (acc >> 64);
    acc *= PRIME64_1;
    acc ^= (acc >> 96);
    acc *= PRIME64_2;
    {
        XXH128_hash_t ret;
        ret.low64 = XXH3_avalanche((U64)acc);
        ret.high64 = XXH3_avalanche((U64)(acc >> 64));
        return ret;
    }
}

Ouch. Yup, that's a blooper. ```c static XXH128_hash_t XXH3_len_9to16_128b(BYTE const *XXH_RESTRICT input, size_t len, BYTE const *XXH_RESTRICT secret, XXH64_hash_t seed) { U128 acc = (U128)(XXH_readLE64(secret) + seed) | ((U128)(XXH_readLE64(secret + 8) - seed) << 64); acc ^= (XXH_readLE64(input) |((U128)XXH_readLE64(input + len - 8) << 64)); acc ^= (acc >> 64); acc *= PRIME64_1; acc ^= (acc >> 96); acc *= PRIME64_2; { XXH128_hash_t ret; ret.low64 = XXH3_avalanche((U64)acc); ret.high64 = XXH3_avalanche((U64)(acc >> 64)); return ret; } } ```

Cyan4973 commented

2019-09-28 19:15:23 -05:00

(Migrated from github.com)

Fix ongoing in #260.

I still need to work on these test tools.
But running these tests can be long, and I might need a quick release next week for internal usages.

Fix ongoing in #260. I still need to work on these test tools. But running these tests can be long, and I might need a quick release next week for internal usages.

Cyan4973 commented

2019-09-28 21:55:47 -05:00

(Migrated from github.com)

So, SMHasher is unable to produce this sequence of inputs,
and my own collision analyzer only works on same-size samples,
but the issue is about collision between samples of different sizes.

So I guess I'm going to create a new tool to catch those ones...

So, `SMHasher` is unable to produce this sequence of inputs, and my own collision analyzer only works on same-size samples, but the issue is about collision between samples of different sizes. So I guess I'm going to create a new tool to catch those ones...

Cyan4973 commented

2019-09-29 15:22:07 -05:00

(Migrated from github.com)

It's more difficult than I anticipated
to modify a generic pattern generator
to output similar-yet-unique patterns like the ones reported in this issue.
It's a pity, as a generic generator could have been merged into the collision analyzer tool.

Another method is to create a dedicated pattern generator,
specifically written to generate patterns similar to those reported by @svpv.
Probably simpler and faster ...

It's more difficult than I anticipated to modify a generic pattern generator to output similar-yet-unique patterns like the ones reported in this issue. It's a pity, as a generic generator could have been merged into the collision analyzer tool. Another method is to create a dedicated pattern generator, specifically written to generate patterns similar to those reported by @svpv. Probably simpler and faster ...

Rows
Columns

collisions due to overlapping loads #259