3
$\begingroup$

I have a NoSQL key-value database. I want to insert couple million of records to it.

For the key generation, I'm, using a prefix (something like data-one-) and then concat the SHA256 hash of something unique to the value stored. So the end key might look like

data-one-0000fdb60e164cf0bf07cef647354d26ed17c9492ca4bbf4114878325871fa1d

The problem is that the key is somewhat large and it will have impact of the DB performance. I want to chop off some of the hash to get a 64-bit string (so, 8 chars). So I'd chop the above key to

data-one-0000fdb6

But will it leave enough entropy for the remaining key? The DB will get large, and I don't want collisions, obviously. Will another hash be more suitable for this use, or is trimming SHA256 fine?

$\endgroup$
  • 4
    $\begingroup$ Note that there are only 32 bits of data in 8 chars of hex, not 64. If you can't store raw binary, use base64 instead of hex to pack more bits into strings. $\endgroup$ – Z.T. Aug 13 '15 at 13:47
7
$\begingroup$

Assuming the hash function is good, and SHA256 is widely believed to be so, the probability of no collisions in $k$ samples into a range of size $n$ (e.g., obtained by selecting a subset of characters) is upper bounded by $exp(-k^2/2n).$

For you, say $k=2^{21}=2,097,152$ (couple million) and $n=2^{64}$ means that your probability of no collision is roughly

$$exp(-2^{42}/2^{65})=exp(-2^{-21})\approx 1-1.2\times 10^{-7}.$$

If you had 8 times more inputs (16 million plus) this would become

$$ exp(-2^{48}/2^{65})=exp(-2^{-17})\approx 1-7.6\times 10^{-6}$$

so probability of collision would be more than one in a million.

$\endgroup$
  • 2
    $\begingroup$ "More than one in a million" is probably really bad — especially because this number will grow very quickly as the size of data grows. $\endgroup$ – Stephen Touset Aug 13 '15 at 22:04
  • $\begingroup$ @StephenTouset I'd say this means that 1 database in 1M databases is likely to have 1 collision which isn't all that great but still acceptable. $\endgroup$ – SEJPM Aug 14 '15 at 8:01
  • 2
    $\begingroup$ @SEJPM, one in a million is definitely not negligible. Whether it's still acceptable depends on what happens in case of collisions. Note that if the records change, a database may go through multiple keys per item even if it stays at ~1M items. $\endgroup$ – otus Aug 14 '15 at 10:42
1
$\begingroup$

When you start chopping off bits of a SHA-256 hash, you obtain a NoSHA-256 :) hash that has none of the security properties of the original hash. I assume, however, that this is not really important in the context of your database.

You can compute the probability to have a collision using the birthday paradox.

If you only want 64 bits, you may prefer to directly use a 64bit hash like SipHash.


Update:

The SHA specification indeed allows truncating the hashes as described here. However, this is not a property of hash functions in general. (And I personally still do not believe this is a good idea.)

$\endgroup$
  • 1
    $\begingroup$ Only taking some bits of the output is actually quite common and doesn't reduce security. See for example SHA-256/224 aka SHA-224. It's basically what the OP suggests but with a few more bits left. $\endgroup$ – SEJPM Aug 13 '15 at 11:27
  • 1
    $\begingroup$ The only reason to prefer SipHash over truncated SHA2 is performance. SipHash isn't even designed to be collision resistant. $\endgroup$ – CodesInChaos Aug 14 '15 at 10:33
  • $\begingroup$ @CodesInChaos: Yes, performance it the reason you might want to use SipHash. It was explicitly designed to be used in hash tables. It even offers protection against attacks as the hashes are randomized based on a secret seed. So I think for this application SipHash could be a good choice. As 64 bits is not very much anyway, and since further the hashes do not only depend on the function but also on the data, I would just try SHA and SipHash and then decide. $\endgroup$ – Chris Aug 14 '15 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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