[FRex]

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/False_positive_paradox

[bo1024]

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.

[vertere]

Yep, in other words the prior probability of a user trying to use a 'bad' password will be a lot higher than badpasses/allpasses. The whole point of checking against a list of compromised passwords is because people reuse their passwords.

[kolpa]

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?

[thomasahle]

One in thousand means the user is very unlikely to run into this event.

"But it's much more likely than running into a true positive" you might say.

Actually not, since the user runs into a true positive exactly when they choose a very common password. It's not random. If they only choose bad passwords they'll run into true positives evey single time.

On the other hand, that there exist more false positives than true ones is actually great, since this means you can't recreate the true set of passwords given the Bloom filter.

[stochastic_monk]

That's true if you're sampling your passwords uniformly from all legal passwords, and that's not an accurate assumption.

That being said, false positives will hopefully outnumber true positives, since not many people should use one of them.

On the use of a bloom, I would instead use a cuckoo filter. Then, since its error rate plateaus when it's close to full, you could get to the same error rate with a significantly smaller filter.

[CapacitorSet]

Is it really a problem, though? Having a high false-positive-to-real-positive ratio isn't as bad for this application, since a user can just pick a slightly different password, with no significant negative outcome.