5 ms·

A little confused. I thought a hash algorithm was designed to make every bit of the output significant. Meaning that there is a massive difference between the i

A little confused. I thought a hash algorithm was designed to make every bit of the output significant. Meaning that there is a massive difference between the inputs of two hashes that differ by one character. In that case it is conceivable that pownd input could collide with non-pownd input especially if checking only a subset of the characters in the output. What I'm saying is I had always thought the point of hashes was to always compare them in their entirety not as subsets of the output characters. This tools seems to suggest (so a crypto novice) that is not a concern. How would users feel that their exceptional password might collide with a bloom filter to a pownd password?

andrewla 8y ago
The usual way to do this is to treat the bloom filter as a cache that can have false positives. So instead of querying haveibeenpwned for each attempted password from the user, you only query if the bloom filter says that the password was found. If the bloom filter says that the password was not found, then that means it is definitively not found in the upstream.
- w8rbt 8y ago
  Exactly. More people should read the original Bloom Filter paper. It covers this. Bloom (1970): "In application areas where error-free performance is a necessity, these new methods are not applicable." (p. 422) https://dl.acm.org/citation.cfm?doid=362686.362692 https://dl.acm.org/citation.cfm?doid=362686.362692
deleted 8y ago
[deleted]
notimetorelax 8y ago
I guess the logic here was as follows: It's not good to send clear text user password to yet another system -> send it hashed But full hash might still be vulnerable to the rainbow table attack -> let's use only a part of the hash, AND, reject full hashes. In summary, I believe, they tried to avoid creating more ways in which user passwords could be leaked.
gknoy 8y ago
The bloom filter will tell you whether _the hash of your password_ is in the set. It doesn't matter whether your _password_ matches a pwned one, it only matters whether your password has the same hash as one that is pwned. This tool expands on that by simplifying the test such that it gets more false positives, but still has no false negatives. Imagine that password hashes are six characters, and `abcdef` is the only pwned password we know about. A smaller version of this tool would reject your password if it hashes to anything that starts with `abc` (such as `abc000`, `abcdee`, `abcdef`, etc). With this toy example, we can see that this is deliberately pessimistic -- it only is a "your password might be pwned" indicator. It's like throwing out anything in your fridge that is past its expiration date, even if you don't know whether it's actually spoiled.
- lightbyte 8y ago
  >Imagine that password hashes are six characters, and `abcdef` is the only pwned password we know about. A smaller version of this tool would reject your password if it hashes to anything that starts with `abc` (such as `abc000`, `abcdee`, `abcdef`, etc). Doesn't that not work very well at all though? If these "abcXXX" strings are hashes, than just because they share a prefix doesn't mean the unhashed password are even remotely similar. "good-password-123-dog-xxx..." could hash to "abcdeg" and "password" could be the thing that hashed to "abcdef".
  - sbarker 8y ago
    Collisions in modern, properly implemented algorithms are rare. http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/ http://everydayinternetstuff.com/2015/04/hash-collision-prob... https://www.google.com/amp/s/www.theregister.co.uk/AMP/2017/02/23/google_first_sha1_collision/ https://www.google.com/amp/s/www.theregister.co.uk/AMP/2017/...
    - lightbyte 8y ago
      Collisions for the entire hash are rare, but this is just a prefix of the hash. I imagine it is significantly more common for a collision in the prefix.

andrewla 8y ago

The usual way to do this is to treat the bloom filter as a cache that can have false positives. So instead of querying haveibeenpwned for each attempted password from the user, you only query if the bloom filter says that the password was found. If the bloom filter says that the password was not found, then that means it is definitively not found in the upstream.

w8rbt 8y ago
Exactly. More people should read the original Bloom Filter paper. It covers this. Bloom (1970): "In application areas where error-free performance is a necessity, these new methods are not applicable." (p. 422) https://dl.acm.org/citation.cfm?doid=362686.362692 https://dl.acm.org/citation.cfm?doid=362686.362692

deleted 8y ago

[deleted]

notimetorelax 8y ago

I guess the logic here was as follows: It's not good to send clear text user password to yet another system -> send it hashed But full hash might still be vulnerable to the rainbow table attack -> let's use only a part of the hash, AND, reject full hashes. In summary, I believe, they tried to avoid creating more ways in which user passwords could be leaked.

gknoy 8y ago

The bloom filter will tell you whether _the hash of your password_ is in the set. It doesn't matter whether your _password_ matches a pwned one, it only matters whether your password has the same hash as one that is pwned. This tool expands on that by simplifying the test such that it gets more false positives, but still has no false negatives. Imagine that password hashes are six characters, and `abcdef` is the only pwned password we know about. A smaller version of this tool would reject your password if it hashes to anything that starts with `abc` (such as `abc000`, `abcdee`, `abcdef`, etc). With this toy example, we can see that this is deliberately pessimistic -- it only is a "your password might be pwned" indicator. It's like throwing out anything in your fridge that is past its expiration date, even if you don't know whether it's actually spoiled.

lightbyte 8y ago
>Imagine that password hashes are six characters, and `abcdef` is the only pwned password we know about. A smaller version of this tool would reject your password if it hashes to anything that starts with `abc` (such as `abc000`, `abcdee`, `abcdef`, etc). Doesn't that not work very well at all though? If these "abcXXX" strings are hashes, than just because they share a prefix doesn't mean the unhashed password are even remotely similar. "good-password-123-dog-xxx..." could hash to "abcdeg" and "password" could be the thing that hashed to "abcdef".
- sbarker 8y ago
  Collisions in modern, properly implemented algorithms are rare. http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/ http://everydayinternetstuff.com/2015/04/hash-collision-prob... https://www.google.com/amp/s/www.theregister.co.uk/AMP/2017/02/23/google_first_sha1_collision/ https://www.google.com/amp/s/www.theregister.co.uk/AMP/2017/...
  - lightbyte 8y ago
    Collisions for the entire hash are rare, but this is just a prefix of the hash. I imagine it is significantly more common for a collision in the prefix.