Hacker News new | past | comments | ask | show | jobs | submit login
Cryptanalysis of Meow Hash (peter.website)
105 points by luu 88 days ago | hide | past | favorite | 9 comments

The original announcement post of Meow Hash from 2018 at https://mollyrocket.com/meowhash said:

> […] we wanted a fast, non-cryptographic hash for use in change detection and deduplication.


> To our surprise, we found a lack of published, well-optimized, large-data hash functions. Most hash work seems to focus on small input sizes (for things like dictionary lookup) or on cryptographic quality.

and also

> The Meow hash is not designed for cryptography and therefore we make no claims about its security. Assume it is completely insecure.

I found it confusing then that the cryptanalysis of Meow Hash posted here said:

> The creators make a few security claims; we will break them all. In particular, we present three main attacks […]

But then looking at the Meow Hash GitHub repo I see in the README:

> Due to recent discoveries by Peter Schmidt-Nielsen, we have decided to reclassify Meow hash 0.5/calico from level 3 to level 1. This means that we recommend not to use this hash for message authentication codes, or for hash tables in scenarios where collision induced denial-of-service attacks are a concern.

> We have seen no evidence that the hash is unfit for non-adversarial/non-cryptographic purposes, and continue to believe that it is amongst the best in this regard.

> For level 3/MAC capabilities consider migrating to SipHash. Do not migrate to any hash not advertising MAC capabilities as these are almost certainly much weaker than Meow 0.5. If the performance of SipHash is not satisfying, continuing to use Meow 0.5 for hash tables is better than migrating to another fast hash. While Meow 0.5 also continue to provide some useful strength for message authentication codes, we have to stress that we strongly recommend migration in this case.

So I guess at some point the creators of Meow Hash made some claims about Meow Hash being suitable in cryptographic context between the original announcement and now.

Either way, it’s nice to see that stuff like this is being looked after and responded to, and to know about where I may want to use Meow Hash and not.

Yes, the original article is long, but it has some paragraphs where all the claims of the Meow authors are quoted precisely.

They have indeed claimed some cryptographic qualities for it, which have been shown now to be false.

In any case this article is interesting for anyone who enjoys cryptanalysis, because it describes in great detail how to break such a hash function or message authentication code.

Meow has serious weaknesses so breaking it is not a great achievement, but the very clear and well illustrated explanation of all steps is quite valuable.

This reminds me of FEAL, one of the earliest proposals (1987) for a cipher to be used as a replacement for DES.

FEAL was proposed by a Japanese company, but it was immediately broken. It was revised a few times, but all revisions were also broken easily.

While FEAL sucked as a real cipher, it was great as an example cipher for teaching cryptanalysis.

Meow belongs to the same class, it is easy to break, which makes it good for demonstrating how to do it.

"cryptographically secure" is not necessarily a binary, it depends on the context, and which attributes we are considering. There is no singular "security context".

Meow hash never claimed to be cryptographically secure in the general case, but they did make claims about certain specific security properties (which the article discusses).

It's addressed in the second section of the article, with the header "Meow hash’s cryptographic claims"

> > To our surprise, we found a lack of published, well-optimized, large-data hash functions. Most hash work seems to focus on small input sizes (for things like dictionary lookup) or on cryptographic quality.

I do still find this to be the case. I recently had to come up with a hash I could use for quickly IDing medium-sized data chunks (hundreds of MBs to small numbers of GB), with no need for cryptographic-level security. Best I could find after a surprisingly uninformative search was murmur3. I'm still not confident in my selection.

for everyone who doesn't think highly of Casey Muratori (or at least the way he conducts himself online), the author of Meow Hash, he took the criticism quite graciously:



all of this is very interesting reading for someone like me who doesn't know very much about cryptography beyond the surface level!

Casey and his gang are quite... harsh. That's their group vibe. And, it's understandable that it rubs strangers on the internet the wrong way. But, underneath that, they really do want to help. And, more importantly, they sit up and go to unreasonable lengths to actually do stuff to help.

Case in point, Casey has had 638 (and counting) 1-3 hour long live coding sessions where he is interactively helping mostly young folks be inspired and learn how to code https://www.youtube.com/c/MollyRocket/videos

It's easy to be nice when many eyes are on you.

Man I remember this project. I was super interested in it but the maintainers are really full of themselves and incredibly rude - some of the more unusual and unpleasant interactions I've had on GitHub in ~10 years.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact