Xxhash: Can we get the code that produced the Meow Hash collisions?

[cmuratori]

Hi there,

I noticed on the page https://github.com/Cyan4973/xxHash/wiki/Collision-ratio-comparison that it says there were unexpected collisions found in Meow Hash. We have not been able to find unexpected collisions, so we would love the code that reproduces this, unless these were done with Meow Hash prior to v0.5, in which case we don't need them (only by v0.5 did we hit what we believe is level 3 quality).

- Casey

[easyaspi314]

Well, it may be seed dependent.

The test @Cyan4973 used is a brute force test. While it tests a lot of data, it still can't test everything, and doesn't look for specific collisions, just "random" data.

I can't test on my PC (not nearly enough RAM lol), so I don't know.

I presume it might have something to do with the fact that aesenc(x, aesenc(x, y)) == y, or that mixing cancels things out somewhere.

I don't personally agree with AES for hashing — it is an encryption algorithm which can cancel itself out. Plus, if you don't have AES-NI or NEON crypto, you either SIGILL or have to deal with dog :stuck_out_tongue: slow scalar AES.

[easyaspi314]

Hmm…I do agree with this.

// NOTE(casey): The default seed is now a "nothing-up-our-sleeves" number for good measure.
// You may verify that it is just an encoding of Pi.
static meow_u8 MeowDefaultSeed[128] =
{
        0x32, 0x43, 0xF6, 0xA8, 0x88, 0x5A, 0x30, 0x8D,
        0x31, 0x31, 0x98, 0xA2, 0xE0, 0x37, 0x07, 0x34,
        0x4A, 0x40, 0x93, 0x82, 0x22, 0x99, 0xF3, 0x1D,
        0x00, 0x82, 0xEF, 0xA9, 0x8E, 0xC4, 0xE6, 0xC8,
        0x94, 0x52, 0x82, 0x1E, 0x63, 0x8D, 0x01, 0x37,
        0x7B, 0xE5, 0x46, 0x6C, 0xF3, 0x4E, 0x90, 0xC6,
        0xCC, 0x0A, 0xC2, 0x9B, 0x7C, 0x97, 0xC5, 0x0D,
        0xD3, 0xF8, 0x4D, 0x5B, 0x5B, 0x54, 0x70, 0x91,
        0x79, 0x21, 0x6D, 0x5D, 0x98, 0x97, 0x9F, 0xB1,
        0xBD, 0x13, 0x10, 0xBA, 0x69, 0x8D, 0xFB, 0x5A,
        0xC2, 0xFF, 0xD7, 0x2D, 0xBD, 0x01, 0xAD, 0xFB,
        0x7B, 0x8E, 0x1A, 0xFE, 0xD6, 0xA2, 0x67, 0xE9,
        0x6B, 0xA7, 0xC9, 0x04, 0x5F, 0x12, 0xC7, 0xF9,
        0x92, 0x4A, 0x19, 0x94, 0x7B, 0x39, 0x16, 0xCF,
        0x70, 0x80, 0x1F, 0x2E, 0x28, 0x58, 0xEF, 0xC1,
        0x66, 0x36, 0x92, 0x0D, 0x87, 0x15, 0x74, 0xE6
};

Having kSecret be the digits of pi would be almost too perfect…

[cmuratori]

Regardless of any of this, we just want to verify that the test was done properly, and what the collisions were. If this test was done with Meow Hash v0.4 (which is over a year old at this point), that's a bad thing, since that is a completely different hash construction from v0.5. If it _was_ done with v0.5, we need to see the collisions so we can find out where they're coming from.

- Casey

[cmuratori]

I don't personally agree with AES for hashing — it is an encryption
algorithm which can cancel itself out.

We designed the hash to not have that issue, as you can see from the mixing function (https://github.com/cmuratori/meow_hash/blob/master/meow_hash_x64_aesni.h#L181) and the pattern in which it is called.

- Casey

[easyaspi314]

Sorry, I do have a severe tendency to get off topic.

If you want to test it yourself or at least see how the test works, the test is in tests/collisions.

You need an absurd amount of RAM, processing power, and time to run it, though.

[cmuratori]

Unfortunately that doesn't tell me what Meow Hash was used - I already looked in there to see. I just need someone to tell me what version of our hash you used to do this test, since that information is nowhere to be found on the Wiki supposedly listing collisions found in the hash.

- Casey

[easyaspi314]

We designed the hash to not have that issue, as you can see from the mixing function (https://github.com/cmuratori/meow_hash/blob/master/meow_hash_x64_aesni.h#L181) and the pattern in which it is called.

I think I see now, but that probably should be explained in a comment as it is definitely not obvious (especially with the meaningless register names)

[erthink]

I think that specifying test vectors (and procedures for reproducing them) would solve all such issues.
On the other hand, it is reasonable to expect replacement the hash function name or (at least) the major version number when changes affect test vectors.

[erthink]

Moreover, in the meow hash, I was able to see (too many definitions for me) only two AES-steps for hashing each piece of data. This is not enough (TL;DR | I've explained it before) for full mixing/avalanche and therefore correlation with other simple operations (ADD, XOR) may be more than enough for the level of collisions shown in the tests.

[Cyan4973]

Thanks for notification @cmuratori ,

I will look at the source code that produced this result.
The test was completed some time ago. As each full test costs ~1 day, and requires access to a specific server with enough RAM to complete it, they can't be run "regularly", so these results tend to stick around. Indeed, it could be that a newer version of your hash actually improves on this metric. It would be fair to reflect it in the displayed result.

First step, let's find back the source code that produced that result.

[Cyan4973]

OK, that part wasn't too difficult, thanks to version control.

So an issue is that I don't see any version number in the source code.

So I guess I will have to compare the tested source code with the one in the github repository.

[Cyan4973]

It's clearly different.

To begin with, at repository level, the file names are different.
And looking at the code / algorithm, it looks different too.

So I presume it must be an old version (v0.4?).
I will update the wiki to reflect that,
and plan a new test session to measure the new version.

Sorry for the confusion.

[cmuratori]

Moreover, in the meow hash, I was able to see
(too many definitions for me) only two AES-steps
for hashing each piece of data.

Two things about this.

First, there is only one AES step per ingest, which is what allows Meow to get actual measured speeds up toward the 16 bytes/cycle AES throughput limit on SSE. Obviously one cannot run AES twice on each input before advancing, as that would limit the speed to 8 bytes/cycle regardless of what other operations you performed.

Second, we are well aware of how AES works and specifically designed the ADD/XOR interlacing to prevent attackers who do not know the seed from producing collisions using knowledge of AES. But as with any cryptographic analysis, it is very hard to definitively prove if that design works or not. So if collisions _were_ found in the hash function, it would be very helpful for us to know _what they were_, so that we can at least verify that they were only findable by brute force and not by some kind of shortcut.

So specifically, if this test can produce collisions in Meow v0.5, it would be great if we could get the seed + inputs that produce the collisions. It would help us verify whether or not the function is sound. If these collisions were only in Meow v0.4, that is unimportant (except perhaps that it would be nice if the wiki were corrected).

- Casey

[cmuratori]

So an issue is that I don't see any version number in the source code.

All versions of Meow Hash that we shipped had the version in the source code, at least as far as I recall. For example, in v0.5 it is here:

https://github.com/cmuratori/meow_hash/blob/master/meow_hash_x64_aesni.h#L119

So I presume it must be an old version (v0.4?).

If it is v0.4, then the version number was here:

https://github.com/cmuratori/meow_hash/blob/v0.4/meow_intrinsics.h#L226

It's clearly different.

Good to know. If you do end up running this kind of test on Meow again, if it would be at all possible to get any collisions you find, that would be very helpful for us in verification of the hash function.

Thanks,
- Casey

[Cyan4973]

If it is v0.4, then the version number was here:

Yes, indeed, I missed that line.
So it's definitely v0.4 that was tested : MEOW_HASH_VERSION_NAME "0.4/himalayan".

The wiki is updated.
Now trying to reserve the server for a new test with v0.5.

[cmuratori]

Now trying to reserve the server for a new test with v0.5.

Awesome, looking forward to the results.

Thanks,
- Casey

[Cyan4973]

let me know where I can rent 2-4-8 cores with 256-521-1024 Gb of RAM for same tests (anyway, sharing looks reasonable).

I would love to be useful on this topic.
But in fact, I'm just lucky : I use private internal servers at Facebook to run these tests.
And as one can guess, unfortunately, these beasts are only accessible by internal developers...

[easyaspi314]

A small request, if possible - let me know where I can rent 2-4-8 cores with 256-521-1024 Gb of RAM for same tests (anyway, sharing looks reasonable).

First thinking a random CPU architecture that is just a prototype will take off, now thinking you can rent a server that powerful…

You sure like to dream. :joy:

@Cyan4973, can you also see if you can test HighwayHash and possibly SeaHash?

[easyaspi314]

@easyaspi314, I'm just a private person who has an opinion and a head, but not the extra money for gigabytes of memory needed for a couple of tests.

So am I.

On the other hand, you're right, I shouldn't be begging. Reragds.

That wasn't begging. It was a legitimate question.

I shouldn't be joking as much, as I have the opposite which is a larger problem.

You seem to be pretty optimistic, while I'm pretty cynical.

[Cyan4973]

Tests with the new version v0.5 are completed.
I don't see any issue with this version.
With 300 collisions on 100 G hashes, the low 64-bit do behave as expected by the Birthday Paradox.
I'm going to update the wiki accordingly.

[easyaspi314]

Nice improvements from v0.4, @cmuratori. 👍

[cmuratori]

Tests with the new version v0.5 are completed.
I don't see any issue with this version.
With 300 collisions on 100 G hashes, the low 64-bit do behave as expected by the Birthday Paradox.

That is excellent news. Thanks for taking the time to run the test suite!

- Casey

[cmuratori]

Nice improvements from v0.4, @cmuratori.

My contribution was marginal. @nohatcoder was the one who brought the A game to Meow v0.5.

- Casey