5 ms·
Can't you just use something like a bloom filter? There is a bit over 1B passwords in there (based on the size of the file and the length of the line). You wou
by twawaaay 4y ago
Can't you just use something like a bloom filter?
There is a bit over 1B passwords in there (based on the size of the file and the length of the line). You would need a binary file around 3GB in size that would have to either load into memory or do about 17 accesses to read specific bytes ( no searching) to figure out if the password is in the filter.
- genericlemon24 4y agoYou can, Scott Helme wrote some articles about this (I mention them at the end of my article): * https://scotthelme.co.uk/when-pwned-passwords-bloom/ https://scotthelme.co.uk/when-pwned-passwords-bloom/ * https://scotthelme.co.uk/sketchy-pwned-passwords/ https://scotthelme.co.uk/sketchy-pwned-passwords/ – here he uses a count-min sketch to also store the frequency
- deleted 4y ago[deleted]
- UncleEntity 4y ago> Can't you just use something like a bloom filter? If I had the ability to download a massive file I’d try it out on a hextree I toy around with occasionally. If you’re making an index file may as well just throw it into a tree structure where a lookup is anywhere from 1 to 20 pointer dereferences (assuming the checksum is 20 hex digits) as it optimizes storage so tree depth is variable. Plus it can retain the counts as well. Now I really want to try this out, the last article I read along these lines I used it as a comparison and it was equally as efficient as their conclusion.
- seritools 4y agoSee the bonus chapter in the post (CTRL+F + "bloom" to find it)
- lern_too_spel 4y agoIt doesn't solve the same problem. They want to know if the password is in the file, not if the password could be in the file.
- twawaaay 4y agoYou can set up bloom filters for arbitrary false positive probability.
- lern_too_spel 4y agoNot 0.
- twawaaay 4y agoArbitrary rate means you can set it up so that you don't have to worry about it in practice. If I served a site where people could check if their passwords leaked I would not worry if one in a million viewers got a false positive.
- lern_too_spel 4y agoAs I said, "not worrying about it in practice" isn't "the same problem." If that is hard to wrap your mind around, you can suppose a fine of $1 billion for every wrong answer.
- twawaaay 4y agoEngineering is all about tradeoffs. In real life things never work 100% reliably. Not being able to do tradeoffs disqualifies person as an engineer. plonk
- lern_too_spel 4y agoAlgorithms are about correctness. Being incorrect disqualifies an algorithm as a solution to a problem.