3 ms·

Because you're ignoring their first stated goal (which is immediately prior to the snippet you quote): "we found a lack of published, well-optimized, large-dat

by dgacmu 8y ago

Because you're ignoring their first stated goal (which is immediately prior to the snippet you quote): "we found a lack of published, well-optimized, large-data hash function" Large-data != Inputs the same size of the outputs. Your comment is irrelevant to their goals. (And later in the doc: "Don’t use the Meow hash for tiny inputs. The minimum block size for the Meow hash is 256 bytes")

DoctorOetker 8y ago
I don't really understand the hysteria over larger (multi block) inputs? To construct a multiblock hash in terms of a single block hash, which multiblock hash do you expect to generate more collisions, the one based on a colliding single-block hash or the one based on a non-colliding single block hash? Do the downvoters really believe in some kind of universal contrarian principle? Remember the attack model is "o fortuna" not a cryptographic one. EDIT: perhaps we can settle this in a more constructive fashion: You (or one of the other downvoters) comes up with an 16-bit irreversible hash function, and I come up with a 16-bit reversible one. Then we look how many collisions we each have on all possible 2 block inputs (32 bits). Let's for simplicity agree on the following structure: MultiBlockHash16( < Block1 , Block2 > ){ return SingleBlockHash16(Block1) xor SingleBlockHash16(Block2); } Then to count the collisions over all possible 32 bit inputs, we set an 65536 bit string S to 0, have a counter c iterate through all 32-bit values, and set S[ MultiBlockHash16(c) ] = 1. If it was already one we increase the number of found collisions. Once the superstition is gone you'll agree that it is a useful concept since it means you can focus on the other desirable aspects of your hash function...
dgacmu 8y ago
Also, to the GP whose posts are getting downvoted to the point of being flagged, in case it's helpful in the future: (1) The idea of using a bijection as a building block of hashing is not new, and it's not new to the creators of MeowHash. You point out that there exists a function from 512 bits to 512 bits that's guaranteed to be unique. Another such function that also has good avalanche properties and is hard to determine the original input from if you don't know the key: The AES mixing function. MeowHash is based, in fact, on transforming individual input blocks with a single round of AES, and then merging streams of AES-mixed blocks. The AES part is straightforward -- but provides much better practical hash properties than your proposal (for example, I can use the low-order 128 or 64 bits of the output of MeowHash with the same general collision behavior). The merging step is more important from the perspective of collision-freedom, and you omit that fairly critical part. (2) The contribution of meowhash is its _speed_ and good hashing behavior. It's a very elegant use of highly-optimized on-CPU AES mixing (a feature used by previous hash functions), with a nice block size and stream mixing design that lets it keep a lot of blocks in flight for high throughput. (Meta) You're engaged in a pattern that HN readers generally respond poorly to: Get downvoted -> Complain about downvotes in a way that implies the downvoters are idiots -> get downvoted -> double down. It's pretty easy to rephrase your comments in a way that doesn't have that tone of "you're all idiots for not seeing the connection here".
- DoctorOetker 8y ago
  1) I don't claim the construction is new or novel! not only is it used in the discrete domain but also in the continuous domain: see the RevNet, Glow etc flow based neural networks. The construction is also very reminiscent of reversible quantum circuits... I don't deny the importance of the choice of merging function, but that does not negate the importance of the choice of single block hashing function. The weakest choice will determine the collision performance... Perhaps a better choice for the challenge hash merging would be: return SingleBlock16(SingleBlock16(Block1) xor Block2); In the toy 16 bit example I chose simple xor of hashes not because it is the best choice, but in order to provide a simple implementation for a challenge. Can I assume you hereby submit as your irreversible single-block hash function the lowest 16 bits of MeowHash? 2) sure, I never criticized MeowHash for its speed or elegance in hardware utilization. I am just used to see proposals accompanied with proofs or analysis. Perhaps MeowHash does in fact use a reversible hash for single blocks, but then why does it not state this? There are so many proposals for hashes, and if every enduser needs to check and verify if some properties he expects are met can't read this from the proposal description, then clearly people are not succeeding in communicating requirements and solutions... (Meta) I don't believe idiots exist, I only believe acts of idiocy exist. Downvoting without replying is an act of idiocy.
  - pvg 8y ago
    Downvoting without replying is an act of idiocy. It's perfectly fine on HN. Going on about downvoting is not.
    - DoctorOetker 8y ago
      don't you sometimes think you'd want a platform where the users are in control of the platform rules? of course we'd all be held to the standards to which we hold others...

by dgacmu 8y ago

DoctorOetker 8y ago

I don't really understand the hysteria over larger (multi block) inputs? To construct a multiblock hash in terms of a single block hash, which multiblock hash do you expect to generate more collisions, the one based on a colliding single-block hash or the one based on a non-colliding single block hash? Do the downvoters really believe in some kind of universal contrarian principle? Remember the attack model is "o fortuna" not a cryptographic one. EDIT: perhaps we can settle this in a more constructive fashion: You (or one of the other downvoters) comes up with an 16-bit irreversible hash function, and I come up with a 16-bit reversible one. Then we look how many collisions we each have on all possible 2 block inputs (32 bits). Let's for simplicity agree on the following structure: MultiBlockHash16( < Block1 , Block2 > ){ return SingleBlockHash16(Block1) xor SingleBlockHash16(Block2); } Then to count the collisions over all possible 32 bit inputs, we set an 65536 bit string S to 0, have a counter c iterate through all 32-bit values, and set S[ MultiBlockHash16(c) ] = 1. If it was already one we increase the number of found collisions. Once the superstition is gone you'll agree that it is a useful concept since it means you can focus on the other desirable aspects of your hash function...

dgacmu 8y ago

Also, to the GP whose posts are getting downvoted to the point of being flagged, in case it's helpful in the future: (1) The idea of using a bijection as a building block of hashing is not new, and it's not new to the creators of MeowHash. You point out that there exists a function from 512 bits to 512 bits that's guaranteed to be unique. Another such function that also has good avalanche properties and is hard to determine the original input from if you don't know the key: The AES mixing function. MeowHash is based, in fact, on transforming individual input blocks with a single round of AES, and then merging streams of AES-mixed blocks. The AES part is straightforward -- but provides much better practical hash properties than your proposal (for example, I can use the low-order 128 or 64 bits of the output of MeowHash with the same general collision behavior). The merging step is more important from the perspective of collision-freedom, and you omit that fairly critical part. (2) The contribution of meowhash is its _speed_ and good hashing behavior. It's a very elegant use of highly-optimized on-CPU AES mixing (a feature used by previous hash functions), with a nice block size and stream mixing design that lets it keep a lot of blocks in flight for high throughput. (Meta) You're engaged in a pattern that HN readers generally respond poorly to: Get downvoted -> Complain about downvotes in a way that implies the downvoters are idiots -> get downvoted -> double down. It's pretty easy to rephrase your comments in a way that doesn't have that tone of "you're all idiots for not seeing the connection here".

DoctorOetker 8y ago
1) I don't claim the construction is new or novel! not only is it used in the discrete domain but also in the continuous domain: see the RevNet, Glow etc flow based neural networks. The construction is also very reminiscent of reversible quantum circuits... I don't deny the importance of the choice of merging function, but that does not negate the importance of the choice of single block hashing function. The weakest choice will determine the collision performance... Perhaps a better choice for the challenge hash merging would be: return SingleBlock16(SingleBlock16(Block1) xor Block2); In the toy 16 bit example I chose simple xor of hashes not because it is the best choice, but in order to provide a simple implementation for a challenge. Can I assume you hereby submit as your irreversible single-block hash function the lowest 16 bits of MeowHash? 2) sure, I never criticized MeowHash for its speed or elegance in hardware utilization. I am just used to see proposals accompanied with proofs or analysis. Perhaps MeowHash does in fact use a reversible hash for single blocks, but then why does it not state this? There are so many proposals for hashes, and if every enduser needs to check and verify if some properties he expects are met can't read this from the proposal description, then clearly people are not succeeding in communicating requirements and solutions... (Meta) I don't believe idiots exist, I only believe acts of idiocy exist. Downvoting without replying is an act of idiocy.
- pvg 8y ago
  Downvoting without replying is an act of idiocy. It's perfectly fine on HN. Going on about downvoting is not.
  - DoctorOetker 8y ago
    don't you sometimes think you'd want a platform where the users are in control of the platform rules? of course we'd all be held to the standards to which we hold others...