1. 48

  2. 6

    I skimmed through, but clearly lots of effort went into this.

    Question: Are the problems discovered with Meow fixable while maintaining speed goals, or is it just fundamentally not cryptographically secure?

    1. 9

      The author seems highly adversarial towards Meow hash at the start of the essay, though the amount of research work that must have gotten into it is worthy of admiration.

      For people that might not know what the initial use Casey wanted fulfilled when he wrote v1. of MeowHash, it was basically to use as a hash-function for building maps of assets in a game engine. I think a long time he has been very vocal about how it will not be suitable to do cryptography, because it was designed for speed, not safety. I guess the subsequent progress in the next versions made them be comfortable with assuming Level 3. I see that currently they have taken it down to Level 1 following this article.

      1. 18

        The author seems highly adversarial towards Meow hash at the start of the essay

        How so?

        The author noted, multiple times, that Meow hash was not advertised as a strong cryptographic hash. I took the author’s tone as polite and collegiate.

        I ask because I often write documents with similar tone and caveats. I don’t want to seem adversarial!

        1. 11

          The article is still held in a professional manner, and backs up the author’s claims with outstanding cryptographic analysis. I symapthise with the author here: The meow hash function claims security where none is to be found. The developers warn that their level 3 classification might be unsound and nobody has proven that it is secure, but they still upheld that claim, which is questionable at best and malicious at worst. It was reclassified after these exploits were made public, but IMO it should never have claimed to be securer without proof.

          I don’t mean to detract from the value of the meow hash function: 50GB/s is an absolutely outstanding hash rate and in situations where cryptographic security isn’t required (such as game asset hasing), and it is certainly one of the fastest out there. Just don’t claim what you haven’t verified yourself.

          1. 10

            I think that, in general, humans should not be boastful about hash functions. We have yet to show that one-way functions even exist; there is a lot of hubris involved in claiming that a hash function is one-way or even slightly hard to invert.

            1. 1

              Have not shown that one way functions exists? This seems… odd. Speaking of which, how is isOdd not a one-way function?

              1. 5

                The Wikipedia article @Corbin linked explains this. It is not, because a one-way function is one where for a given output, it is hard to find any input, it doesn’t have to be the input originally provided.

                1. 1

                  Interesting, cheers. I will let this stew in the ol’ noggin.

            2. 2

              [Meow hash] was designed for speed, not safety

              My understanding is that speed and safety are basically the same thing:

              • Either you want maximum security for given speed constraints,
              • or you want maximum speed for a given security margin.

              Thus, the quality of a symmetric primitive is basically measured by how many rounds it needs to thwart all known attacks (assuming the community made a concerted effort to break it, mind you), and how much time each round takes.

              Now if we can increase the rounds of MeowHash down to the speed of some modern hash like BLAKE2, BLAKE3, or SHA-3, and we notice that it has a similar security margin, then it’s probably pretty good. If however the margin is smaller, or it stays broken even with that many rounds, then it’s just crap…

              …which may be a worthy trade-off anyway if it was never meant to be attacked in the first place of course, especially if the first rounds take little computation.

            3. 1

              Skimming through the article, I get the sense that a career’s-worth of skill and knowledge went into performing that analysis.

              Now, in 2021, could someone let me know what books, articles and/or papers I can read as a cryptography beginner to be able to understand this article, say six months down the line.

              For example, what’s a Level 3 and a Level 1 hash? I need to learn the background which will help me understand concepts like that.

              1. 2

                “Hash Levels” is pretty non-standard terminology I think. The source is this: http://nohatcoder.dk/2019-05-19-1.html. It seems that some cryptographers dislike these categories– the reddit comments for this article have one complaining about the lack of rigor in the level descriptions.

                For learning cryptography, I really, really enjoyed reading Prof. Rosulek’s Joy Of Cryptography: https://web.engr.oregonstate.edu/~rosulekm/crypto/. I think it’s still a work in progress, though.

                1. 1

                  Wow, that looks great, and also links to other good resources. Bookmarked. Thank you!