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?

  • 1
    $\begingroup$ There are truncated versions of SHA-512 (for 224 bit and 256 bit). NIST did define a new IV for those versions. I suppose you could follow the idea behind those versions (csrc.nist.gov/groups/ST/hash/documents/Kelsey_Truncation.pdf) to define a custom length output. $\endgroup$
    – mikeazo
    Commented Mar 19, 2012 at 15:31
  • 1
    $\begingroup$ @Alec: You only solve the problem with the most obvious class of near collisions by xor-ing the four 128 bit parts of a SHA512 hash together. Finding a class of inputs that would result in the same truncated hash using your scheme would be a different problem, but it's not obvious that it would be a significantly harder problem. $\endgroup$ Commented Mar 19, 2012 at 16:36
  • 1
    $\begingroup$ @Alec: you might want to use RIPEMD-128; rmd128.c; rmd128.h. Contrary to MD5, there is no known attack better than brute force. $\endgroup$
    – fgrieu
    Commented Mar 19, 2012 at 17:32
  • 1
    $\begingroup$ @mikeazo: RIPEMD-128 and RIPEMD-160 have been introduced after early signs that MD5 and RIPEMD have weaknesses (but much before actual breaks), in an effort to offer a strong (though not extremely fast) design. I think they have been the subject of significant attention, without result. At one point RIPEMD-160 was formally endorsed by some European crypto authority (DCSSI or/and BSI). $\endgroup$
    – fgrieu
    Commented Mar 20, 2012 at 7:59
  • 2
    $\begingroup$ if you're worried about malicious collisions, I'd consider using larger hashes. Even for perfect hash-functions, brute-force collisions on 128 bit hashes seem possible. Personally I'd go with 256 bit hashes if collision resistance is required. $\endgroup$ Commented Nov 7, 2012 at 10:55

2 Answers 2


The two proposals in the question have their advantages and disadvantages.

Using MD5
There are three major types of attacks to worry about.

  1. Preimage attacks: given $h$ find $m$ such that $H(m)=h$
  2. Second preimage attacks: given $m$ find $m'\neq m$ such that $H(m)=H(m')$
  3. Collision resistance: find any $m$ and $m'$ such that $H(m)=H(m')$

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.

  • $\begingroup$ Thanks very much for your responses Mikeazo. I'm implementing this in PHP, Erlang and possibly Perl as well so I'd like as simple an implementation as possible. Which rules out truncated SHA and leaves Xor'ing SHA512 and @fgrieu's suggestion of RIPEMD-128. Between the two, I feel sure the Xor'ing SHA512 method isn't going to be defeated, whereas a weakness could be discovered in the lesser used and trusted RIPEMD-128. So I'm gonna go for the former. Do you agree? $\endgroup$
    – Max
    Commented Mar 19, 2012 at 18:08
  • $\begingroup$ @Alec, Why not truncated SHA (w/o the custom IV)? That would be pretty simple and at least as good as XORing. I'm not very up to date on the cryptanalysis of RIPEMD, hence my comment to fgrieu. $\endgroup$
    – mikeazo
    Commented Mar 19, 2012 at 18:54
  • $\begingroup$ That was because I thought the truncated SHA you were referencing was more complicated than it was. Now I've reread things I've reached the same conclusion but for different reasons. I can't use a custom IV, which exposes what seems to me a potentially greater weakness than those of the Xor SHA512 solution - people can use standard rainbow tables and lookups to attack my keys to find near-collisions. With the Xor SHA512 method, it requires extra computation and strikes me as infeasible to attack. $\endgroup$
    – Max
    Commented Mar 19, 2012 at 20:44
  • $\begingroup$ @Alec, personally I would prefer something that has at least been analyzed by the crypto community (truncation). That said, I cannot think of any major reason to not do what you suggest. $\endgroup$
    – mikeazo
    Commented Mar 19, 2012 at 20:55
  • $\begingroup$ How has MD5 not been broken in a practical sense? It's already been used to spoof certificates in vulnerable systems using chosen-prefix attacks. $\endgroup$
    – bryc
    Commented Sep 5, 2018 at 14:36

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.

  • 1
    $\begingroup$ Hey Grant, thanks for your response. 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$
    – Max
    Commented Mar 21, 2012 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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