256-bit variants

[DonaldTsang]

It would be great if MeowHash has a 25-bit variants for those who wants both accuracy and speed in a non-cryptographic setting (as fast or faster than FNV-1a)

[mmozeiko]

Meow hash is heavily based on AES operation which has 128-bit block size. Having 256-bit output will require significant changes to algorithm, it almost will be completely different hash (unless doing some trivial change, like hashing input two times with different "seed" and concatenating two 128-bit outputs).

[DonaldTsang]

@mmozeiko the thought would be to have a 256-bit hash that has similar speeds to Meow128, and I don't know if a simple "seed" concatenation would do for randomness. Maybe have an intermediate step to mix between the two 128-bit blocks?

[NoHatCoder]

Mainly 256 bit non-cryptographic hashes don't really do anything. If you are afraid of collisions in 128 bit hashes, by far the most likely reason for a collision is that someone forged a collision, so to get a meaningfully higher security level you need to move to cryptographic hashing. That is why most hash functions don't provide more than 128 bits of output.

[DonaldTsang]

@NoHatCoder mind if I ask, what are the chances of a hash collision, for both the case of 128-bit and 256-bit, if the server has 2^23 files (a small site)? what about 2^28 files (a large media company)?Considering the bit failure rate of an SSD is about 1e-16 to 1e-17 (2^-53 to 2^-57).

[NoHatCoder]

2^-83, 2^-211, 2^-73 and 2^-201, respectively. So you are still far more likely to serve the wrong files because cosmic rays flipped a bit somewhere.

Also for your benchmarking, please note that most of the hash functions you find around the internet are broken in some way, for instance you could have a 128 bit hash that seems fine, but if you swap two blocks of the input there is a 2^-32 chance that it causes a collision, so that flaw will dominate the chance of collisions appearing in the wild. Test suites generally won't find problems like that, since they are slightly too unlikely to be found, and the suite might not test a suitable pattern.

[DonaldTsang]

@NoHatCoder so you took a look at the other issues page? Glad to see people care. So... out of the ones listed there that has 128 and 256-bit hashes, which ones are "the best"? (assuming that I will be using both Intel and AMD CPUs which have different ISAs (AES vs SHA2))

[NoHatCoder]

I have no faith in XXH (all variants), see https://github.com/Cyan4973/xxHash/issues/180

CityHash at least has a seed that does nothing, see http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/ beyond that it is complete mess, not as much designed as just thrown together, combining arbitrary operations with no rhyme or reason.

HighwayHash I have looked at before, probably ok.

The others I don't know.

About ISAs, all modern X86 processors have the AES-NI extension, the is no problem supporting both Intel and AMD processors. The ISA problem for Meow is that there is basically two ways to implement AES and keeping it simple: Transforming the decode to be like the encode, or transforming the encode to be like the decode, neither is inherently better than the other. X86 and ARM made opposite choices, but the way Meow works, it takes extra instructions to make one of the implementations work like the other.

[DonaldTsang]

@NoHatCoder out of all the methods listed, has anyone ever tried to benchmark all these hashes by speed (and non-cryptographic/"common" collision resistance if it is doable)?

[NoHatCoder]

Lots of people have made comparing lists of assorted hash functions, including vain attempts at benchmarking quality.

The problem is that it takes a lot of work to dig through the internals of a hash function in order to properly gauge the quality. And all the thank you ever get is to have an internet argument with the creator, and possibly some randos, over whether or not what you found "counts".

[DonaldTsang]

Any good or bad examples of such a situation where people bicker over which code base to use? Also are there any organizations that can be "neutral" (at least in the speed front)?

[NoHatCoder]

The speed part is the easy part, while you can surely mess it up, lots of people are able to do it reasonably well. It seems that most people with the capabilities to be authoritative in the field choose to spend their time on crypto instead, makes it a bit of a wild west.

For bickering, see for instance: https://github.com/vinkla/hashids/issues/48

The library claims to obscure sequential ids so that they can't be guessed. The code is a mixed up substitution cipher, generally a worthless construct, but it falls completely apart when the input is highly guessable. The author doesn't seem to think that there is anything wrong with publishing a library that is basically pointless without the security claims that it is unable to make.

[DonaldTsang]

I would sincerely hope, in the near future, that a speed test be conducted for all 128 and 256 bit hashes for the sake of comparing performance, even before evaluating randomness/security. Regarding randomness, what about establishing a standard test suite like https://github.com/aappleby/smhasher/ before initiating a public benchmark?

[NoHatCoder]

You only get so far with a test suite. Many hashes have been designed using smhasher, meaning that the author have started out by making a broken hash, run it through smhasher, found some brokenness that way, fixed it, and repeated until smhasher didn't report any problems. This basically means that the code is still full of problems, but only those too subtle for smhasher to find remain. Proper vetting must be done analytically, and that is almost impossible to automate.