{"action":"created","issue":{"url":"https://api.github.com/repos/aappleby/smhasher/issues/57","repository_url":"https://api.github.com/repos/aappleby/smhasher","labels_url":"https://api.github.com/repos/aappleby/smhasher/issues/57/labels{/name}","comments_url":"https://api.github.com/repos/aappleby/smhasher/issues/57/comments","events_url":"https://api.github.com/repos/aappleby/smhasher/issues/57/events","html_url":"https://github.com/aappleby/smhasher/issues/57","id":311055370,"number":57,"title":"[Flaw/Bug in MurmurHash3_x86_128] Collisions within component hashes for small keys - related to shared seed","user":{"login":"bryc","id":1408749,"avatar_url":"https://avatars1.githubusercontent.com/u/1408749?v=4","gravatar_id":"","url":"https://api.github.com/users/bryc","html_url":"https://github.com/bryc","followers_url":"https://api.github.com/users/bryc/followers","following_url":"https://api.github.com/users/bryc/following{/other_user}","gists_url":"https://api.github.com/users/bryc/gists{/gist_id}","starred_url":"https://api.github.com/users/bryc/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bryc/subscriptions","organizations_url":"https://api.github.com/users/bryc/orgs","repos_url":"https://api.github.com/users/bryc/repos","events_url":"https://api.github.com/users/bryc/events{/privacy}","received_events_url":"https://api.github.com/users/bryc/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2018-04-04T01:39:25Z","updated_at":"2018-04-14T03:56:58Z","closed_at":null,"author_association":"NONE","body":"I noticed something alarming when generating hashes for keys under 16 bytes using the x86_128 MurmurHash3 function that uses 32-bit operations. `h2`, `h3` and `h4` have collisions at a 100% rate. \r\n\r\nThis doesn't affect MurmurHash3_x64_128 but in my case I can't do 64-bit operations.\r\n\r\nLook:\r\n\r\n```\r\nseed = 1, data = {}\r\nh1 = 2294590956, h2 = 1423049145 h3 = 1423049145, h4 = 1423049145\r\nBAD.. h2 == h3 == h4\r\n\r\nseed = 0, data = {0}\r\nh1 = 2294590956, h2 = 1423049145 h3 = 1423049145, h4 = 1423049145\r\nBAD.. h2 == h3 == h4\r\n\r\nseed = 0, data = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}\r\nh1 = 1514173910, h2 = 1798126887, h3 = 3549588527, h4 = 3944909319\r\nOK\r\n\r\nseed = 0, data = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}\r\nh1 = 894685359, h2 = 2425853539, h3 = 2425853539, h4 = 2425853539\r\nBAD.. h2 == h3 == h4\r\n\r\nseed = 253, data = {254,254,254,254,254,254,254,254}\r\nh1 = 3510856102, h2 = 544881857, h3 = 3491786221, h4 = 3491786221\r\nBAD.. h3 == h4\r\n```\r\n\r\nIt seems this happens because h1-h4 is initialized exactly the same. The issue is mitigated by XORing the seed like so:\r\n\r\n```\r\n  uint32_t h1 = seed ^ c1;\r\n  uint32_t h2 = seed ^ c2;\r\n  uint32_t h3 = seed ^ c3;\r\n  uint32_t h4 = seed ^ c4;\r\n```\r\nBut I am not a mathematician, so don't know if that modification compromises the hash quality."},"comment":{"url":"https://api.github.com/repos/aappleby/smhasher/issues/comments/381301259","html_url":"https://github.com/aappleby/smhasher/issues/57#issuecomment-381301259","issue_url":"https://api.github.com/repos/aappleby/smhasher/issues/57","id":381301259,"user":{"login":"bryc","id":1408749,"avatar_url":"https://avatars1.githubusercontent.com/u/1408749?v=4","gravatar_id":"","url":"https://api.github.com/users/bryc","html_url":"https://github.com/bryc","followers_url":"https://api.github.com/users/bryc/followers","following_url":"https://api.github.com/users/bryc/following{/other_user}","gists_url":"https://api.github.com/users/bryc/gists{/gist_id}","starred_url":"https://api.github.com/users/bryc/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bryc/subscriptions","organizations_url":"https://api.github.com/users/bryc/orgs","repos_url":"https://api.github.com/users/bryc/repos","events_url":"https://api.github.com/users/bryc/events{/privacy}","received_events_url":"https://api.github.com/users/bryc/received_events","type":"User","site_admin":false},"created_at":"2018-04-14T03:56:58Z","updated_at":"2018-04-14T03:56:58Z","author_association":"NONE","body":"> If the hash function viewed as pure hash (without cryptographic sense), the quality of the hash dependend on good distribution and cannot be compared using few messages (in addition if they are too short).\r\nAdditionally I don't know why you looking at h1 ... h4 as separate values - they are parts of whole hash, so you should compare it always as one 128-bit large hash-value.\r\n\r\n\r\nI don't need cryptographic hash, just fast and random/well-distributed output. The reason why I look at h1 ... h4 is because they are computed separately and mixed together, then concatenated.\r\n\r\n> <pre>MMH3-128(\"\", seed=1)\r\n> 88c4adec 54d201b9 54d201b9 54d201b9</pre>\r\n\r\nIn that example `54d201b9` is the final result of computations in h2, h3, h4, repeating 3 times in final hash. This pattern is  reproducible on many input that is under 8 and 16 bytes (simply changing seed will show this) - and does not seem well-distributed.  Only once input is more than 16 bytes does this pattern seem to disappear.\r\n\r\nIn MMH3_x64_128, the same input does not have this pattern and is better distributed (possibly due to using two 64-bit words only):\r\n\r\n`MMH3_x64_128(\"\", seed=1)`\r\n`6eff5cb54610abe578f8358351622daa`\r\n\r\nA workaround to fix this only requires h1-h4 to have different start values (using XOR mod in OP):\r\n\r\n<pre>MMH3-128_mod(\"\", seed=1)\r\n385e023f 865a0e29 c8bd436f 0b9dada7</pre>\r\n\r\nThis is no longer compatible with original function output, but for my purposes that is fine as long as it is still good distribution. \r\n\r\nI can only assume this hash function is not intended for <16-bit keys, but it seems like a bug to me, as there is no reason to have patterns in output of a good hash function."}}
{"actor":{"display_login":"bryc"}}