Need for secure hash function for a bloom filter

Question

I'm creating a bloom filter.

The purpose of bloom filters is to tell the enquirer whether a value is either definitely not in the set, or is possibly in the set.

The only attack vector I can think of is:

An attacker has two versions of the bloom filter, the first version containing a set of values and the second version containing that set plus one additional value.

Could the attacker get any information about the newly added value from the (up to 20) hash-derived bits that are set in the second version and clear in the first version?

Are there other attack vectors?

Is there any benefit to using a cryptographically secure hash function when calculating (20) hashes of the value, which are used to set bits in the bloom filter?

In particular, with a non-cryptographic hash function, does prefixing the value with the byte values 0-19, before hashing, to create the 20 hashes, create any form of weakness?

Answer 1

Are there other attack vectors?

This will very much depend on the application and how the attacker interacts with the bloom filter.

Let's say you are using a bloom filter to whitelist applications that are allowed to run on your system. The system computes a hash of an application before it is executed and checks it against the bloom filter. If it is in the whitelisted "set", then then application runs. If not, then the application is terminated.

Users can submit applications to the system administrator to have them whitelisted. The administrator does some manual analysis of the application before adding it to the whitelist to ensure it is good software (let's just pretend that the administrator can do this with complete accuracy).

The administrator can set the size of the bloom filter and the number of hashes to get an arbitrarily low false positive rate.

If a non-cryptographic hash function is used, e.g., CRC32. It is not unreasonable to assume that the probabilistic analysis that the administrator uses to determine the parameters of the bloom filter are incorrect.

This could manifest itself in a few particular ways.

1. If the attacker cannot get a benign application of his choosing approved but does know some number of already approved applications, the attacker can likely construct a malicious application that will be guaranteed to be in the set.

2. If the attacker can get a benign application approved, it is not unreasonable to assume that an attacker could come up with 2 programs, 1 benign and 1 malicious that would have the same hash values. By getting the benign one in the set, the malicious one is now also in the set.

Both of these scenarios would be much harder (i.e., computationally infeasible) if a cryptographically secure hash function is used, as opposed to a non-cryptographic function (like CRC32).

Answer 2

Use siphash: this is exactly what is was designed for.

A short output (up to 128 bits with SipHash) is enough to build a bloom filter, and the fact that this hash function is keyed will prevent attackers from causing collisions, hence false positives.

Also, you don't need more than 2 hash functions. See the Less Hashing, Same Performance: Building a Better Bloom Filter paper for reference.

And in order to build these two hash functions, all you need with SipHash is 2 distinct keys.