4
$\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 SHA-256 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 SHA-256 fine?

Improve this question
$\endgroup$
1
  • 5
    $\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.
    Commented Aug 13, 2015 at 13:47

2 Answers 2

Reset to default
7
$\begingroup$

Assuming the hash function is good, and SHA-256 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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Aug 13, 2015 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
    Commented Aug 14, 2015 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
    Commented Aug 14, 2015 at 10:42
0
$\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.)

Improve this answer
$\endgroup$
3
  • 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
    Commented Aug 13, 2015 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
    Commented Aug 14, 2015 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
    Commented Aug 14, 2015 at 11:34

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.