I want to store document hashes in a smart contract as a prove of a document (eg pdf contract - could be large, dozones of MB) related to a blockchain transaction.

Is murmur3 128 hash functions a good choice for this?

murmur3 is not a cryptographic hash function, but it as difficult as with cryptographic functions to construct a document with same function which will make sense.

  • "It as difficult as with cryptographic functions to construct a document with same function which will make sense." That's not how hash functions work. Even an insecure 1024 bit hash or one million bit hash is still insecure. The idea behind the statement "I don't know how, so no one can" is always wrong. – Future Security Oct 27 at 21:05
up vote 7 down vote accepted

Actually, it's even worse than what Otus suggested; it's trivial to find a second-preimage; that is, given a message, it is easy to find a second message that hashes to the same value. In fact, you can make the second preimage start with an arbitrary text, and so this is a practical (rather than just an academic) attack.

It's actually quite straight-forward; the state update function for MurMur3-128 is:

h1 ^= mixK1(k1)
h1 <<<= 27;
h1 += h2;
h1 = 5*h1 + constant_1;
h2 ^= mixK2(k2);
h2 <<<= 31;
h2 += h1;
h2 = 5*h2 + constant_2;

where h1, h2 are the hash state, k1, k2 are 128 bits from the current part of the message, and mixK1, mixK2 are invertible functions.

What we do is process the arbitrary preliminary text (which we're assume is a multiple of 16 bytes in length), this will result in some state h1, h2.

Now, what we do is find some 16 byte block k1, k2 that converts this state into a state that is obtained during the processing of the original message; once we have done that, we can append the rest of the original message, and that will result in the same hash as the original message.

Finding such a k1, k2 is quite straight-forward; we just work backwards through the above logic. We start with the h1, h2 being the target values, and compute what the previous state is. When we hit the h1 ^= mixK1(k1) and h2 ^= mixK2(k2) lines, those are (in the backwards direction) the last time we'll update h1 and h2, and so we just set mixK1(k1) and mixK2(k2) to be the values that'll give us the state after processing our chosen prefix.

Since mixK1 and mixK2 are invertible, that gives us K1 and K2, which are the 128 bit values we're looking for.

Note that this is somewhat different from the analysis by Jean-Phillip Aumasson, as he is actually tackling a harder problem. He assumed a secret start state (and was able to find collisions); I'm assuming a known state state (and able to find second preimages)

  • Thank you! That's a great explanation. Could you recommend a hash function which I can use for my use-case? How about bcrypt or Argon2? The salt could be stored in a DB. – Robert Zaremba Oct 27 at 12:41
  • @RobertZaremba: how about either SHA-2 or SHA-3? The point about bcrypt and Argon2 is that they're deliberately designed to be expensive to compute; you don't need that... – poncho Oct 27 at 13:13
  • I was thinking that adding a salt could be a good idea. And there is also blake2, which is faster on the software layer and has good reviews, what do you think? Is 256-length is enough or 512 is preferred now? – Robert Zaremba Oct 27 at 13:47
  • 1
    @RobertZaremba actually a salt is a terrible idea, it allows an attacker a huge degree of freedom in message forgery – Richie Frame Oct 28 at 5:21

No, MurMur3 is not a good choice for proofs, it is vulnerable to at least collision attacks: http://asfws12.files.wordpress.com/2012/11/asfws2012-jean_philippe_aumasson-martin_bosslet-hash_flooding_dos_reloaded.pdf

You should use a cryptographic hash if you care about its strength against anyone acting maliciously.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.