1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
  • 3
    $\begingroup$ I think it's worth highlighting that the idea of using nothing more than a Bloom filter to gate access to a resource in this way is an odd one to start with. Bloom filters are normally used to short-circuit more expensive checks—if the filter returns "no" you avoid an expensive operation, but then if it returns "maybe" you have to do the expensive operation to actually confirm whether it's a "yes." $\endgroup$ – Luis Casillas Nov 1 '17 at 18:22
  • 1
    $\begingroup$ @LuisCasillas, agreed. It was the best I could come up with, however. If you have any other ideas, please do post. $\endgroup$ – mikeazo Nov 1 '17 at 18:24
  • 2
    $\begingroup$ The best I can think of is that Bloom filters with weak hash functions could be vulnerable to denial of service attacks similar to those on hash tables. An attacker would compute false positives for the Bloom filter and submit them to cause it to perform the expensive operation over and over. Although you have to wonder why wouldn't they just query legitimate values, maybe there's a realistic scenario where the ability to perform this attack with novel values enhances it. $\endgroup$ – Luis Casillas Nov 1 '17 at 18:47
1
$\begingroup$

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.

$\endgroup$

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.