13 ms·

A journey to searching Have I Been Pwned database in 49μs

333 points by stryku2393 7y ago

7532yahoogmail 7y ago
Nicely done and explained.
dvasdekis 7y ago
I respect that the author learnt the underly concepts, which are not simple. But is the net result truly that the default Postgres index method was perfectly suitable for this use case?
- stryku2393 7y ago
  Thanks (: About the Postgres, I wanted to create a library and a CLI without dependencies. I wanted them to be a complete tools for doing this one thing. Tools that you can just grab and use, without installing anything.
krackers 7y ago
If you were to just throw the file into a database, wouldn't the database's index essentially lead to the same result (b-tree, compacted using bulk-loading procedure).
- nightfly 7y ago
  I briefly had a Rocket/IRC bot that talked to a postgres instance with the HIBP DB loaded into it, and yes it worked great.
- stryku2393 7y ago
  True, but I wanted to create a library and a CLI without dependencies. I don't want to force an end user to install and use a database (even under the hood).
barrkel 7y ago
B-trees, with their trade-off between slow disk seeks and fast in-memory scans, make just as much sense for slow memory accesses and fast in-cache scans.
tylerchr 7y ago
I undertook a similar endeavor a while back. My solution[1] rested on the observation that you don’t need to have a B-tree to do a binary search; one need only be able to calculate the correct byte offset of the Nth hash. With some optimizations, this approach produced a 9.9GB file with similarly fast lookups. [1]: https://github.com/tylerchr/pwnedpass/blob/master/README.md#file-format https://github.com/tylerchr/pwnedpass/blob/master/README.md#...
- fwip 7y ago
  It looks like the link to your blog post is broken (at the bottom of the README).
  - tylerchr 7y ago
    Awkward! Thanks for the tip. I added a copy of that post to the repo and fixed the link.
simonw 7y ago
This is a really informative write-up and an excellent learning exercise. 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-version-2/ 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 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-k-anonymity/ https://blog.cloudflare.com/validating-leaked-passwords-with...
- camillovisini 7y ago
  Thank you for these resources. Truly ingenious.
- ComputerGuru 7y ago
  Honestly they’re being super mathematical about it but it’s really nothing fancy at all. SHA is designed to be used like this, CloudFlare hasn’t done anything remotely ingenious (and I wouldn’t mind except they go out of their way to talk about how much better their fancy new algorithm is compared to other multi-set intersection theories). 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.)
  - rmwaite 7y ago
    For someone who claims to not like pretension (sic), you're being pretty pretentious.
Avamander 7y ago
There was an app for Android phones that searched for default router passwords based on SSID using this method. It indeed was very fast, even on very bad hardware.
glangdale 7y ago
Any good literal search algorithm could do a one-off search for a single long literal 'needle' way faster than the roughly 1GB/s that the author attained with grep. 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 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.
lalaland1125 7y ago
You can actually do much better than binary search due to the uniform distribution of hashes. https://en.wikipedia.org/wiki/Interpolation_search 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.
- zamadatix 7y ago
  If you're going to sort the hashes then might as well make a jump table of the first n bits and a binary search from there.
  - thedance 7y ago
    Why do you even need the jump table? If the hash function is working you should get quite close just by dead reckoning.
- geocar 7y ago
  Much better? 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 This took about an hour to download, an hour to 7z|cut|xxd, and about 40 minutes to bake. At complete, I have an on-disk artefact in kdb's native format. q)hibp:get`:hibp; / this mmaps the artefact almost instantly q)\t:1000 {x~hibp[hibp bin x]} .Q.sha1 "1234567890" 5 Now that's 1000 runs taking sum 5msec, or 5µsec average lookup time! It's entirely possible my MacBook Air is substantially faster than the authors' machine, but I'm also doing a lot of other shit while this is going on so whilst I believe a better benchmark is possible, I suspect even better results under better conditions, not worse. 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 .. Ok that looks pretty even to me, so next I partition on the first byte to see if getting 99% closer (1-1/256) on our first guess gets us anything: 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 And it's still 5µsec for lookup! So I'm finding it difficult to believe there's "much better" in there. Do you have some benchmarks to look at?
jiggawatts 7y ago
This and other similar solutions seem awfully over-engineered. 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 There. I solved the blogger's problem in literally under 5 minutes without having to write a custom binary. 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!
- jakoblorz 7y ago
  Yet you pay the cost in speed when using a database engine, there is a big overhead.
  - jiggawatts 7y ago
    Meh. 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.
emmelaich 7y ago
Just to remind people of `look`, which does a binary search. It might be superior to the articles methods if you only want to search for a few.
- lolc 7y ago
  Funny how many tools are stowed on my system. I'll never know them all!
- xurukefi 7y ago
  Didn't know about look. Seems good enough (tested on a HDD): $ 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 dd is used to drop the file from the fs cache. Something the author probably didn't do given the unrealistic 49μs. It's simply not possible to fetch data from a HDD that fast.
  - stryku2393 7y ago
    True, the benchmarks are bad. I'll rewrite them (to drop the cache every time) and update the results.
- iseeyou 7y ago
  wow, thanks, yet another tool to remember in the toolbox sudo purge time look E38AD214943DAAD1D64C102FAEC29DE4AFE9DA3D pwned-passwords-sha1-ordered-by-hash-v5.txt E38AD214943DAAD1D64C102FAEC29DE4AFE9DA3D:2413945 0.01 real 0.00 user 0.00 sys` not 49us, but fast enough for most use cases (purge should clear the fs cache)
jonstewart 7y ago
In digital forensics we often have to do a hash set lookup as in this article. When the set is constant, you can sort it as the author did, and then perform a linear scan to determine the maximum error—i.e., how far away a hash value is from its expected location—and then use a reduced binary search/interpolation search, where the expected index is used as the midpoint and the maximum error is used to determine the window. On large hash sets of this size, the maximum error is still often measured in KB. 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.
- iomintz 7y ago
  I'm trying to implement this myself. How is the expected location computed? Is it just hash_as_int / max_sha1_hash * file_size?
saagarjha 7y ago
> A node is a simple structure of sixteen 32 bit values. The values are 'pointers' to next nodes, at given character of the SHA-1 hash. So, one node takes 16 * 4B = 64B. 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.)
_wldu 7y ago
You may also consider using a bloom filter to do this: https://github.com/62726164/bp https://github.com/62726164/bp
deleted 7y ago
[deleted]
ttt111222333 7y ago
I did something similar when I wanted to search the HIBP database and if you are okay with some false positives you can do better than your results, both in terms of speed and size. 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 https://github.com/terencechow/PwnedPasswords
marcan_42 7y ago
This is bad benchmarking. There is no way you're doing a b-tree lookup in microseconds on an on-disk file... Unless the parts you care about are already cached. 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/23e1ec416bf884dcd7f0e635ce5f2724 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.
- rovr138 7y ago
  > 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
  - saagarjha 7y ago
    Note that this does take a while; I let it go for about two hours before killing sort.
    - rovr138 7y ago
      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 48mins `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 :)
jadia 7y ago
While preparing for interviews, I use to wonder why do they emphasize so much data structures. This article proved them right and made me realize why data structures must be your muscle memory.
ThePhysicist 7y ago
Great writeup! Another way to query the DB are probabilistic filters. I wrote a Bloom filter based query API for this a while ago: https://github.com/adewes/have-i-been-bloomed 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).
QuadrupleA 7y ago
Cool learning exercise and fun read. Can't help but think SQLite could do this screamingly fast and very easily, with nice compact storage (blob primary key with the hashes, without-rowid table to avoid a hidden integer per row). That said, 49us is very impressive. Hard to beat low level custom coded solutions.
- geocar 7y ago
  > 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 This took about an hour to download, an hour to 7z|cut|xxd, and about 40 minutes to bake. At complete, I have an on-disk artefact in kdb's native format. I can load it: q)hibp:get`:hibp; / this mmaps the artefact almost instantly and I can try to query it: q)\t:1000 {x~hibp[hibp bin x]} .Q.sha1 "1234567890" 5 Now that's 1000 runs taking sum 5msec, or 5µsec average lookup time! It's entirely possible my MacBook Air is substantially faster than the authors' machine, but I think being ten times slower than an "interpreted language" suggests there's a lot of room to improve!
DmitryOlshansky 7y ago
> Trie structure sucks if you have pretty random words. 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: https://en.wikipedia.org/wiki/Radix_tree https://en.wikipedia.org/wiki/Radix_tree
haberman 7y ago
There are 555,278,657 passwords in the database. With a Bloom Filter, you could quickly rule out potential inputs. Even better, there is no need to hash the input, because... it's already a cryptographic hash. 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= 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.
- ascar 7y ago
  > 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!?!?").
  - haberman 7y ago
    That makes sense. I was thinking of this more as a fun algorithms optimization challenge, not something to actually put into a production setting with real users. I agree that for real users you would especially not want to skip the last step.
  - ThePhysicist 7y ago
    The false positive rate can be made arbitrarily small. I have an implementation with a fp rate of 1:1.000.000 with a filter size of just 1.8 GB (https://github.com/adewes/have-i-been-bloomed https://github.com/adewes/have-i-been-bloomed). The cost of lowering the rate is logarithmic so you could go to much lower values for little cost (1:1.000.000.000 would be 2.8 GB) so false positives are not really a problem in practice. If you really want you could still perform an exact check against a DB if the filter returns true to rule out false positives with certainty, though at one false positive for one billion requests this might be exaggerated.
aquadrop 7y ago
Why was data sorted by usage count in the first place? Hash of the password doesn't give you the password, so you just get "something was used x amount of times". Seems like you always want to look up by hash and then sorting by hash from the beginning makes more sense.
viraptor 7y ago
Another solution for cases where you don't add new entries all the time and can reindex the whole database every once in a while instead: use cdb. There's a nice description of the internals and how it works. http://www.unixuser.org/~euske/doc/cdbinternals/index.html http://www.unixuser.org/~euske/doc/cdbinternals/index.html It guarantees access in two disk reads. The original version has the limit of 4gb, but there are 64b versions as well - for example https://github.com/pcarrier/cdb64?files=1 https://github.com/pcarrier/cdb64?files=1
bArray 7y ago
Surely if you know that the hashes will have an ~even distribution you can quite quickly make some assumptions about roughly where the key will be? 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. [1] http://www.cplusplus.com/reference/cstdio/fseek/ http://www.cplusplus.com/reference/cstdio/fseek/
- dana321 7y ago
  Thinking about it, you would need a 64-bit value to point to the offset because of the size of the file. 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?)
ocfnash 7y ago
I love this write up, and while the solutions discussed are excellent, I think the general-purpose FM Index data structure might work even better. I confess I'd have to read this post more closely to be sure, but I find the FM Index data structure so appealing, I'm always looking for excuses to promote it! 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/index.html http://olivernash.org/2014/01/03/dna-of-a-password-disaster/...
chinesempire 7y ago
using ETS with Erlang (or Elixir) I get sub 50μs (30μs on avergae) lookup times. 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 end
- geocar 7y ago
  I agree these performance numbers don't seem great. Using q (another interpreted language; not compiled) I get 5µsec on my Macbook Air: Here'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 I can then shut down this process, and start a new one: q)hibp:get`:hibp; / this mmaps the artefact almost instantly q)\t:1000 {x~hibp[hibp bin x]} .Q.sha1 "1234567890" 5 It's so fast I need to run it 1000 times to take just 5msec (5µsec average lookup time!). I imagine converting to md5 would be substantially faster since there's a 16-byte scalar type in q I would be able to use.

333 points by stryku2393 7y ago

Nicely done and explained.

I respect that the author learnt the underly concepts, which are not simple. But is the net result truly that the default Postgres index method was perfectly suitable for this use case?

stryku2393 7y ago
Thanks (: About the Postgres, I wanted to create a library and a CLI without dependencies. I wanted them to be a complete tools for doing this one thing. Tools that you can just grab and use, without installing anything.

krackers 7y ago

If you were to just throw the file into a database, wouldn't the database's index essentially lead to the same result (b-tree, compacted using bulk-loading procedure).

nightfly 7y ago
I briefly had a Rocket/IRC bot that talked to a postgres instance with the HIBP DB loaded into it, and yes it worked great.
stryku2393 7y ago
True, but I wanted to create a library and a CLI without dependencies. I don't want to force an end user to install and use a database (even under the hood).

barrkel 7y ago

B-trees, with their trade-off between slow disk seeks and fast in-memory scans, make just as much sense for slow memory accesses and fast in-cache scans.

tylerchr 7y ago

I undertook a similar endeavor a while back. My solution[1] rested on the observation that you don’t need to have a B-tree to do a binary search; one need only be able to calculate the correct byte offset of the Nth hash. With some optimizations, this approach produced a 9.9GB file with similarly fast lookups. [1]: https://github.com/tylerchr/pwnedpass/blob/master/README.md#file-format https://github.com/tylerchr/pwnedpass/blob/master/README.md#...

fwip 7y ago
It looks like the link to your blog post is broken (at the bottom of the README).
- tylerchr 7y ago
  Awkward! Thanks for the tip. I added a copy of that post to the repo and fixed the link.

simonw 7y ago

This is a really informative write-up and an excellent learning exercise. 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-version-2/ 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 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-k-anonymity/ https://blog.cloudflare.com/validating-leaked-passwords-with...

camillovisini 7y ago
Thank you for these resources. Truly ingenious.
ComputerGuru 7y ago
Honestly they’re being super mathematical about it but it’s really nothing fancy at all. SHA is designed to be used like this, CloudFlare hasn’t done anything remotely ingenious (and I wouldn’t mind except they go out of their way to talk about how much better their fancy new algorithm is compared to other multi-set intersection theories). 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.)
- rmwaite 7y ago
  For someone who claims to not like pretension (sic), you're being pretty pretentious.

Avamander 7y ago

There was an app for Android phones that searched for default router passwords based on SSID using this method. It indeed was very fast, even on very bad hardware.

glangdale 7y ago

Any good literal search algorithm could do a one-off search for a single long literal 'needle' way faster than the roughly 1GB/s that the author attained with grep. 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 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.

lalaland1125 7y ago

You can actually do much better than binary search due to the uniform distribution of hashes. https://en.wikipedia.org/wiki/Interpolation_search 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.

zamadatix 7y ago
If you're going to sort the hashes then might as well make a jump table of the first n bits and a binary search from there.
- thedance 7y ago
  Why do you even need the jump table? If the hash function is working you should get quite close just by dead reckoning.
geocar 7y ago
Much better? 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 This took about an hour to download, an hour to 7z|cut|xxd, and about 40 minutes to bake. At complete, I have an on-disk artefact in kdb's native format. q)hibp:get`:hibp; / this mmaps the artefact almost instantly q)\t:1000 {x~hibp[hibp bin x]} .Q.sha1 "1234567890" 5 Now that's 1000 runs taking sum 5msec, or 5µsec average lookup time! It's entirely possible my MacBook Air is substantially faster than the authors' machine, but I'm also doing a lot of other shit while this is going on so whilst I believe a better benchmark is possible, I suspect even better results under better conditions, not worse. 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 .. Ok that looks pretty even to me, so next I partition on the first byte to see if getting 99% closer (1-1/256) on our first guess gets us anything: 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 And it's still 5µsec for lookup! So I'm finding it difficult to believe there's "much better" in there. Do you have some benchmarks to look at?

jiggawatts 7y ago

This and other similar solutions seem awfully over-engineered. 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 There. I solved the blogger's problem in literally under 5 minutes without having to write a custom binary. 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!

jakoblorz 7y ago
Yet you pay the cost in speed when using a database engine, there is a big overhead.
- jiggawatts 7y ago
  Meh. 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.

emmelaich 7y ago

Just to remind people of `look`, which does a binary search. It might be superior to the articles methods if you only want to search for a few.

lolc 7y ago
Funny how many tools are stowed on my system. I'll never know them all!
xurukefi 7y ago
Didn't know about look. Seems good enough (tested on a HDD): $ 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 dd is used to drop the file from the fs cache. Something the author probably didn't do given the unrealistic 49μs. It's simply not possible to fetch data from a HDD that fast.
- stryku2393 7y ago
  True, the benchmarks are bad. I'll rewrite them (to drop the cache every time) and update the results.
iseeyou 7y ago
wow, thanks, yet another tool to remember in the toolbox sudo purge time look E38AD214943DAAD1D64C102FAEC29DE4AFE9DA3D pwned-passwords-sha1-ordered-by-hash-v5.txt E38AD214943DAAD1D64C102FAEC29DE4AFE9DA3D:2413945 0.01 real 0.00 user 0.00 sys` not 49us, but fast enough for most use cases (purge should clear the fs cache)

jonstewart 7y ago

In digital forensics we often have to do a hash set lookup as in this article. When the set is constant, you can sort it as the author did, and then perform a linear scan to determine the maximum error—i.e., how far away a hash value is from its expected location—and then use a reduced binary search/interpolation search, where the expected index is used as the midpoint and the maximum error is used to determine the window. On large hash sets of this size, the maximum error is still often measured in KB. 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.

iomintz 7y ago
I'm trying to implement this myself. How is the expected location computed? Is it just hash_as_int / max_sha1_hash * file_size?

saagarjha 7y ago

> A node is a simple structure of sixteen 32 bit values. The values are 'pointers' to next nodes, at given character of the SHA-1 hash. So, one node takes 16 * 4B = 64B. 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.)

_wldu 7y ago

You may also consider using a bloom filter to do this: https://github.com/62726164/bp https://github.com/62726164/bp

deleted 7y ago

[deleted]

ttt111222333 7y ago

I did something similar when I wanted to search the HIBP database and if you are okay with some false positives you can do better than your results, both in terms of speed and size. 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 https://github.com/terencechow/PwnedPasswords

marcan_42 7y ago

This is bad benchmarking. There is no way you're doing a b-tree lookup in microseconds on an on-disk file... Unless the parts you care about are already cached. 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/23e1ec416bf884dcd7f0e635ce5f2724 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.

rovr138 7y ago
> 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
- saagarjha 7y ago
  Note that this does take a while; I let it go for about two hours before killing sort.
  - rovr138 7y ago
    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 48mins `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 :)

jadia 7y ago

While preparing for interviews, I use to wonder why do they emphasize so much data structures. This article proved them right and made me realize why data structures must be your muscle memory.

ThePhysicist 7y ago

Great writeup! Another way to query the DB are probabilistic filters. I wrote a Bloom filter based query API for this a while ago: https://github.com/adewes/have-i-been-bloomed 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).

QuadrupleA 7y ago

Cool learning exercise and fun read. Can't help but think SQLite could do this screamingly fast and very easily, with nice compact storage (blob primary key with the hashes, without-rowid table to avoid a hidden integer per row). That said, 49us is very impressive. Hard to beat low level custom coded solutions.

geocar 7y ago
> 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 This took about an hour to download, an hour to 7z|cut|xxd, and about 40 minutes to bake. At complete, I have an on-disk artefact in kdb's native format. I can load it: q)hibp:get`:hibp; / this mmaps the artefact almost instantly and I can try to query it: q)\t:1000 {x~hibp[hibp bin x]} .Q.sha1 "1234567890" 5 Now that's 1000 runs taking sum 5msec, or 5µsec average lookup time! It's entirely possible my MacBook Air is substantially faster than the authors' machine, but I think being ten times slower than an "interpreted language" suggests there's a lot of room to improve!

DmitryOlshansky 7y ago

> Trie structure sucks if you have pretty random words. 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: https://en.wikipedia.org/wiki/Radix_tree https://en.wikipedia.org/wiki/Radix_tree

haberman 7y ago

There are 555,278,657 passwords in the database. With a Bloom Filter, you could quickly rule out potential inputs. Even better, there is no need to hash the input, because... it's already a cryptographic hash. 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= 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.

ascar 7y ago
> 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!?!?").
- haberman 7y ago
  That makes sense. I was thinking of this more as a fun algorithms optimization challenge, not something to actually put into a production setting with real users. I agree that for real users you would especially not want to skip the last step.
- ThePhysicist 7y ago
  The false positive rate can be made arbitrarily small. I have an implementation with a fp rate of 1:1.000.000 with a filter size of just 1.8 GB (https://github.com/adewes/have-i-been-bloomed https://github.com/adewes/have-i-been-bloomed). The cost of lowering the rate is logarithmic so you could go to much lower values for little cost (1:1.000.000.000 would be 2.8 GB) so false positives are not really a problem in practice. If you really want you could still perform an exact check against a DB if the filter returns true to rule out false positives with certainty, though at one false positive for one billion requests this might be exaggerated.

aquadrop 7y ago

Why was data sorted by usage count in the first place? Hash of the password doesn't give you the password, so you just get "something was used x amount of times". Seems like you always want to look up by hash and then sorting by hash from the beginning makes more sense.

viraptor 7y ago

Another solution for cases where you don't add new entries all the time and can reindex the whole database every once in a while instead: use cdb. There's a nice description of the internals and how it works. http://www.unixuser.org/~euske/doc/cdbinternals/index.html http://www.unixuser.org/~euske/doc/cdbinternals/index.html It guarantees access in two disk reads. The original version has the limit of 4gb, but there are 64b versions as well - for example https://github.com/pcarrier/cdb64?files=1 https://github.com/pcarrier/cdb64?files=1

bArray 7y ago

Surely if you know that the hashes will have an ~even distribution you can quite quickly make some assumptions about roughly where the key will be? 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. [1] http://www.cplusplus.com/reference/cstdio/fseek/ http://www.cplusplus.com/reference/cstdio/fseek/

dana321 7y ago
Thinking about it, you would need a 64-bit value to point to the offset because of the size of the file. 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?)

ocfnash 7y ago

I love this write up, and while the solutions discussed are excellent, I think the general-purpose FM Index data structure might work even better. I confess I'd have to read this post more closely to be sure, but I find the FM Index data structure so appealing, I'm always looking for excuses to promote it! 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/index.html http://olivernash.org/2014/01/03/dna-of-a-password-disaster/...

chinesempire 7y ago

using ETS with Erlang (or Elixir) I get sub 50μs (30μs on avergae) lookup times. 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 end

geocar 7y ago
I agree these performance numbers don't seem great. Using q (another interpreted language; not compiled) I get 5µsec on my Macbook Air: Here'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 I can then shut down this process, and start a new one: q)hibp:get`:hibp; / this mmaps the artefact almost instantly q)\t:1000 {x~hibp[hibp bin x]} .Q.sha1 "1234567890" 5 It's so fast I need to run it 1000 times to take just 5msec (5µsec average lookup time!). I imagine converting to md5 would be substantially faster since there's a 16-byte scalar type in q I would be able to use.