A journey to searching Have I Been Pwned database in 49μs
stryku.pl
stryku.pl
It's worth noting that haveibeenpwned's API has a really clever design for allowing people to look up their passwords without transmitting them to the site.
It's explained here: https://www.troyhunt.com/ive-just-launched-pwned-passwords-v...
The short version is that you can take the first 5 characters of a SHA-1 hash and hit this endpoint:
https://api.pwnedpasswords.com/range/21BD1
The endpoint returns (right now) a list of 528 full hashes along with counts. You can compare your full calculated SHA-1 hash to that list to see if the password is present in the dump.
The trick here is called k-Anonymity - I think it's a really elegant solution. This technique is written up in more detail here: https://blog.cloudflare.com/validating-leaked-passwords-with...
E.g. 512-bit SHA-2 and SHA-3 may be truncated at 128 or 256 bits if that’s all the entropy you need (and you don’t need to be compatible with the formal SHA2/SHA3-512/256 spec). Here, CloudFlare is truncating to an intentionally low entropy of just 20 bits, not to reduce the security but rather to intentionally increase the collisions. It’s ultimately just a glorified hash table and as any CS student can tell you, the bucket size is just a function of the hash size (v1 of the api: 128-bit hash, v2 of the api: 20-bit hash).
(I don’t like pretension.)
Pretentious: adjective. characterized by assumption of dignity or importance, especially when exaggerated or undeserved: a pretentious, self-important waiter. making an exaggerated outward show; ostentatious. full of pretense or pretension; having no factual basis; false.
If you're suggesting that their analysis is false, you should probably point out why. The self importance part I'm not seeing. Aren't they just stating the facts as they see them?
If you assume that everyone who is dismissive is actually wrong and just pretending to know stuff, then I guess being dismissive is pretentious.
The reply could very well be interpreted as "You think that Kk-Anonymity is fancy? How primitive of you. This way is the natural way of doing that thing and I would know because I'm the smartest person in the room. Oh by the way I dislike people who are pretentious."
The not-remotely ingenious part was regarding Cloudflare.
I bet most people who haven't thought about it beforehand or heard the solution, would fail an interview question as "So, we have a database of 100s Million passwords and we want the user to check if his password is inside; without the user actually sending his password.. or his hash; without us outright revealing all our passwords/hashes to the user."
Their solution is a pretty good tradeoff imho.
It's also similar to how we spread mail folders in the past to avoid large directories. Or how Debian splits repo by package prefix: http://ftp.us.debian.org/debian/pool/main/
But then they wouldn’t have been able to give it a fancy name if they called it what it is.
Pwned Passwords chooses prefixes short enough that any password you wonder about will cause a prefix to be looked up that has lots of Pwned Passwords in it. Was one of them yours? Only you know, this is k-Anonymity.
Safe Browsing chooses prefixes long enough that many sites you look at won't match anything at all. There is still arguably k-Anonymity because the total number of possible URLs is so vast, but that's not their main goal.
And sure enough:
214943DAAD1D64C102FAEC29DE4AFE9DA3D:2413945
Wow, 2.4 million for "password1". Apparently "123456" is the most common password of all time. Even random phrases and memes I tried were pwned, like "The Lord of the Rings" and "correcthorsebatterystaple"
"The Lord of the Rings" and "correcthorsebatterystaple" match but similar truly random phrases do not, I picked these without looking:
This Duke and Some Circles
impossiblegoosecheesebinder
Sure enough neither of them was in the dataset.
Give it a week...
A long hash will identify your password very precisely.
A very short hash e.g. down to 1 byte will have so many matches to be useless.
Cloudflare chose:
> For example; the Hash Prefix 21BD1 contains 475 seemingly unrelated passwords, including:
...and this allows attackers to easily create a list of short hashes of common passwords and try them against matching accounts, as they point out:
> It is important to note that where a user's password is already breached, an API call for a specific range of breached passwords can reduce the search candidates used in a brute-force attack
I have a suspicion the answers is no due to the way DNS lookup is recursive and so all dns servers would have to implement the protocol. Would there be a way to make this work?
If you use the API to look up one of you passwords and it turns out to be pretty poor, then the service knows you're highly likely to have been looking up the top (by count) result, so now has the password and your IP address. I appreciate this service provider is well respected, but still, this is also worth noting.
a) Hashes are constant size (20 bytes for SHA1)
b) You only care if they're present or not in the database. There's no associated variable length data.
The simplest yet very efficient format is simply a sorted array of "byte[20]", with binary-search as the lookup. No headers, no pointers, no custom format of any type. Literally just 20 x n bytes where 'n' is the number of hashes. Lookup of the 'n-th' hash is just multiplying 'n' by 20.
If you really, really want a B-Tree (why?), just stuff it in any database engine. Literally anything will handle a single fixed-length key lookup efficiently for you.
CREATE TABLE "HIBP" ( "SHA1" BINARY(20) PRIMARY KEY );
SELECT 1 FROM "HIBP"
WHERE "SHA1" = 0x70CCD9007338D6D81DD3B6271621B9CF9A97EA00
You can trivially query databases from both web apps and CLI tools, and you can do this with batch queries too. E.g.: WHERE "SHA1" IN (... list... )
PS: Text-based tools (such as most shell tools) suck at this type of binary data. The newline terminated hex representation is 41 bytes per hash, so just over double the required size. Clever 5-10% prefix compression tricks pale in comparison to not doubling the data size to begin with.
PPS: A pet peeve of mine is older Java database "enterprise" applications that use UCS-2 "nvarchar" text columns in databases to store GUID primary keys. The 16 byte GUID ends up taking a whopping 78 bytes to store!
This query is just a key lookup, so the response time is likely to be well under 10ms even if you're not trying very hard to be efficient.
If using a stored procedure or a prepared query with persistent connections it'll be most likely be under 1ms if the data is stored on SSDs or in-memory. In this binary format, you need about 6 GB.
For some scenarios such as small cloud web servers, fast storage or lots of ram may not be viable. So if you're storing this on mechanical drives, the random nature of hashes means that for practically all queries the db engine will be walking the B-Tree pages and then the random I/O seek latency will dominate.
Some quick back-of-the-envelope maths: You can fit roughly 300 hashes into a typical 8KB page, as used by MS SQL Server as a random example. That means it'll build a 4-level B-Tree index for the HIBP database.
Unless you have less than 1 GB of memory, the first 2 index levels will become cached, leaving 2 random seeks for each lookup. At a typical 3-5ms, this is about 6-10ms of disk I/O latency, which will likely dwarf all other overheads.
Now keep in mind that the OP was trying to optimise a workflow that took 33 seconds originally!
Using a proper database has a ton of other benefits. For example, it becomes trivial to fit into modern asynchronous web application programming frameworks as yet another async call. Literally 1 line of code using Dapper or something along those lines.
Cheap writes, in an OLTP sense?
I had a similar problem recently: discovering "everything" in a DHT (= asking each node for everything it has), and feeding the resulting documents into a message queue for processing, without wasting resources processing each object's thousands of duplicate copies found distributed in the DHT.
These objects had no natural key, so I had to use a content hash for deduplication. And there was no way to time-bound the deduplication such that I could bucket objects into generations and only deduplicate within a generation. I needed a big fat presence-set of all historical hashes; and I needed to add new hashes to it every time I found a new unique object.
B-Trees have a good balance of read- and write-performance, which is why they're used for database indices and (usually) as the lower-level persistence strategy of key-value databases.
> PPS: A pet peeve of mine is older Java database "enterprise" applications that use UCS-2 "nvarchar" text columns in databases to store GUID primary keys.
Endorsing this point and boosting it: DBMSes really haven't thought out how to efficiently store large identifiers.
For example, a DBMS could suggest that clients feed it UUIDv1s, and then break them down into separate hidden {mac:48, timestamp:60, clockseq:14} columns, enabling per-column compression. (In most installations I've encountered, there's only one client generating UUIDs for the DBMS anyway, so these would compress really well, in fact enabling a default packed format where the timestamp + 5 bits of clockseq are kept in a 1-bit-tagged uint64; and the full value-size is only needed for exceptions.)
Sure, but HIBP is most certainly not an OLTP workload. It is updated infrequently as a batch process. The official mirror was last modified in July 2019!
Whenever a "new set" of millions of passwords are leaked, the HIBP maintainer(s) merge it with their existing data set of millions of passwords.
The "update" process is to download the new data set... and that's it. It's already sorted.
The only step I'm suggesting is to simply convert the pre-sorted HIBP SHA1 text file to a flat binary file. This takes a constant time and requires only a tiny buffer in memory.
This 1000x.
I really wish SQL Server had a "hash key" type where the hash is SHA512. You could then use anything as a primary key or an index, irrespective of size.
https://gist.github.com/timmc/df5fbb6e069fb8c1c4e181a29930ac...
I didn't bother with using binary keys, and just used hex, because I couldn't be arsed to do something more than `.mode csv` and `.import hashes.lst hashes` at the time, but it would be easy to write a tiny Python program to halve the space, as you say.
2. There's nothing over engineered about a B-Tree. It's a simple, well understood data structure which solves this exact problem.
3. There are meaningful differences in what you can do with a solution that gives you answers in microseconds vs milliseconds, as the blogger mentions.
Of course it works. You don't have to literally load the whole file into memory as an array. That's not how file I/O works! Just fseek() to the desired multiple-of-20 address and read 20 bytes.
> You could try mmap'ing the file
You'd only try that if you haven't read the documentation for mmap, just like a bunch of Rust programmers did. They started on 64-bit machines and never noticed that mmap is limited to a ~256MB window on most 32-bit architectures. Certainly less than the 11GB needed for this problem!
> There's nothing over engineered about a B-Tree.
Yes there is. This guy hand-rolled 400+ lines of low-level data structure manipulation code just for the B-Tree manipulation. How much do you want to bet that he's got zero memory safety issues or other unsafety in that thing?
Would you link this to your web app? Really, a C++ library?
> That gives you answers in microseconds vs milliseconds
I don't want to call him a liar... but now I have to. At the very least, he's made fatal mistakes in his benchmarking.
There is no way that he can do random password lookups from on-disk structures in under 50 microseconds, unless he's got an Intel Optane SSD, and even then I would be highly suspicious.
He's either cached the entire data structure in memory (at which point why bother with such a complex solution), or he's used the same set of passwords over and over for testing (which will falsely show a much lower latency than you would get with real passwords).
So answer me this: How would this solution work on a typical auto-scale cluster of stateless web server VMs? Do you replicate 5-12GB to every VM every time this database changes? Or do you put one copy on a network share? Congratulations, you now have 1ms latency minimum! That fancy microsecond optimisation has just gone out the window...
To be blunt: If your password-testing is the bottleneck to the point that a 50 microsecond latency is needed, then you're running a service that gets 20,000 password resets per second. At this point you're bigger than Office 365 and G Suite... combined, and you likely have much more important scaling concerns.
Do you have a reference for that? I've never heard of this and I can't imagine the reason for such a limitation.
..although in practive it might be hard to find 256MB of contiguous memory in a 4GB virtual memory space due to fragmentation of other allocations and shared libraries, especially with ASLR.
There's the hard limit of 2GB for most versions of 32-bit Windows and 4GB for any operating system.
Couple that with the requirement for a contiguous address space as well as various page table entry (PTE) limits, you get all sorts of "soft" limits way before 2GB. From what I've heard, 256MB is relatively safe to map, but anything much larger than that is increasingly likely to fail.
Correctly written code should be able to work with moveable "windows" into the file as small as 32MB to be properly robust, especially if the process memory is already fragmented.
Lots of software crashes with large files on 32-bit machines because of this. E.g.: https://www.monetdb.org/pipermail/users-list/2009-January/00...
As a more recent example, ripgrep had issues on 32-bit platforms because of a bug in the way the underlying mmap library worked in Rust.
Even on 64-bit platforms you can run into trouble. For example: https://jira.mongodb.org/browse/SERVER-15070
In that example, Windows Server 2008 R2 has an 8 TB limit. You could hit that if using a tool like ripgrep to do "forensic analysis" of disk images from a SAN, where virtual disks typically have 16 TB limit. So if you mount a SAN snapshot and open the disk as a file to scan it, you will hit this limit!
Programmers make all sorts of invalid assumptions...
ripgrep has always had a fast traditional buffering strategy using `read` calls for searching, because I knew that mmap couldn't be used in every case.
Anyway, this has been fixed for a couple years at this point, so if you're still experiencing a problem, then please file a new bug report.
> As a more recent example, ripgrep had issues on 32-bit platforms because of a bug in the way the underlying mmap library worked in Rust.
This is false. The bug you're thinking about is probably https://github.com/BurntSushi/ripgrep/issues/922, which was not caused by an underlying bug in memmap. memmap did have an underlying bug with respect to file offsets, but ripgrep did not use the file offset API. The bug was caused in ripgrep itself, since I made the classic mistake of trying to predict whether an mmap call would fail instead of just trying mmap itself. That bug was fixed on master before the Windows bug was even reported: https://github.com/BurntSushi/ripgrep/commit/93943793c314e05...
> You'd only try that if you haven't read the documentation for mmap, just like a bunch of Rust programmers did.
This isn't exclusive to Rust programmers. C tools make the same mistake all the time. Because memory maps aren't just problematic with large files on 32-bit systems, but they also don't work with virtual files on Linux. Try, for example, `ag MHz /proc/cpuinfo` and see what you get. Crazy how, you know, sometimes humans make mistakes even if they are a C programmer!
And the implication that I (or the author of memmap) never read the docs for `mmap` is just absurd.
If you're going to be snooty about stuff like this, then at least get the story correct. Or better yet, don't be snooty at all.
The specific issue making the "mmap" crate incorrect was that it used a "usize" instead of "u64" for some of the functions, limiting it to 4GB files on 32-bit platforms. I believe it's this line of code: https://github.com/rbranson/rust-mmap/blob/f973ae1969b4b7e80...
Now, I'm not a mindreader, but to me this feels an awful lot like its author made a tacit assumption that mmap() is a "memory operation" that is tied to the architecture's pointer size. In similar conversations, heck, in this very discussion people were incredulous that a file can be bigger than memory and be processed.
I absolutely believe that people do not read much past the function declarations, and it might be a "snooty attitude" but experience unfortunately has shown it to be an accurate attitude.
I'm also not accusing you of incorrectly using mmap(), buuuuut... having a quick flip through your current code I see that you still have the attitude that "mmap() takes a filename and makes into a slice that the kernel magically reads in for me on demand".
This is just not true, not even on 64-bit platforms. On smaller devices with only 2-4GB of memory, it's entirely possible to simply run out of page table entries (PTEs). It's possible the memory space simply gets too fragmented. It's possible the kernel has other limits for processes. It's possible the that file is some virtual device with an enormous reported size. Etc, etc, etc...
The correct usage of mmap() is to use moderately-sized sliding windows of, say, 128MB at a time or whatever.
But, having said that: Your code is now correct in the sense that it won't crash, it won't have unsafety, it'll run on 32-bit just fine, and will probably work for all practical scenarios that people want to use a grep tool for. I also know that you have specific optimisations for "the whole file fits in a byte slice", so there's benefits to using the simple approach instead of a sliding window.
However, if this was a database engine that required mmap() to work, it would be absolutely incorrect. But it isn't a database engine, so no big deal...
I don't understand why you're saying this. Could you point me to the place in the commit history where I used the `mmap` crate? The second commit in ripgrep's history is what introduced memory map support and it used the `memmap` crate: https://github.com/BurntSushi/ripgrep/commit/403bb72a4dd7152...
> albeit the CPU fan noises annoy my co-workers
ripgrep is happy to be told to run more slowly with `-j1`.
> I absolutely believe that people do not read much past the function declarations, and it might be a "snooty attitude" but experience unfortunately has shown it to be an accurate attitude.
This sounds to me like "I'm right so I can be as much of an arse as I want." Just don't be snooty about this. Sometimes I can read a man page thoroughly and still come away from misconceptions. Sometimes the docs are just bad. Sometimes it's just very dense. Sometimes there's a small but important detail that's easy to miss. Or sometimes I'm just not smart enough to comprehend everything. Instead of getting up on your holier-than-thou perch, maybe tone it down a notch next time.
> I'm also not accusing you of incorrectly using mmap(), buuuuut... having a quick flip through your current code I see that you still have the attitude that "mmap() takes a filename and makes into a slice that the kernel magically reads in for me on demand".
Not really. Especially since ripgrep's man page explicitly calls out memory maps as potential problem areas, and even gives users the option to avoid the issue entirely if they like:
> ripgrep may abort unexpectedly when using default settings if it searches a file that is simultaneously truncated. This behavior can be avoided by passing the --no-mmap flag which will forcefully disable the use of memory maps in all cases.
But, invariably, one of the nice things about memory mapping a file is precisely that it "mmap() takes a filename and makes into a slice that the kernel magically reads in for me on demand." And it generally pretty much works.
> However, if this was a database engine that required mmap() to work, it would be absolutely incorrect. But it isn't a database engine, so no big deal...
It's good enough where SQLite actually provides an option to use memory mapped I/O (noting pertinent downsides): https://sqlite.org/mmap.html Lucene also provides it as an option: https://lucene.apache.org/core/6_3_0/core/org/apache/lucene/... --- They likely both do the windowing you're talking about, but as the SQLite docs mention, that's not enough to stop it from crashing and burning.
At that level, it's good enough for ripgrep and it sure as hell is good enough for a random fun project like the one the OP posted. Absolutely no reason to get on your soapbox and snub your nose.
That's interesting, but processing more than 4gb of data on a 32bit systems seems pretty niche, these days? Where do you find them outside of industrial embedded applications? I think even my long discarded smart watch ran 64bit.
Now, vfat filesystems will bite you (Esp for removable media), but that's also fixable with some other fs, like xfat or zfs.
You're right. The benchmarks are bad. I benchmarked the best and the worst case in scope of the original file, so I look up for the first and the last hash.
I totally missed that if I look for the same hash over and over again, I'd end up reading the same B-tree files parts, so they can be easily cached. That's probably the reason it seemed so fast.
No lies here, I just missed this (:
I'll rewrite benchmarks and update the results.
Roughly, instead of picking at 1/2 every time, you pick b/256 in, where b is the current byte value. That gets you log log n search. (You can of course pick 2 bytes, or 3, or...)
The fastest method would be to treating the 20-byte hash as a floating point number in the range 0.0 and 1.0. This would let you use Newton's iteration method to very accurately guess the approximate location in the file and then narrow it down from there. By reading small blocks of 0.5-4KB you could probably get to the required hash in just 1-2 reads, which is either optimal or very close to it.
Do clever things to simple data!
Multiply this by the number 'n' hashes in your file, and it'll very closely approximate its ordinal in the list, because as you said hashes are equidistributed very well.
Now multiply this ordinal by 20 and load a small slice of the file a few KB to either side of where you're aiming so that there's essentially a 100% chance of finding the hash in one "random read" operation.
If not, you now have a block of hashes that is close, but not quite what you want. You can use the floating point conversion trick to see "how far away" you are, calculate a more accurate estimate and do a second read. It's very unlikely you'd need a third read step.
In general, I rejected all approaches that operates on a sorted file. That's simply because keeping the file sorted is slow, when you need to insert more data in the future. With B-tree approach, you have fast searching, as well as, inserting. That's the reason.
Sorting a handful of gigabytes was a solved problem over 20 years ago. Sorting a file using an "online" operation like row-by-row insertion in a B-Tree is necessarily slower than any offline sort. Merge sort is particularly efficient with data that won't fit on disk.
If you do need "online" operation, a real database engine provides this (and more) for practically zero effort. It's almost as if... they were designed for this purpose!
Yes, you're right that sorting data using B-tree is slower than other methods. But I don't use it only for sorting. It's not like 'create B-tree and forget about it'. You create the tree from initial data, and if you need to insert any more hashes there, you can do it really quickly, without a need to sort everything again.
I agree again. If I'd create okon only for my home usage, I'd probably use a real database. But I didn't want to depend on anything. I wanted to create a library that can be used by any program and just works, without forcing user to install anything else. That's why I sort the data on my own, and that's why I implemented B-tree on my own. Everything is in okon's codebase.
The purpose of the tool and the library is to be a complete solution for this one thing. The user can grab the binary and just use it, without installing/using any database under the hood.
So either the whole file fits in RAM and you pre-load it (in which case you have to account for that memory usage), or you have to run benchmarks on random hashes, which would yield much slower numbers (on the order of 30ms for an HDD).
Personally, when I implemented this in a web service, I used a bloom filter. It has some false positives (tunable) and requires a few extra disk reads per check, but the resulting file is also smaller and the code to generate it and check it is very, very simple.
https://gist.github.com/marcan/23e1ec416bf884dcd7f0e635ce5f2...
P.S. if you need to sort a huge file, just literally use the UNIX/Linux `sort` command. No, it does not load it all into RAM. It knows how to do chunked sorts, dump temp files into /tmp, and then merge them. Old school UNIX tools are smarter than you think.
This so much.
I’ve worked with many devs and admins that don’t understand the tools that they have at their disposal on their systems. They end up trying to reinvent the wheel and their solutions usually don’t consider all the edge cases
time gsort --parallel=2 -o $HOME/pwned-pass-sorted.txt pwned-passwords-sha1-ordered-by-count-v5.txt
2890.06 real 1400.86 user 165.54 sys
`gsort` is GNU sort on coreutils (not the one included on macOS).
This is on a Mac Mini 2011 (5,1) with the 2.3GHz i5.
They really have a lot of things built into these tools :)
HDD latency is composed of seek + rotation latency + processing time, on the best of the best server HDDs random read might be in the ballpark of 10ms (10,000μs), desktop HDD... maybe around 30-40ms (30,000μs). Or ~600x times more than 49μs.
I'm not a professional programmer, but I would have supposed a bloom filter is in this case equivalent to just saving the first n bits of every sha1 hash. Is that wrong?
But really, hashing is so cheap there's no point in trying to be clever like this for an on-disk implementation. My code is designed to take any strings as input, whether they are HIBP hex hashes already or something else. If this were intended to be a high performance in-memory implementation used for a database or something, the constraints would be different.
We can use this set of prefixes to filter the data. Given an input hash, check whether its prefix is in the table. If it's not in the table, the prefix is certainly not in the file. If the prefix is in the table, there is a 1/8 ~ 13% chance of a "false positive" where the query is not actually in the file, but the set thinks it is.
What a Bloom filter does is start using the rest of the hash, by storing the presence of the next 32-bits of the hash in the same set, and so on. By storing the next 32 bits as well, we can drop the false positive rate to 6%. By using the next chunk of 32 bits, it drops again to 4%, and finally when storing 5 32-bit chunks (very conveniently, we have at this point "used up" all 32-bit chunks of our original 160 bits) to around 2.5%. All the while, the bloom filter is fitting into the same 512MB we originally gave it.
Pwned passwords 2.0 was half a billion passwords. That's 29 bits. To get a 0.05% false positive rate you need an additional 11 bits or so. That's 40 bits per hash, or 20 billion bits total, and then you need to binary search it (29 lookups) or make it into a tree and add bookkeeping structures.
The equivalent performance bloom filter only takes 5 billion bits of storage and 11 single bit checks in a bitmap.
When I was working on blocking leaked passwords, I found projects using bloomfilters for this (e.g. Keycloak). I find false positives completely unacceptable from a user experience perspective.
Blocking a perfectly fine password is playing with the users mind. If he cares even a little, he will wonder what is wrong with his password (was it leaked???) and if the answer "false positive" isn't available to him it's just evil.
A bloom filter is a good tool to filter out the negatives (which should hopefully be the majority of passwords), but please run all positives against the full set.
But if you're using it as a way to prevent people from using known-breached passwords on a site/service, it's really not worth worrying about. False positives would only be a problem when the user is using bad password practices anyway. If it's a non-shared, random password like it should be, a tiny chance of blocking an acceptable one is fine. They can just generate another one, it's an extremely minor inconvenience at worst.
Just include a note in the error message saying something like, "In very rare cases, this could be a false positive. Even if it is, you must choose a different password." The 0.1% of users it impacts (or whatever your error rate is) will be fine.
Even if you display there is a minor chance of a false positive, your user must now think 0,1% this was a false positive or 99,9% my password was leaked! I don't want users to panic if there is no reason to and I don't want users to blame false positives if there is reason to panic. I think it's definitely worth worrying about.
Also research has shown that forcing users to regularly change passwords leads to weaker passwords. And as many (most?) users are not using password managers (yet) expecting a different secure (i.e. long enough, non dictionary) password is too far from reality.
The database only lists the SHA hash of passwords which have been found in various datasets and the occurrence count. It does not indicate that the matching password (one of half a billion) has ever been associated with the user account.
The fault in knowledge schemes is oversharing the secret. However, there is no way to know for sure that the user has done this by reusing passwords - you will have false positives (say, one other person on the internet chose this password by chance) and false negatives (the user has reused the password all over the place, but has managed to not be part of a known breach dataset).
If this were a bigger service, yes, I would've done an exact check afterwards :-)
I run a separate Redis server specifically for this purpose, which means when I want to update the list, I can build the Bloom filter on my local machine, and then just transfer the RDB file to the server and replace the previous one.
Here's the Python code for the simple CLI tool to initialize and add the hashes from the HIBP files to the Bloom filter if anyone's curious: https://gitlab.com/tildes/tildes/-/blob/master/tildes/script...
To check if a password's in the list, you just SHA-1 hash it and send a Redis command like:
BF.EXISTS breached_passwords_bloom <sha1>You're right. As I said in some comment up there, the benchmarks are bad. I benchmarked the best and the worst case in scope of the original file, so I look up for the first and the last hash.
I totally missed that if I look for the same hash over and over again, I'd end up reading the same B-tree files parts, so they can be easily cached. That's probably the reason it seemed so fast.
I'll rewrite benchmarks and update the results.
About the Bloom filter, I thought about that but I wanted a solution that is 100% correct. The filter doesn't guarantee that.
About the sorting. I wanted to implement a stand-alone library that does everything for you and that is cross-platform. That's why everything is implemented, without dependencies/usage of other tools.
https://en.wikipedia.org/wiki/Interpolation_search for example can achieve O(log log n) performance under the uniform distribution assumption which is order of magnitudes faster for this scale of data. Another trick is to start with interpoluation search and then switch to binary search once the sample size gets small enough.
I'm not sure about that, but this seems like a fun problem for exploration. Also, 49µsec sounds like a pretty easy target to beat.
I used the following in q to build a data set I could play with:
\wget https://downloads.pwnedpasswords.com/passwords/pwned-passwords-sha1-ordered-by-hash-v5.7z
\7z -so e pwned-passwords-sha1-ordered-by-hash-v5.7z pwned-passwords-sha1-ordered-by-hash-v5.txt | cut -c1-40 | xxd -r -p > hibp.input
`:hibp 1: `s#0N 20#read1 `:hibp.input
q)hibp:get`:hibp; / this mmaps the artefact almost instantly
q)\t:1000 {x~hibp[hibp bin x]} .Q.sha1 "1234567890"
5
So, if binary search is fast enough, how much faster should an Interpolation search be? My understanding is that an Interpolation search will make a better initial guess than a naive binary search because it can start "closer" to the correct value but it'd only work at all if the input had an extremely even distribution so it can guess that initial starting point to reduce the search space, so let's check that first:
q)count each group hibp[;0]
00| 2171182
01| 2171242
02| 2170869
03| 2168638
04| 2171675
05| 2171500
06| 2169285
07| 2171129
08| 2171463
09| 2173704
0a| 2173702
0b| 2169950
0c| 2169562
0d| 2172129
0e| 2171763
0f| 2173154
10| 2170242
11| 2168806
12| 2172306
13| 2171502
14| 2170208
15| 2167949
..
q)t:(0,sums value count each group hibp[;0]) _ hibp
q)`:t 1: t
q)t:get`:t / no cheating! back to the disk!
q)\t:1000 {x~g(g:t[first x]) bin x} .Q.sha1 "1234567890"
5
It’s probably not the fastest possible algorithm (though likely faster than what the author obtained), but it plays much better with memory than naive binary search and the storage format doesn’t have any overhead.
The input SHA-1 provides 160 bits of hash. If we divide that up into 5 hash values of 32 bits, we can get a 3% false positive rate with a 483 MiB Bloom Filter (which will easily fit in memory).
https://hur.st/bloomfilter/?n=555M&p=0.03&m=&k=
This will be blindingly fast. We're talking 5 random reads from memory. Even in the worst case of 5 cache misses, we're still well under 1us. This will let us return "not found" for 97% of inputs that aren't in the database.
If we get a hit there, then we could turn to a larger bloom filter for greater accuracy, but we'd have to actually hash the key to get more hash bits.
Of course if you get hits for all your bloom filters, you still have to do a real lookup to positively confirm that the key is in the database.
As I replied elsewhere, please do not ignore this part for good user experience. I've seen it ignored in open source projects (Keycloak). You don't wanna block perfectly fine passwords for reasons unknown to the user because of false positives. That might cause unwanted reactions at your user's side ("was my password leaked!?!?").
A single string of that length is extremely easy to search for with a range of different algorithms - I would be surprised if a decent approach couldn't keep up with memory bandwidth (assuming your 22GB file is already, somehow, in memory). The mechanics of simply reading such a big file are likely to dominate in practice.
We implemented some SIMD approaches in https://github.com/intel/hyperscan that would probably work pretty well (effectively a 2-char search followed by a quick confirm) for this case.
Of course, that begs the question - presupposing that any kind of whole-text search is actually the answer to this question. The end result - assuming that you really do have more than a few searches to do - of keeping the results in any kind of prebuilt structure - is way superior to an ad hoc literal search.
The FM Index is ideally suited to the problem of repeatedly searching a large fixed corpus for many different short substrings, and achieves optimal time complexity: linear in the length of the substring, with excellent constants independent of the length of the corpus (!).
Some years ago undertook a very similar exercise to that of the author except using the leaked Adobe password data rather than the HIBP data, and found the FM Index worked well: http://olivernash.org/2014/01/03/dna-of-a-password-disaster/...
[1]: https://github.com/tylerchr/pwnedpass/blob/master/README.md#...
It might be superior to the articles methods if you only want to search for a few.
$ dd of=pwned-passwords-sha1-ordered-by-hash-v5.txt oflag=nocache conv=notrunc,fdatasync count=0
0+0 records in
0+0 records out
0 bytes (0 B) copied, 9.5864e-05 s, 0.0 kB/s
$ time look `sha1sum <(echo -n password) | tr [a-z] [A-Z] | cut -d" " -f1` pwned-passwords-sha1-ordered-by-hash-v5.txt
5BAA61E4C9B93F3F0682250B6CF8331B7EE68FD8:3730471
real 0m0.137s
user 0m0.002s
sys 0m0.013s
sudo purge
time look E38AD214943DAAD1D64C102FAEC29DE4AFE9DA3D pwned-passwords-sha1-ordered-by-hash-v5.txt
E38AD214943DAAD1D64C102FAEC29DE4AFE9DA3D:2413945
0.01 real 0.00 user 0.00 sys`
If you are okay with false positives, you can use a bloom filter and tune the number of false positives you want. I chose a false positive rate of 1 in a million so my data structure was still very accurate in determining whether a password was already hacked.
It only took 30 microseconds to determine if a password was in the list and for size, was at the theoretical limit of 22 bits per element or ~1.5gb.
I originally used a bloom filter which made it 2gb but given a bloom filter was just a sequence of 0s and 1s, I was able to use a golomb coding to shrink it down to 1.5gb.
The time to process the original 24gb however, is something that I could have improved, but I kinda lost interest once I already had something that was at the theoretical minimum size, as well as able to determine a password exists within 30 microseconds.
Anyways take a look if you're interested in trying a different approach: https://github.com/terencechow/PwnedPasswords
I'm not entirely sure I'm sold on the speed gained by splitting files vs doing a simple seek operation to an offset [1]. There's probably a bunch of time lost searching the filesystem through a file/folder structure?
Also the simple act of converting the numbers from ASCII to binary should save a bunch of disk space too (and make searching quicker)?
Great write-up though, good to see a bunch of solutions tried.
But an index file of 64-bit offsets could easily be seeked to read the value of the offset based upon the first 2 or even 4 byte offset.
Though with 4 bytes, that becomes a 4 gigabyte index file! But that would probably be much faster as you only do one seek in one file, then another seek to the main file, then search a much shorter distance to the result!
If the system has enough ram, the operating system will cache the files anyway and will be pretty fast i think.
(can you tell my first job involved writing ad-hoc database systems?)
The original version has the limit of 4gb, but there are 64b versions as well - for example https://github.com/pcarrier/cdb64?files=1
I have often used a dictionary to store tries to prevent this kind of memory usage–it's auto-resizing, if slightly slow. But hey, you're chasing pointers anyways, so it's not like going through the tree was going to be fast anyways…
(I'm also curious about the "scumbag Steve" hat on the B-tree, but I digress.)
https://github.com/adewes/have-i-been-bloomed
Very fast and highly space efficient as well, 17.000 requests per second on a conventional laptop with 1.7 GB memory required at a false positive rate of 1:1.000.000 (and no dependencies on databases or anything else).
Classic uncompressed trie sucks pretty much in all cases.
Now if we go for half-decent implementation of packed variation, it does get significantly better:
That said, 49us is very impressive. Hard to beat low level custom coded solutions.
Challenge accepted!
I used the following in q to download and load the data into a disk object I could mmap quickly:
\wget https://downloads.pwnedpasswords.com/passwords/pwned-passwords-sha1-ordered-by-hash-v5.7z
\7z -so e pwned-passwords-sha1-ordered-by-hash-v5.7z pwned-passwords-sha1-ordered-by-hash-v5.txt | cut -c1-40 | xxd -r -p > hibp.input
`:hibp 1: `s#0N 20#read1 `:hibp.input
q)hibp:get`:hibp; / this mmaps the artefact almost instantly
q)\t:1000 {x~hibp[hibp bin x]} .Q.sha1 "1234567890"
5
Memory usage is quite high, around 95 bytes per element, bu I'm sure that by spending more than 5 minutes on it, like I did, one can take it down considerably
For reference, this is the code I used
I converted the SHA hashes to MD5 to save memory, given we don't care about collisions (which are very unlikely anyway), we just want to know if the password was there or not.
defmodule Pwned do
def load do
:ets.new(:table, [:named_table, :set])
File.stream!("pwned-passwords-sha1-ordered-by-hash-v5.txt")
|> Stream.each(fn line ->
<<hash::binary-size(40), ":", _rest::binary>> = String.trim_trailing(line)
hash = :crypto.hash(:md5, Base.decode16!(hash))
:ets.insert(:table, {:binary.copy(hash), true})
end)
|> Stream.run()
end
def lookup_hash(hash) do
hash = :crypto.hash(:md5, Base.decode16!(hash))
case :ets.lookup(:table, hash) do
[] -> false
_ -> true
end
end
def lookup_password(password) do
lookup_hash(:crypto.hash(:sha, password) |> Base.encode16())
end
endHere's my load script:
\wget https://downloads.pwnedpasswords.com/passwords/pwned-passwords-sha1-ordered-by-hash-v5.7z
\7z -so e pwned-passwords-sha1-ordered-by-hash-v5.7z pwned-passwords-sha1-ordered-by-hash-v5.txt | cut -c1-40 | xxd -r -p > hibp.input
`:hibp 1: `s#0N 20#read1 `:hibp.input
q)hibp:get`:hibp; / this mmaps the artefact almost instantly
q)\t:1000 {x~hibp[hibp bin x]} .Q.sha1 "1234567890"
5