4 ms·

Going to generate a bloom-filter from this dataset tonight. Troy mentions some arguments against torrents, but it is better to have a authoritative torrent tha

Going to generate a bloom-filter from this dataset tonight. Troy mentions some arguments against torrents, but it is better to have a authoritative torrent than none, imo.

developer2 9y ago
Is a bloom filter worth it in this case? With the optimal "k" hash functions of 10 and a "p" error rate of 0.001% (false positives of approximately 1 in 1000), a bloom filter for the 306,259,512 items will take 538 MB. Increasing the error rate to 0.01% (1 in 100) is still 358 MB. That's a sizeable filter to maintain in memory (then again... RAM is cheap). I'd probably just shove the passwords into a database, limiting the index prefix to the first X characters to reduce index size.
- captn3m0 9y ago
  Distributing a 538 MB file (which can be compressed further) is much easier.
  - wongarsu 9y ago
    What are the actual use cases where this size difference matters? I distributing to a general audience, 0.5GB and 10GB isn't that much of a difference, and most people are more equipped for handling lists of strings than for handling bloom filters.
  - bradleyjg 9y ago
    >which can be compressed further Can it? I think of a bloom filter as similar to a lossy compression scheme and wouldn't expect it to be further compressible to any significant extent using a general purpose lossless scheme. Similar to how general purpose compressors generally don't do very well with mp3s or jpgs.
- Deimorz 9y ago
  Reducing the size by ~95% in exchange for a 0.001% error rate seems like a pretty nice tradeoff to be able to make for some uses. The nature of the data means it can never really be "perfect" anyway (there are certainly some password breaches that exist but aren't included in the list), so massively reducing the resources required in exchange for a bit of artificial error seems pretty reasonable to me.
bradleyjg 9y ago
A signed minimal perfect hash function may be a better bet. You can get down to around 2.68 bits per key plus w sign bits where the false positive rate is 2^-w. For false positive rate of 2^-9 (0.00195) that's 447 MB, which is slightly less than an optimal bloom filter for the same number of items, and lookups will be considerably faster. Construction time and the fact that you can't add to it without rebuilding the whole thing are the downsides. But given the application I don't think they matter much. http://sux4j.di.unimi.it/docs/it/unimi/dsi/sux4j/mph/MinimalPerfectHashFunction.html http://sux4j.di.unimi.it/docs/it/unimi/dsi/sux4j/mph/Minimal...
hedora 9y ago
It's also a bummer there are only sha1's in the file. It would be good to block things within hamming distance 2 of a leaked password (so p@ssw0rd€ would also be blacklisted...)
- Piskvorrr 9y ago
  You could go the other way, and check likely candidates from the new password - e.g. if user enters "hunter2", you check hunter and hunter0 and hunter1 and hunter3 and hunt3r2.
vanni 9y ago
Or better a cookoo filter: http://dl.acm.org/citation.cfm?doid=2674005.2674994 http://dl.acm.org/citation.cfm?doid=2674005.2674994
danbruc 9y ago
If it doesn't have to be really fast, you can simply binary search fetching no more than 29 lines from the file. Or you can interpolate the expected location of the hash and read a block around that location. This could get you down to reading only one or two disk blocks if the actual position is never more than half a disk block away from the interpolated position. It could be more but given that we are dealing with cryptographic hashes I would expect the interpolated position to never be too far away from the actual position.

Going to generate a bloom-filter from this dataset tonight. Troy mentions some arguments against torrents, but it is better to have a authoritative torrent than none, imo.

developer2 9y ago

Is a bloom filter worth it in this case? With the optimal "k" hash functions of 10 and a "p" error rate of 0.001% (false positives of approximately 1 in 1000), a bloom filter for the 306,259,512 items will take 538 MB. Increasing the error rate to 0.01% (1 in 100) is still 358 MB. That's a sizeable filter to maintain in memory (then again... RAM is cheap). I'd probably just shove the passwords into a database, limiting the index prefix to the first X characters to reduce index size.

captn3m0 9y ago
Distributing a 538 MB file (which can be compressed further) is much easier.
- wongarsu 9y ago
  What are the actual use cases where this size difference matters? I distributing to a general audience, 0.5GB and 10GB isn't that much of a difference, and most people are more equipped for handling lists of strings than for handling bloom filters.
- bradleyjg 9y ago
  >which can be compressed further Can it? I think of a bloom filter as similar to a lossy compression scheme and wouldn't expect it to be further compressible to any significant extent using a general purpose lossless scheme. Similar to how general purpose compressors generally don't do very well with mp3s or jpgs.
Deimorz 9y ago
Reducing the size by ~95% in exchange for a 0.001% error rate seems like a pretty nice tradeoff to be able to make for some uses. The nature of the data means it can never really be "perfect" anyway (there are certainly some password breaches that exist but aren't included in the list), so massively reducing the resources required in exchange for a bit of artificial error seems pretty reasonable to me.

bradleyjg 9y ago

A signed minimal perfect hash function may be a better bet. You can get down to around 2.68 bits per key plus w sign bits where the false positive rate is 2^-w. For false positive rate of 2^-9 (0.00195) that's 447 MB, which is slightly less than an optimal bloom filter for the same number of items, and lookups will be considerably faster. Construction time and the fact that you can't add to it without rebuilding the whole thing are the downsides. But given the application I don't think they matter much. http://sux4j.di.unimi.it/docs/it/unimi/dsi/sux4j/mph/MinimalPerfectHashFunction.html http://sux4j.di.unimi.it/docs/it/unimi/dsi/sux4j/mph/Minimal...

hedora 9y ago

It's also a bummer there are only sha1's in the file. It would be good to block things within hamming distance 2 of a leaked password (so p@ssw0rd€ would also be blacklisted...)

Piskvorrr 9y ago
You could go the other way, and check likely candidates from the new password - e.g. if user enters "hunter2", you check hunter and hunter0 and hunter1 and hunter3 and hunt3r2.

vanni 9y ago

Or better a cookoo filter: http://dl.acm.org/citation.cfm?doid=2674005.2674994 http://dl.acm.org/citation.cfm?doid=2674005.2674994

danbruc 9y ago

If it doesn't have to be really fast, you can simply binary search fetching no more than 29 lines from the file. Or you can interpolate the expected location of the hash and read a block around that location. This could get you down to reading only one or two disk blocks if the actual position is never more than half a disk block away from the interpolated position. It could be more but given that we are dealing with cryptographic hashes I would expect the interpolated position to never be too far away from the actual position.