Bloom Filters: Students at Some State University (SSU) select very bad passwords
ID: 3751457 • Letter: B
Question
Bloom Filters: Students at Some State University (SSU) select very bad passwords. The system administrator decided to use a Bloom Filter to prevent students from using the passwords “cat, dog, fish, and bear”. The Bloom Filter uses 3 hash functions (H1, H2, H3) and 10 bits in the hash table. When the hash functions are applied to the prohibited passwords, the results are:
H1(cat) = 8 H2(cat) = 1 H3(cat) = 2
H1(dog) = 1 H2(dog) = 9 H3(dog) = 1
H1(fish) = 2 H2(fish) = 8 H3(fish) = 2
H1(bear) = 2 H2(bear) = 4 H3(bear) = 1
Bit 0
Bit 1
Bit 2
Bit 3
Bit 4
Bit 5
Bit 6
Bit 7
Bit 8
Bit 9
Question 1C: List one value for H3(mouse) of H3(mouse) that would cause the "mouse" to be accepted as a password or explain why no value of H3(mouse) could cause this.
Bit 0
Bit 1
Bit 2
Bit 3
Bit 4
Bit 5
Bit 6
Bit 7
Bit 8
Bit 9
Explanation / Answer
Answer:
Bloom Filter: Bloom filter is a probability-based data structure that is used to confirm whether a given value is member of set or not. A bloom filter is an bit array of given size, say m. Values at positions in array can be set to either 1 or 0. Given a key, we use a set of hash functions H1, H2, H3 etc. to decide positions to set in array. These hash functions take key as argument and returns hashed values. These hashed values indicate positions in array (bloom filter) that will be set to 1.
For example, for the given case, bit positions are shown below:
Issue with Bloom Filter: One major issue with bloom filter is that it can report false positives. For example, for a given key (not in the set), if hash functions return the positions that are already set to 1, then filter will indicate that the key under consideration is in the set, although it is not in the set.
For "mouse", the one value for H3("mouse") that can cause "mouse" to be accepted as a password will be any bit position that is already set to 1. These positions are 1, 2, 4, 8 and 9.
Initial Bit 0 Bit 1 Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 Bit 8 Bit 9 0 0 0 0 0 0 0 0 0 0 H1 H2 H3 Cat 8 1 2 Bit 0 Bit 1 Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 Bit 8 Bit 9 0 1 1 0 0 0 0 0 1 0 H1 H2 H3 dog 1 9 1 Bit 0 Bit 1 Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 Bit 8 Bit 9 0 1 1 0 0 0 0 0 1 1 H1 H2 H3 fish 2 8 2 Bit 0 Bit 1 Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 Bit 8 Bit 9 0 1 1 0 0 0 0 0 1 1 H1 H2 H3 bear 2 4 1 Bit 0 Bit 1 Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 Bit 8 Bit 9 0 1 1 0 1 0 0 0 1 1