12 ms·

Blooming Password – A banned password check using a bloom filter

226 points by vuln 8y ago

Buge 8y ago
I'm not sure if 1/1000 is the right tradeoff. You can get 1/100000 for less than double the size. https://hur.st/bloomfilter/?n=500M&p=100000&m=&k= https://hur.st/bloomfilter/?n=500M&p=100000&m=&k=
fenollp 8y ago
Code is at https://github.com/w8rbt/blooming_password https://github.com/w8rbt/blooming_password but is private/404 right now.
- transitivebs 8y ago
  Yeah, I'd love to check out the source.
  - brianm 8y ago
    A different implementation of same idea, if you just want to see how it's been done at least once: https://github.com/brianm/pwned https://github.com/brianm/pwned
    - FRex 8y ago
      Are you aware of the pitfall I've mentioned here?: https://news.ycombinator.com/item?id=17323068 https://news.ycombinator.com/item?id=17323068 Just making the possible passwords be 10 chars and contain chars out of a set of 62 (lowercase + uppercase + digits) gives me 0.05 sensitivity at 0.00000001 (0.000001%) FP rate. Edit: (This is reply to w8rbt below, here since HN has decided I cannot post anymore for next who knows how many hours.) I'm aware of this and wouldn't treat a bloom filter as the final decision maker if there is a hit but many people seem to act like it is intended to be one and bring up its FP rate as low enough, i.e.: 1. This comment and several of its replies: https://news.ycombinator.com/item?id=17322692 https://news.ycombinator.com/item?id=17322692 2. This comment telling me false positives don't matter: https://news.ycombinator.com/item?id=17323438 https://news.ycombinator.com/item?id=17323438 3. Both of the linked bloom filters don't mention that if there is a hit you should check with https://haveibeenpwned.com/ https://haveibeenpwned.com/ API. 4. (Of course, this is HN after all!) my comments pointing this paradox/pitfall/whatever out being at negative point scores. I've literally lowered my score for saying "hey, 1 in 1000 FP isn't actually super accurate and almost sure hit is a good hit". And there are one or two green named users who seem to be criticizing this bloom filter with freshly made accounts, exactly because of this BS.
      - w8rbt 8y ago
        Read the original Bloom Filter paper from 1970. It covers all of this and it's very short. If the test for membership returns 'probably' then you do the more expensive test if you need to know for certain or you don't use one to begin with: Space/Time Trade-offs in Hash Coding with Allowable Errors BURTON H. BLOOM https://dl.acm.org/citation.cfm?doid=362686.362692 https://dl.acm.org/citation.cfm?doid=362686.362692
sirsuki 8y ago
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.
- 8y ago
reiichiroh 8y ago
The Palo Alto NG firewalls can do this although I haven't gotten it working yet.
- kchr 8y ago
  Do what exactly? Check for bad passwords by inspecting traffic...?
  - vuln 8y ago
    Yes, 'Phishing Attack Prevention' https://live.paloaltonetworks.com/t5/Featured-Articles/PAN-OS-8-0-PAN-OS-Phishing-Attack-Prevention/ta-p/129935 https://live.paloaltonetworks.com/t5/Featured-Articles/PAN-O...
    - dustindecker 8y ago
      Intercepting TLS on a device running rebranded CentOS 5 (11 year old distro that stopped getting security updates over a year ago) does not seem like a safe idea.
bloomthrowaway 8y ago
Sorry to say this, but this is actually worse than just truncating the hash. Why? Bloom filters are designed to maintain a reasonable false positive rate while still allowing you to add items extremely quickly (high insertion rate). Since the bad password list is presumably fixed (or almost so) you can do checks faster and with a lower FP rate by just truncating the hashes and prefix sorting the list ahead of time.
- dlhavema 8y ago
  but don't you still have to store/manage the whole 30gb list of hashes? the point of a bloom filter is it can store any arbitrary string in 7-8 BITS depending on how many hash functions you use to test for existence
  - bloomthrowaway 8y ago
    If you use a secure hash on the banned passwords they will be random (as good as arbitrary), then just truncate them to 7-8 bits and sort by prefix, searching them using binary search. It will be more efficient than a Bloom filter because there can be zero empty space between entries. It creates a structure similar to a Bloom filter but with no wasted space (no empty entries) A Bloom filter is great when you need a probabilistic hash table that is fairly efficient and can have records added efficiently. With a fixed list as I described above, the insertion cost is enormous (avg cost of moving 1/2 of the array elements), but the space/speed efficiency reaches the theoretical limit
    - dlhavema 8y ago
      thanks for the clarification, with a fixed list that makes sense.
    - pronoiac 8y ago
      Your math is bogus. 7-8 bits? If there's one entry, that would give false positives of 1/256, or 0.3%. Even given 1k entries would likely hit the vast majority of entries. Or, flipping this: every time you add a password, you check that it hasn't been used before. You can only set 256 passwords, total, before the space of truncated hashes is filled.
Tostino 8y ago
Another option if you're able to do a server side check, is to use a library like nbvcxz (Full disclosure, I wrote it): https://github.com/GoSimpleLLC/nbvcxz https://github.com/GoSimpleLLC/nbvcxz If you have a list of passwords you want to exclude, you can load it into the library, or it comes with it's own list of common passwords from leaked datasets.
- ezekg 8y ago
  Does nbvcxz do anything different than zxcvbn? Just curious on if your implementation does anything different/better. (Might be mentioned in the README, which I just skimmed, so apologies if so.)
  - web007 8y ago
    The very first line of the README: nbvcxz is java library (and standalone console program) which is heavily inspired by the work in zxcvbn. Also it has https://github.com/GoSimpleLLC/nbvcxz#differentiating-features https://github.com/GoSimpleLLC/nbvcxz#differentiating-featur... for its own features, but not necessarily how it compares to zxcvbn.
    - ezekg 8y ago
      I saw that it was heavily inspired by zxcvbn, which is why I asked. Didn't see the differentiating features, so ty for the link.
  - Tostino 8y ago
    Hey there. As said, the readme points out the major differences with zxcvbn. I think the main difference you'd see, is the quality of matches and the scores generated are superior to zxcvbn. I had put a lot of work into fixing some of the algorithms, and adding more than the original to cover all the corner cases zxcvbn didn't support well. For example, I support finding separators within a password with nbvcxz, so passphrase detection is much much better. I also added support for levenshtein distance calculations for dictionary matches. So common misspelling, or slight alterations to a word will be caught, even if they are not included in the dictionary. Also, internationalization support is nice for those who need it.
sandworm101 8y ago
500,000,000 forbidden passwords/hashes? What exactly is the real benefit of excluding those? It only matters if someone steals your list of hashed passwords AND you have hashed them in some deficient way (poor salting etc) so that the hashes may be "reversed" and used. That a password has been used by someone else in the past, for some other reason, and that password is now on some database, does not make that password dangerous. What matters is whether your users are using the same passwords across multiple services, services out of your control. But ATM no tech out there would allow you to test for this. If your system cannot detect someone running 500,000,000 passwords against a single account, you have far bigger problems.
- andrewla 8y ago
  > What matters is whether your users are using the same passwords across multiple services, services out of your control. But ATM no tech out there would allow you to test for this. Checking against a list of known passwords from breaches does accomplish this, albeit with a high false positive rate.
  - sandworm101 8y ago
    Does it? If I have used the same password at a dozen sites, and none of those sites have ever suffered a public breech, then my password isn't in any public database.[1] So you will also have a high false negative rate, something far more dangerous than false positives. I don't think I'm alone in using passwords across multiple sites. Every here lives in that glass house.
    - dsnuh 8y ago
      > and none of those sites have ever suffered a public breech Yet. That you know of. > Every here lives in that glass house. No, some of us use password manager software for exactly this reason - so we don't use the same password across multiple accounts and have a smaller blast radius when/if a password is compromised.
      - 8y ago
jedberg 8y ago
By using a bloom filter, you'll deny a lot of perfectly valid passwords. Bloom filters are designed to be quick and give a lot of false positives, in exchange for never having a false negative. If you're ok with not allowing a lot of valid passwords, than this approach has some merit, but user beware.
- zwily 8y ago
  You can tune how much "a lot" is. In this case, the filter appears to be tuned for a 1 in 1000 false positive rate. How annoying that may be to your customers is up to you to decide. (I'm not sure about the utility in banning every exposed password ever anyway.) You could also use this is a pre-check before querying the real haveibeenpwned api.
  - FRex 8y ago
    Due to the fact how little 500 million passwords is out of the entire set of all possible passwords (even with single digit length) the 1 in 1000 false positive rate is extremely high actually. See my other comment: https://news.ycombinator.com/item?id=17323068 https://news.ycombinator.com/item?id=17323068
  - philwelch 8y ago
    > You could also use this is a pre-check before querying the real haveibeenpwned api. Yeah, bloom filters are a fantastic pseudo-caching layer.
    - slededit 8y ago
      To me a cache is actually the inverse data structure of a bloom filter. A bloom filter will return whether something is in a set with potential false positives but never false negatives. A cache will return whether something is in a set but with potential false negatives but never false positives (i.e. item is not currently in the cache but exists in the set).
      - 8y ago
thanks_I_hateit 8y ago
Great idea. Another tool to enable dickhead sysadmins to enforce even more capricious password rules. Hint: the more rules enforced, the more predictable the passwords become. Lazy people will find ways to be just as lazy, in a smaller password space. More passwords start to look the same.
- FRex 8y ago
  These are not any rules. This haveibeenpwned list was made of password lists that were already leaked in hacks before and its author criticizes the 'now add a number', 'now add a symbol', 'now add a capital' rules that result in 'mypassword1_A'.
- Johnny555 8y ago
  There's only one rule that should be needed - a long (24+ char) random string. With a long enough password, mixed case, punctuation, etc becomes less relevant.
  - tomjen3 8y ago
    Nobody can remember a random string that long -- which might be okay, if you assume (which I don't think is unreasonable) that it is written down or remembered by a password app.
    - tylersmith 8y ago
      Everybody should be using a password manager. The times of it being reasonable to use garbage passwords because you want to remember them is long past.
      - Spivak 8y ago
        What's the password for your local machine before you can launch the password manager? What's the password for the password manager? What do you do on a shared machine that doesn't have your password manager software installed? What's the password for the place where you could download your database on a new machine? Password requirements so complex humans can't remember them is just slang for DIY 2FA where the factors are a weak password and possession of your user's database. You might as well just require actual 2FA at that point and lax the requirements.
peterwwillis 8y ago
What is a bad password? It's a password that's easy to guess. Nobody is going to guess 500 million passwords. If they get the password hash, just assume they're going to crack it. To protect against this eventuality, I think forcing users to create a new password every 6 months might be a really powerful protection for consumers. Rather than try to verify if a password is easy to guess, you could offer up strong password suggestions if the user can't create a good one in two tries using basic password heuristics. Most online accounts are not critical to a user's life if they get hacked; the real danger is in reused passwords. If you generate random passwords for the users, there's no way they're going to reuse it. So that might be better for user security than just fighting to try to get a password that's impossible to guess/brute force. So my suggestion is to just generate a super difficult password for the user and tell them to save it in their browser's password manager (make sure your site behaves well with browsers' password save feature), and if they forget it, hit that "e-mail me a password reset link" button. After that, implement non-SMS 2FA.
- ggggtez 8y ago
  >new password every 6 months This has been tried. It doesn't work. Two factor is the real solution.
  - peterwwillis 8y ago
    Two factor only prevents someone logging into your current account; it doesn't prevent someone from reusing your password on a different system. I'm talking about two completely different attacks. One is password reuse, one is not. 2FA does not protect against password reuse, because not every system in the world offers 2FA.
    - ggggtez 8y ago
      2FA "only" prevents someone from logging into my account? What do you mean "only"? That's the whole point!
      - 8y ago
oppositelock 8y ago
You don't have to store every compromised password ever to ensure users have a reasonable one. Just follow the NIST recommendations, and check against the top million, or top few million, and you're all set. If you use a good password storage library, and you slow down guessing attacks, or stop them altogether, your users will be safe. Those 300 million compromised passwords have a very long tail, and if you let a hacker attempt a few million password attempts running down the list, you've already failed.
- dwaite 8y ago
  IMHO, you only need to block the top few (thousand) if you have a policy to block rapid/unlimited guessing. The issue is targeted attacks, when a strong password was reused by someone between say linkedin and their corporate account. If I can get a list of compromised email addresses and passwords, I will be trying those email/password combinations across services, not passwords from the top 100.
  - oppositelock 8y ago
    Fair enough. It's hard to protect against users being silly. No matter how you salt, hash, and encrypt, if someone knows the username/password, they're in. I delegate auth for the systems I build to a SAML provider, and require 2FA. An expert can do a much better job managing passwords than me, and as long as I trust their identity document, we're good to go.
  - slavik81 8y ago
    Attacking accounts with reused credentials seems to be pretty common. > We have some ability at ArenaNet to watch hacking attempts live, and it tells a fascinating story. We watch as hackers use tens of thousands of different IP addresses to scan through millions of attempted account names and passwords, almost all of which are for accounts that don’t even exist in our database, looking for matches. They’re not guessing or brute-forcing passwords; they’re trying a very specific account name and password for each attempt. For example, account name “joe.user@example.com”, password “alligator101”. If they don’t get a match immediately, they may try a variant like “alligator100” or “alligator102”, then they quickly move on to the next entry on their list. And it’s interesting to see that the passwords on these lists are mostly quite good passwords. For every one account on the hackers’ lists with a password like “twilight” (real example, ಠ_ಠ), there are dozens of accounts with good strong passwords. So the world at large clearly knows how to pick good passwords; the reason people are still getting hacked is because they use the same passwords on multiple sites. https://www.guildwars2.com/en/news/mike-obrien-on-account-security/ https://www.guildwars2.com/en/news/mike-obrien-on-account-se...
_dcwr 8y ago
PSA for anyone playing around with that haveibeenpwned file: the text list is 30 GB after un7zipping but every line is padded with many trailing spaces (up to 61 chars I think, making all lines equal in length) and the line endings are the Windows ones (\r\n, instead of just a \n). With trailing spaces and \rs stripped the file is 'just' 21 GB and fits onto a RAM disk on a 32 GB machine with no swapping. This has bit me because I was playing with that file and to save space and fit it onto a RAM disk (to save time) I've converted it to binary and then when converting it back it had a different hash despite being 'exactly the same', only later I've realized it's using Windows line endings and trailing spaces padding (and that I didn't even have to bother with binary, since 21 GB comfortably fits in a RAM disk on a machine with 32 GB RAM while 30 GB didn't with browser, Windows, etc. running). Troy said it's a quirk of the export, might be fixed in next version of the file but doesn't matter for the compressed 7z size (which is true, I've checked personally with 7z going at it for hours and it really did compress those line endings and spaces down to nothing). Edit: Also see my other comment about how very overly eager at rejecting passwords this filter might be (unless I've made an error in my reasoning that someone has since pointed out): https://news.ycombinator.com/item?id=17323068 https://news.ycombinator.com/item?id=17323068
FRex 8y ago
Does 1 in 1000 false positive mean that 1 in every 1000 passwords not on the list returns a true? If so, that's not good because good passwords vastly outnumber the bad ones so even a small false positive rate makes a positive very very unlikely to be a true one. For example: let's assume all passwords (including all of the ones on haveibeenpwned list) are exactly 8 chars long and composed of 50 characters. This gives a lot of headstart to this filter since the way possible passwords outnumber ones on the list is extremely more crushing in reality due to many possible lengths, unbounded length and there being 95 printable ASCII chars to use (even alnums themselves is 62 chars already). passlen = 8 passchars = 50 badpasses = 501636842 allpasses = passchars ** passlen falsepos = 0.001 print(badpasses / (badpasses + falsepos * allpasses)) The above script prints 0.012679079642336052, which means (in these extremely forgiving scenario from above where possible passwords are limited to next to nothing compared to real life) only just over one in a hundred positives is a true positive. This apparently comes up with FP rates for cancer and AV and such (most people dont' have cancer, most exes aren't viruses, etc.). I might be wrong, feel free to point that out. I'm not a statistician or a doctor, I just had a statistics class as part of my CS degree. :) Edit: I've found the English terms and explanations: https://en.wikipedia.org/wiki/Sensitivity_and_specificity https://en.wikipedia.org/wiki/Sensitivity_and_specificity https://en.wikipedia.org/wiki/False_positive_paradox https://en.wikipedia.org/wiki/False_positive_paradox
- kolpa 8y ago
  What you are missing is that the cost of a false negative is over 1000x the cost of a false positive. The number of false positives don't matter, and getting a false positive matters nearly not at all. 1 in 1000 good passwords are rejected. Good passwords are nearly random, and cheap to generate. That means that average person needs to re-pick a password once every, what, 100 years?
- bo1024 8y ago
  The right way to think about the base rate is the chance that a random user is going to try a bad password. You made the base assumption that the user tries a random 8-char password, which means the base rate of a bad password is 1 in 100,000. With a FP rate of 1 in 1,000 this means that 99/100 positives are false ones. In other words, if you were right, every 100,000 users would only trip the filter 100 times, and of those, 99 would be false positives. But actually, probably more like 1 in 10 or 1 in 50 users use bad passwords. If we use 1 in 50, we get that 19/20 positives are true positives and only 1/20 are false positives. With 100,000 users we'd expect to trip the filter 2,000 times, only 100 of which are false positives.
daedalus2027 8y ago
You are doing hashes over hashes, even if you cut the hashes to 4bytes you are going to hash them again. you have to skip that second hashing and you'll get a more decent performance. since you are alreading dealing with hashes. Check my implementation: https://github.com/daedalus/bloomHIBP https://github.com/daedalus/bloomHIBP https://github.com/daedalus/fastBloomFilter https://github.com/daedalus/fastBloomFilter With a 512MB bloom filter I can get 0 FP.
- Buge 8y ago
  I don't see how it's possible to have 0 false positives. I thought it was inherent in the nature of a bloom filter to have false positives. This site is a false positive rate calculator: https://hur.st/bloomfilter/?n=500M&p=1000&m=&k= https://hur.st/bloomfilter/?n=500M&p=1000&m=&k=
fearYourVarChar 8y ago
I’d almost suggest a form of passive threat analysis, on the basis that someone occupying a compromised hash is regarded as a weak link (don’t ban the hash, but notice it, and keep an eye on things surrounding it), but even that idea is bound to provoke abuse. E.G. Right now, Google keeps looking at my browser string, and starts whining and making unwarranted demands when it sees something unexpected. Oh noes! UR browser string seems goofy! Time for mandatory 2 factor auth, buddy! Fuck you, Google. Fuck you, right in your stupid fucking face. I decide my security stance. I decide what’s dangerous. I decide which risks are acceptable.
bo1024 8y ago
Isn't sending the SHA1 of a password over the web, such as via a DNS request, a bit insecure?
- splitrocket 8y ago
  The sha1 doesn't live in the DNS request. DNS exposes the hostname requested, not the parameters of the URL.
- w8rbt 8y ago
  It does not take SHA1 hashes.
  - Buge 8y ago
    It takes 64 bits of a sha1 hash, which is effectively the same as a sha1 hash for most users' passwords.
    - w8rbt 8y ago
      Except it's missing 96 bits (which is the vast majority) of the hash. So it's not a SHA1 hash. Why do you think that most passwords are just in the first 64 bits of a SHA1 hash?
      - Buge 8y ago
        What is an attacker going to do with the hash? The attacker will try to crack it, to get the original password. As long as the user's password had at most 64 bits of entropy, it's just as easy to crack a truncated sha1 hash as a full sha1 hash. Truncating it has not harmed the attacker at all. The attacker doesn't care if it's a full sha1 hash or a truncated sha1 hash. The attacker just cares about cracking it. >Why do you think that most passwords are just in the first 64 bits of a SHA1 hash? I don't understand what you're trying to say. Are you asking why I think most passwords have less than 64 bits of entropy? >According to one study involving half a million users, the average password entropy was estimated at 40.54 bits. https://en.wikipedia.org/wiki/Password_strength#Human-generated_passwords https://en.wikipedia.org/wiki/Password_strength#Human-genera...
Null-Set 8y ago
Here is a oneliner to try it out with your own passwords read -s password && curl -4 https://www.bloomingpassword.fun/hashes/sha1/$(echo -n "$password" | shasum | cut -c 1-16)
decafb 8y ago
That would make it possible to create a program that would check all the passwords in the keychain without sending data over the web. False positives wouldn't be an issue as the user can decide himself if he wants to update. Currently it still is a bit of a big filter to have on a mobile device - wonder how far it could be slimed down and to have just 99% accuracy. I just wonder how one could create such a program that the users will have some guarantees that it will not leak stuff.
- arthurfm 8y ago
  > I just wonder how one could create such a program that the users will have some guarantees that it will not leak stuff. You could do what Okta does with its PassProtect [1][2][3] browser extension and use the Have I Been Pwned API along with k-Anonymity [4][5][6]. PassProtect is a browser plugin that makes it easy for people to see in the moment whether or not their password was exposed in a breach. With a real time, as-you-type notification, PassProtect quickly alerts users of possible "riskier" passwords so they can take action immediately and without compromising privacy. By using k-anonymity, PassProtect ensures that your passwords are never seen, stored, or sent over the network during this checking process. We’ve also made it easy for developers to add this functionality directly into their app or website. By also surfacing related information and breach details, PassProtect promotes security awareness for users while relieving developers of the burden of tracking breaches and maintaining a homegrown tool. [1] https://www.passprotect.io/ https://www.passprotect.io/ [2] https://www.okta.com/blog/2018/05/add-passprotect-to-your-web-browser/ https://www.okta.com/blog/2018/05/add-passprotect-to-your-we... [3] https://chrome.google.com/webstore/detail/passprotect/cpimldclklpfifolmdnicjnfbjdepjnf https://chrome.google.com/webstore/detail/passprotect/cpimld... [4] https://www.troyhunt.com/ive-just-launched-pwned-passwords-version-2/ https://www.troyhunt.com/ive-just-launched-pwned-passwords-v... [5] https://blog.cloudflare.com/validating-leaked-passwords-with-k-anonymity/ https://blog.cloudflare.com/validating-leaked-passwords-with... [6] https://github.com/OktaSecurityLabs/passprotect-js https://github.com/OktaSecurityLabs/passprotect-js
megaman22 8y ago
I hate password restrictions. They are dumb and make people use more easily guessable passwords, because otherwise the user themselves is unable to remember. It's like, okay, I need uppercase, a symbol, a number, oh well, I'll just use my password, camelCased, with an underscore and my favorite number appended. Especially for some bullshit service that I have no real interest in having an account for in the first place. Love it or hate it, at least OAuth with Google or Facebook or Microsoft cuts down on that nonsense a little bit.
conroy 8y ago
If you're looking to build a server-side check for password re-use, I'd suggest using the Have I Been Pwned API. When searching by range[0], you only send the first 5 characters of the SHA-1 password hash, thus preserving the privacy of your users' passwords. Cloudflare has a great write up on how it works[1]. [0] https://haveibeenpwned.com/API/v2#SearchingPwnedPasswordsByRange https://haveibeenpwned.com/API/v2#SearchingPwnedPasswordsByR... [1] https://blog.cloudflare.com/validating-leaked-passwords-with-k-anonymity/ https://blog.cloudflare.com/validating-leaked-passwords-with...

226 points by vuln 8y ago

Buge 8y ago

I'm not sure if 1/1000 is the right tradeoff. You can get 1/100000 for less than double the size. https://hur.st/bloomfilter/?n=500M&p=100000&m=&k= https://hur.st/bloomfilter/?n=500M&p=100000&m=&k=

fenollp 8y ago

Code is at https://github.com/w8rbt/blooming_password https://github.com/w8rbt/blooming_password but is private/404 right now.

transitivebs 8y ago
Yeah, I'd love to check out the source.
- brianm 8y ago
  A different implementation of same idea, if you just want to see how it's been done at least once: https://github.com/brianm/pwned https://github.com/brianm/pwned
  - FRex 8y ago
    Are you aware of the pitfall I've mentioned here?: https://news.ycombinator.com/item?id=17323068 https://news.ycombinator.com/item?id=17323068 Just making the possible passwords be 10 chars and contain chars out of a set of 62 (lowercase + uppercase + digits) gives me 0.05 sensitivity at 0.00000001 (0.000001%) FP rate. Edit: (This is reply to w8rbt below, here since HN has decided I cannot post anymore for next who knows how many hours.) I'm aware of this and wouldn't treat a bloom filter as the final decision maker if there is a hit but many people seem to act like it is intended to be one and bring up its FP rate as low enough, i.e.: 1. This comment and several of its replies: https://news.ycombinator.com/item?id=17322692 https://news.ycombinator.com/item?id=17322692 2. This comment telling me false positives don't matter: https://news.ycombinator.com/item?id=17323438 https://news.ycombinator.com/item?id=17323438 3. Both of the linked bloom filters don't mention that if there is a hit you should check with https://haveibeenpwned.com/ https://haveibeenpwned.com/ API. 4. (Of course, this is HN after all!) my comments pointing this paradox/pitfall/whatever out being at negative point scores. I've literally lowered my score for saying "hey, 1 in 1000 FP isn't actually super accurate and almost sure hit is a good hit". And there are one or two green named users who seem to be criticizing this bloom filter with freshly made accounts, exactly because of this BS.
    - w8rbt 8y ago
      Read the original Bloom Filter paper from 1970. It covers all of this and it's very short. If the test for membership returns 'probably' then you do the more expensive test if you need to know for certain or you don't use one to begin with: Space/Time Trade-offs in Hash Coding with Allowable Errors BURTON H. BLOOM https://dl.acm.org/citation.cfm?doid=362686.362692 https://dl.acm.org/citation.cfm?doid=362686.362692

sirsuki 8y ago

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.
8y ago

reiichiroh 8y ago

The Palo Alto NG firewalls can do this although I haven't gotten it working yet.

kchr 8y ago
Do what exactly? Check for bad passwords by inspecting traffic...?
- vuln 8y ago
  Yes, 'Phishing Attack Prevention' https://live.paloaltonetworks.com/t5/Featured-Articles/PAN-OS-8-0-PAN-OS-Phishing-Attack-Prevention/ta-p/129935 https://live.paloaltonetworks.com/t5/Featured-Articles/PAN-O...
  - dustindecker 8y ago
    Intercepting TLS on a device running rebranded CentOS 5 (11 year old distro that stopped getting security updates over a year ago) does not seem like a safe idea.

bloomthrowaway 8y ago

Sorry to say this, but this is actually worse than just truncating the hash. Why? Bloom filters are designed to maintain a reasonable false positive rate while still allowing you to add items extremely quickly (high insertion rate). Since the bad password list is presumably fixed (or almost so) you can do checks faster and with a lower FP rate by just truncating the hashes and prefix sorting the list ahead of time.

dlhavema 8y ago
but don't you still have to store/manage the whole 30gb list of hashes? the point of a bloom filter is it can store any arbitrary string in 7-8 BITS depending on how many hash functions you use to test for existence
- bloomthrowaway 8y ago
  If you use a secure hash on the banned passwords they will be random (as good as arbitrary), then just truncate them to 7-8 bits and sort by prefix, searching them using binary search. It will be more efficient than a Bloom filter because there can be zero empty space between entries. It creates a structure similar to a Bloom filter but with no wasted space (no empty entries) A Bloom filter is great when you need a probabilistic hash table that is fairly efficient and can have records added efficiently. With a fixed list as I described above, the insertion cost is enormous (avg cost of moving 1/2 of the array elements), but the space/speed efficiency reaches the theoretical limit
  - dlhavema 8y ago
    thanks for the clarification, with a fixed list that makes sense.
  - pronoiac 8y ago
    Your math is bogus. 7-8 bits? If there's one entry, that would give false positives of 1/256, or 0.3%. Even given 1k entries would likely hit the vast majority of entries. Or, flipping this: every time you add a password, you check that it hasn't been used before. You can only set 256 passwords, total, before the space of truncated hashes is filled.

Tostino 8y ago

Another option if you're able to do a server side check, is to use a library like nbvcxz (Full disclosure, I wrote it): https://github.com/GoSimpleLLC/nbvcxz https://github.com/GoSimpleLLC/nbvcxz If you have a list of passwords you want to exclude, you can load it into the library, or it comes with it's own list of common passwords from leaked datasets.

ezekg 8y ago
Does nbvcxz do anything different than zxcvbn? Just curious on if your implementation does anything different/better. (Might be mentioned in the README, which I just skimmed, so apologies if so.)
- web007 8y ago
  The very first line of the README: nbvcxz is java library (and standalone console program) which is heavily inspired by the work in zxcvbn. Also it has https://github.com/GoSimpleLLC/nbvcxz#differentiating-features https://github.com/GoSimpleLLC/nbvcxz#differentiating-featur... for its own features, but not necessarily how it compares to zxcvbn.
  - ezekg 8y ago
    I saw that it was heavily inspired by zxcvbn, which is why I asked. Didn't see the differentiating features, so ty for the link.
- Tostino 8y ago
  Hey there. As said, the readme points out the major differences with zxcvbn. I think the main difference you'd see, is the quality of matches and the scores generated are superior to zxcvbn. I had put a lot of work into fixing some of the algorithms, and adding more than the original to cover all the corner cases zxcvbn didn't support well. For example, I support finding separators within a password with nbvcxz, so passphrase detection is much much better. I also added support for levenshtein distance calculations for dictionary matches. So common misspelling, or slight alterations to a word will be caught, even if they are not included in the dictionary. Also, internationalization support is nice for those who need it.

sandworm101 8y ago

500,000,000 forbidden passwords/hashes? What exactly is the real benefit of excluding those? It only matters if someone steals your list of hashed passwords AND you have hashed them in some deficient way (poor salting etc) so that the hashes may be "reversed" and used. That a password has been used by someone else in the past, for some other reason, and that password is now on some database, does not make that password dangerous. What matters is whether your users are using the same passwords across multiple services, services out of your control. But ATM no tech out there would allow you to test for this. If your system cannot detect someone running 500,000,000 passwords against a single account, you have far bigger problems.

andrewla 8y ago
> What matters is whether your users are using the same passwords across multiple services, services out of your control. But ATM no tech out there would allow you to test for this. Checking against a list of known passwords from breaches does accomplish this, albeit with a high false positive rate.
- sandworm101 8y ago
  Does it? If I have used the same password at a dozen sites, and none of those sites have ever suffered a public breech, then my password isn't in any public database.[1] So you will also have a high false negative rate, something far more dangerous than false positives. I don't think I'm alone in using passwords across multiple sites. Every here lives in that glass house.
  - dsnuh 8y ago
    > and none of those sites have ever suffered a public breech Yet. That you know of. > Every here lives in that glass house. No, some of us use password manager software for exactly this reason - so we don't use the same password across multiple accounts and have a smaller blast radius when/if a password is compromised.
    - 8y ago

jedberg 8y ago

By using a bloom filter, you'll deny a lot of perfectly valid passwords. Bloom filters are designed to be quick and give a lot of false positives, in exchange for never having a false negative. If you're ok with not allowing a lot of valid passwords, than this approach has some merit, but user beware.

zwily 8y ago
You can tune how much "a lot" is. In this case, the filter appears to be tuned for a 1 in 1000 false positive rate. How annoying that may be to your customers is up to you to decide. (I'm not sure about the utility in banning every exposed password ever anyway.) You could also use this is a pre-check before querying the real haveibeenpwned api.
- FRex 8y ago
  Due to the fact how little 500 million passwords is out of the entire set of all possible passwords (even with single digit length) the 1 in 1000 false positive rate is extremely high actually. See my other comment: https://news.ycombinator.com/item?id=17323068 https://news.ycombinator.com/item?id=17323068
- philwelch 8y ago
  > You could also use this is a pre-check before querying the real haveibeenpwned api. Yeah, bloom filters are a fantastic pseudo-caching layer.
  - slededit 8y ago
    To me a cache is actually the inverse data structure of a bloom filter. A bloom filter will return whether something is in a set with potential false positives but never false negatives. A cache will return whether something is in a set but with potential false negatives but never false positives (i.e. item is not currently in the cache but exists in the set).
    - 8y ago

thanks_I_hateit 8y ago

Great idea. Another tool to enable dickhead sysadmins to enforce even more capricious password rules. Hint: the more rules enforced, the more predictable the passwords become. Lazy people will find ways to be just as lazy, in a smaller password space. More passwords start to look the same.

FRex 8y ago
These are not any rules. This haveibeenpwned list was made of password lists that were already leaked in hacks before and its author criticizes the 'now add a number', 'now add a symbol', 'now add a capital' rules that result in 'mypassword1_A'.
Johnny555 8y ago
There's only one rule that should be needed - a long (24+ char) random string. With a long enough password, mixed case, punctuation, etc becomes less relevant.
- tomjen3 8y ago
  Nobody can remember a random string that long -- which might be okay, if you assume (which I don't think is unreasonable) that it is written down or remembered by a password app.
  - tylersmith 8y ago
    Everybody should be using a password manager. The times of it being reasonable to use garbage passwords because you want to remember them is long past.
    - Spivak 8y ago
      What's the password for your local machine before you can launch the password manager? What's the password for the password manager? What do you do on a shared machine that doesn't have your password manager software installed? What's the password for the place where you could download your database on a new machine? Password requirements so complex humans can't remember them is just slang for DIY 2FA where the factors are a weak password and possession of your user's database. You might as well just require actual 2FA at that point and lax the requirements.

peterwwillis 8y ago

What is a bad password? It's a password that's easy to guess. Nobody is going to guess 500 million passwords. If they get the password hash, just assume they're going to crack it. To protect against this eventuality, I think forcing users to create a new password every 6 months might be a really powerful protection for consumers. Rather than try to verify if a password is easy to guess, you could offer up strong password suggestions if the user can't create a good one in two tries using basic password heuristics. Most online accounts are not critical to a user's life if they get hacked; the real danger is in reused passwords. If you generate random passwords for the users, there's no way they're going to reuse it. So that might be better for user security than just fighting to try to get a password that's impossible to guess/brute force. So my suggestion is to just generate a super difficult password for the user and tell them to save it in their browser's password manager (make sure your site behaves well with browsers' password save feature), and if they forget it, hit that "e-mail me a password reset link" button. After that, implement non-SMS 2FA.

ggggtez 8y ago
>new password every 6 months This has been tried. It doesn't work. Two factor is the real solution.
- peterwwillis 8y ago
  Two factor only prevents someone logging into your current account; it doesn't prevent someone from reusing your password on a different system. I'm talking about two completely different attacks. One is password reuse, one is not. 2FA does not protect against password reuse, because not every system in the world offers 2FA.
  - ggggtez 8y ago
    2FA "only" prevents someone from logging into my account? What do you mean "only"? That's the whole point!
    - 8y ago

oppositelock 8y ago

You don't have to store every compromised password ever to ensure users have a reasonable one. Just follow the NIST recommendations, and check against the top million, or top few million, and you're all set. If you use a good password storage library, and you slow down guessing attacks, or stop them altogether, your users will be safe. Those 300 million compromised passwords have a very long tail, and if you let a hacker attempt a few million password attempts running down the list, you've already failed.

dwaite 8y ago
IMHO, you only need to block the top few (thousand) if you have a policy to block rapid/unlimited guessing. The issue is targeted attacks, when a strong password was reused by someone between say linkedin and their corporate account. If I can get a list of compromised email addresses and passwords, I will be trying those email/password combinations across services, not passwords from the top 100.
- oppositelock 8y ago
  Fair enough. It's hard to protect against users being silly. No matter how you salt, hash, and encrypt, if someone knows the username/password, they're in. I delegate auth for the systems I build to a SAML provider, and require 2FA. An expert can do a much better job managing passwords than me, and as long as I trust their identity document, we're good to go.
- slavik81 8y ago
  Attacking accounts with reused credentials seems to be pretty common. > We have some ability at ArenaNet to watch hacking attempts live, and it tells a fascinating story. We watch as hackers use tens of thousands of different IP addresses to scan through millions of attempted account names and passwords, almost all of which are for accounts that don’t even exist in our database, looking for matches. They’re not guessing or brute-forcing passwords; they’re trying a very specific account name and password for each attempt. For example, account name “joe.user@example.com”, password “alligator101”. If they don’t get a match immediately, they may try a variant like “alligator100” or “alligator102”, then they quickly move on to the next entry on their list. And it’s interesting to see that the passwords on these lists are mostly quite good passwords. For every one account on the hackers’ lists with a password like “twilight” (real example, ಠ_ಠ), there are dozens of accounts with good strong passwords. So the world at large clearly knows how to pick good passwords; the reason people are still getting hacked is because they use the same passwords on multiple sites. https://www.guildwars2.com/en/news/mike-obrien-on-account-security/ https://www.guildwars2.com/en/news/mike-obrien-on-account-se...

_dcwr 8y ago

PSA for anyone playing around with that haveibeenpwned file: the text list is 30 GB after un7zipping but every line is padded with many trailing spaces (up to 61 chars I think, making all lines equal in length) and the line endings are the Windows ones (\r\n, instead of just a \n). With trailing spaces and \rs stripped the file is 'just' 21 GB and fits onto a RAM disk on a 32 GB machine with no swapping. This has bit me because I was playing with that file and to save space and fit it onto a RAM disk (to save time) I've converted it to binary and then when converting it back it had a different hash despite being 'exactly the same', only later I've realized it's using Windows line endings and trailing spaces padding (and that I didn't even have to bother with binary, since 21 GB comfortably fits in a RAM disk on a machine with 32 GB RAM while 30 GB didn't with browser, Windows, etc. running). Troy said it's a quirk of the export, might be fixed in next version of the file but doesn't matter for the compressed 7z size (which is true, I've checked personally with 7z going at it for hours and it really did compress those line endings and spaces down to nothing). Edit: Also see my other comment about how very overly eager at rejecting passwords this filter might be (unless I've made an error in my reasoning that someone has since pointed out): https://news.ycombinator.com/item?id=17323068 https://news.ycombinator.com/item?id=17323068

FRex 8y ago

Does 1 in 1000 false positive mean that 1 in every 1000 passwords not on the list returns a true? If so, that's not good because good passwords vastly outnumber the bad ones so even a small false positive rate makes a positive very very unlikely to be a true one. For example: let's assume all passwords (including all of the ones on haveibeenpwned list) are exactly 8 chars long and composed of 50 characters. This gives a lot of headstart to this filter since the way possible passwords outnumber ones on the list is extremely more crushing in reality due to many possible lengths, unbounded length and there being 95 printable ASCII chars to use (even alnums themselves is 62 chars already). passlen = 8 passchars = 50 badpasses = 501636842 allpasses = passchars ** passlen falsepos = 0.001 print(badpasses / (badpasses + falsepos * allpasses)) The above script prints 0.012679079642336052, which means (in these extremely forgiving scenario from above where possible passwords are limited to next to nothing compared to real life) only just over one in a hundred positives is a true positive. This apparently comes up with FP rates for cancer and AV and such (most people dont' have cancer, most exes aren't viruses, etc.). I might be wrong, feel free to point that out. I'm not a statistician or a doctor, I just had a statistics class as part of my CS degree. :) Edit: I've found the English terms and explanations: https://en.wikipedia.org/wiki/Sensitivity_and_specificity https://en.wikipedia.org/wiki/Sensitivity_and_specificity https://en.wikipedia.org/wiki/False_positive_paradox https://en.wikipedia.org/wiki/False_positive_paradox

kolpa 8y ago
What you are missing is that the cost of a false negative is over 1000x the cost of a false positive. The number of false positives don't matter, and getting a false positive matters nearly not at all. 1 in 1000 good passwords are rejected. Good passwords are nearly random, and cheap to generate. That means that average person needs to re-pick a password once every, what, 100 years?
bo1024 8y ago
The right way to think about the base rate is the chance that a random user is going to try a bad password. You made the base assumption that the user tries a random 8-char password, which means the base rate of a bad password is 1 in 100,000. With a FP rate of 1 in 1,000 this means that 99/100 positives are false ones. In other words, if you were right, every 100,000 users would only trip the filter 100 times, and of those, 99 would be false positives. But actually, probably more like 1 in 10 or 1 in 50 users use bad passwords. If we use 1 in 50, we get that 19/20 positives are true positives and only 1/20 are false positives. With 100,000 users we'd expect to trip the filter 2,000 times, only 100 of which are false positives.

daedalus2027 8y ago

You are doing hashes over hashes, even if you cut the hashes to 4bytes you are going to hash them again. you have to skip that second hashing and you'll get a more decent performance. since you are alreading dealing with hashes. Check my implementation: https://github.com/daedalus/bloomHIBP https://github.com/daedalus/bloomHIBP https://github.com/daedalus/fastBloomFilter https://github.com/daedalus/fastBloomFilter With a 512MB bloom filter I can get 0 FP.

Buge 8y ago
I don't see how it's possible to have 0 false positives. I thought it was inherent in the nature of a bloom filter to have false positives. This site is a false positive rate calculator: https://hur.st/bloomfilter/?n=500M&p=1000&m=&k= https://hur.st/bloomfilter/?n=500M&p=1000&m=&k=

fearYourVarChar 8y ago

I’d almost suggest a form of passive threat analysis, on the basis that someone occupying a compromised hash is regarded as a weak link (don’t ban the hash, but notice it, and keep an eye on things surrounding it), but even that idea is bound to provoke abuse. E.G. Right now, Google keeps looking at my browser string, and starts whining and making unwarranted demands when it sees something unexpected. Oh noes! UR browser string seems goofy! Time for mandatory 2 factor auth, buddy! Fuck you, Google. Fuck you, right in your stupid fucking face. I decide my security stance. I decide what’s dangerous. I decide which risks are acceptable.

bo1024 8y ago

Isn't sending the SHA1 of a password over the web, such as via a DNS request, a bit insecure?

splitrocket 8y ago
The sha1 doesn't live in the DNS request. DNS exposes the hostname requested, not the parameters of the URL.
w8rbt 8y ago
It does not take SHA1 hashes.
- Buge 8y ago
  It takes 64 bits of a sha1 hash, which is effectively the same as a sha1 hash for most users' passwords.
  - w8rbt 8y ago
    Except it's missing 96 bits (which is the vast majority) of the hash. So it's not a SHA1 hash. Why do you think that most passwords are just in the first 64 bits of a SHA1 hash?
    - Buge 8y ago
      What is an attacker going to do with the hash? The attacker will try to crack it, to get the original password. As long as the user's password had at most 64 bits of entropy, it's just as easy to crack a truncated sha1 hash as a full sha1 hash. Truncating it has not harmed the attacker at all. The attacker doesn't care if it's a full sha1 hash or a truncated sha1 hash. The attacker just cares about cracking it. >Why do you think that most passwords are just in the first 64 bits of a SHA1 hash? I don't understand what you're trying to say. Are you asking why I think most passwords have less than 64 bits of entropy? >According to one study involving half a million users, the average password entropy was estimated at 40.54 bits. https://en.wikipedia.org/wiki/Password_strength#Human-generated_passwords https://en.wikipedia.org/wiki/Password_strength#Human-genera...

Null-Set 8y ago

Here is a oneliner to try it out with your own passwords read -s password && curl -4 https://www.bloomingpassword.fun/hashes/sha1/$(echo -n "$password" | shasum | cut -c 1-16)

decafb 8y ago

That would make it possible to create a program that would check all the passwords in the keychain without sending data over the web. False positives wouldn't be an issue as the user can decide himself if he wants to update. Currently it still is a bit of a big filter to have on a mobile device - wonder how far it could be slimed down and to have just 99% accuracy. I just wonder how one could create such a program that the users will have some guarantees that it will not leak stuff.

arthurfm 8y ago
> I just wonder how one could create such a program that the users will have some guarantees that it will not leak stuff. You could do what Okta does with its PassProtect [1][2][3] browser extension and use the Have I Been Pwned API along with k-Anonymity [4][5][6]. PassProtect is a browser plugin that makes it easy for people to see in the moment whether or not their password was exposed in a breach. With a real time, as-you-type notification, PassProtect quickly alerts users of possible "riskier" passwords so they can take action immediately and without compromising privacy. By using k-anonymity, PassProtect ensures that your passwords are never seen, stored, or sent over the network during this checking process. We’ve also made it easy for developers to add this functionality directly into their app or website. By also surfacing related information and breach details, PassProtect promotes security awareness for users while relieving developers of the burden of tracking breaches and maintaining a homegrown tool. [1] https://www.passprotect.io/ https://www.passprotect.io/ [2] https://www.okta.com/blog/2018/05/add-passprotect-to-your-web-browser/ https://www.okta.com/blog/2018/05/add-passprotect-to-your-we... [3] https://chrome.google.com/webstore/detail/passprotect/cpimldclklpfifolmdnicjnfbjdepjnf https://chrome.google.com/webstore/detail/passprotect/cpimld... [4] https://www.troyhunt.com/ive-just-launched-pwned-passwords-version-2/ https://www.troyhunt.com/ive-just-launched-pwned-passwords-v... [5] https://blog.cloudflare.com/validating-leaked-passwords-with-k-anonymity/ https://blog.cloudflare.com/validating-leaked-passwords-with... [6] https://github.com/OktaSecurityLabs/passprotect-js https://github.com/OktaSecurityLabs/passprotect-js

megaman22 8y ago

I hate password restrictions. They are dumb and make people use more easily guessable passwords, because otherwise the user themselves is unable to remember. It's like, okay, I need uppercase, a symbol, a number, oh well, I'll just use my password, camelCased, with an underscore and my favorite number appended. Especially for some bullshit service that I have no real interest in having an account for in the first place. Love it or hate it, at least OAuth with Google or Facebook or Microsoft cuts down on that nonsense a little bit.

conroy 8y ago

If you're looking to build a server-side check for password re-use, I'd suggest using the Have I Been Pwned API. When searching by range[0], you only send the first 5 characters of the SHA-1 password hash, thus preserving the privacy of your users' passwords. Cloudflare has a great write up on how it works[1]. [0] https://haveibeenpwned.com/API/v2#SearchingPwnedPasswordsByRange https://haveibeenpwned.com/API/v2#SearchingPwnedPasswordsByR... [1] https://blog.cloudflare.com/validating-leaked-passwords-with-k-anonymity/ https://blog.cloudflare.com/validating-leaked-passwords-with...