# 128 bit hash with least chance of collision

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?

Cheers,

Alec

-
Is there any reason you are using 128 bits for the key as opposed to a larger bit size for the key? Also, what is your threat model? I.e., are you worried about maliciously created collisions or accidental collisions? –  mikeazo Mar 19 '12 at 15:16
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. –  mikeazo Mar 19 '12 at 15:31
@mikeazo I'm using PostgreSQL's UUID type, which seems the best way to efficiently represent the key. I'm worried about maliciously created collisions because, correct me if I'm wrong, even with trillions of documents hashed, the probability of a collision is still something like $10^{-15}$. –  Alec Mar 19 '12 at 15:49
@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. –  Henrick Hellström Mar 19 '12 at 16:36
@Alec: you might want to use RIPEMD-128; rmd128.c; rmd128.h. Contrary to MD5, there is no known attack better than brute force. –  fgrieu Mar 19 '12 at 17:32

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.

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.

-
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? –  Alec Mar 19 '12 at 18:08
@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. –  mikeazo Mar 19 '12 at 18:54
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. –  Alec Mar 19 '12 at 20:44
@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. –  mikeazo Mar 19 '12 at 20:55
There was a paper (cannot find it anymore) that suggested that truncating a hash would lead to (potential) weaknesses. Just a warning, although I think it was largely accademical. –  owlstead Mar 20 '12 at 23:45

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.

-
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. –  Alec Mar 21 '12 at 1:09