Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I'm building a storage system for JSON documents where they are looked up on a 128 bit key. These JSON documents have a timestamp within them, but apart from that are user-entered data. These JSON documents can have within them private information, so I want to avoid any issues where two documents have the same hash and the wrong one is served.
Should I use MD5, which I know is vulnerable to collision attacks, or go for one of the SHA functions and use the first 128 bits?
The two proposals in the question have their advantages and disadvantages.
Using MD5
There are three major types of attacks to worry about.
MD5 is broken with respect to collision resistance. So, what could an attacker do if you use MD5. They could submit two documents that they created which has the same hash value. Since the attacker would have to create both documents, no private information will be leaked. To learn private information, they'd have to break #1.
MD5's preimage resistance is academically broken. It has not been broken, however, in a practical sense.
Truncated SHA
Since NIST has a truncated mode for SHA-512/256 and SHA-512/224. This should give some credibility to the idea. The link talks about some potential attacks, but all are purely academic at this point.
Now, they do suggest using a unique IV for each truncated length. This is to fix "Issue #1" on slide 7. This issue is very specialized and will not matter for your application as you will always be using the same size output. That said, if you have the ability to modify the IV, I would do it. Modifying the IV could cause problems with interoperability and might break things any time you update software, so you'll have to weigh the options.
The near-collisions is also purely academic as we cannot efficiently find near collisions for say SHA-256 (or 512). This is pointed out on slide 15.
The main disadvantage of truncated SHA is that there are no reduction proofs to the original hash function. Basically this means that the truncated version could be less resistant to preimage attacks, but no known preimage attacks exist on truncated versions.
Xor SHA512 (from comments)
This method seems better than using MD5, but worse than using truncated SHA. Let's look at an example (for this I'm going to split the digest at the byte level to keep it simple and use a short output).
Say I'm looking for a preimage attack and am given a digest of 01001010 00100111. The XOR would be 01101101. If I can find a near collision that looks like 00101010 01000111, the XOR is the same. Thus, this construction is also vulnerable to near-collisions, granted this is more of an academic attack.
Since this is also vulnerabile to near-collisions, and since NIST uses Truncated SHA, I'd go with that instead.
This doesn't sound like a cryptography problem. I think you could use Fnv1 and get the same dangerous construction. Hashes of any kind do not work for row identity.
Collision resistance does not mean collisions don't occur. It means that it is computationally difficult to determine an input (of which there are many) that creates a desired output. It's a misleading term.
Consider your 128 bit hash. If the documents are larger than 16 bytes long, then there will be at least two possible collisions. Is that negligible?
The documents are essentially random input. You can get a collision in the first two docs, or a collision after a billion. Depending on your implementation you'll either fail to insert the second doc, or worse, overwrite the first one. What if these docs were editable? The ID would change with every edit. I guess they would have to be immutable for this to work.
I recommend using a different method to generate your identity key. If you need to make the key secure, then use some other method, perhaps cryptography, to secure access. There are many good ways to do that, but that's a different question than this one.
I hope this helps.
Is that negligible? I think it is. The probabilities for an accidental collision are still so low even with huge numbers of documents - as I said above, to the order of $10^{-15}$ with trillions of documents. Which, according to Wikipedia, is the unavoidable error rate in writing data to hard drives, and, more to the point, is unlikely to ever be noticed in my application. And the data is immutable, which solves the other problem.
$\endgroup$