Why Searching Through 500M Pwned Passwords Is So Quick
troyhunt.com
troyhunt.com
It’s read-only static data. Spending even 60ms on the response is ridiculous. Reading from files in blob storage... WTF?
Ctrl-F Redis - was disappointed.
Actually, even forget Redis. Pre-generate each of the 1 million possible HTTP responses and store in a string array. The 5 character hex is the index into the array. Write < 100 lines of Go to load the data structure and serve it. What am I missing?
This is like “Hello World” in those HTTP Framework Benchmarks that used to make the rounds every few months.
response.body = result[(int)hexCode];Edit: and if he points the requests directly at blob storage as he's suggesting, we're very close to to flat files on a filesystem again.
On the lookups CF workers has a global state that is shared amongst nodes. Been playing with that. Wondering if you hold string array in that and can get the origin hits below 10% you can run this svc with many million reqs day practically for free. Vps tho, not amzn.
Going down the small hosting a 100 line Go program route, the cheapest "B1" instance type with 1GiB of RAM costs $105.12 a year, and then if you want the service to be HA you need probably another instance in a different zone, maybe a load balancer as well.
I suspect Azure Functions + Blob Storage costs a lot less. Although he didn't mention how much CloudFlare was costing him.
[1] https://azure.microsoft.com/en-us/pricing/details/cache/ [2] https://azure.microsoft.com/en-us/pricing/details/virtual-ma...
The current system works great, most of the hits will be cached, and optimizing the origin to be that milliseconds faster isn't worth it at all.
If the only reason your web app is fast is when its data is cached, you need to take a long hard look at how your web app is built. It's not that hard to build a performant query system like this even with that amount of data.
It doesn't get much simpler than a function that does a key/value lookup or returns a text file; what exactly is over-engineered about that? The app is fast, it's < 100ms which is perfectly fine for non-cached access. This isn't mission critical real-time, it's a completely free service to lookup a password hash.
Everyone here is caught up in the usual "we can do better" perspective without actually thinking about why it was done this way. In reality the current method is cheaper, more reliable, more scalable and has 0 maintenance compared to anything else suggested so far.
Argos is then nice to have but not really necessary. If the server responds back <1ms, those 30% saved RTT are probably not detectable for the user.
To that end, "just use a VPS or a cheap dedicated server" sounds a whole lot like the middlebrow thing we're supposed to not be fans of around here.
AFAIK caching already kicks in when people check different passwords that have same first five characters in their hash.
"A VPS or cheap dedicated server" is YOLO stuff. Not something you do when you want other people to rely on you.
huh?
(Edit: ah, typo. s/this this/with this. Clearer?)
Could you write out deelowe's quoted sentence, above, as clearly as you're able?
Troy's goal is to get this used by a lot of people with a large number of requests per second (so, a number with a lot of zeros in it)
"Soak a few zeros" for example going from 1,000 calls per second to 1,000,000 calls per second.
Learning 'soak a few zeros' is more valuable to me than the whole rest of this thread. I doubt I'll ever use it, but I like it.
> To that end, "just use a VPS or a cheap dedicated server" sounds a whole lot like the middlebrow thing we're supposed to not be fans of around here.
I know that we're supposed to all be fans of AWS and everything as a service. But in reality I found simple VPS (can be Hetzner, OVH, AWS, Google, whatever) to be faster, cheaper and less prone to downtime (as most downtime comes from software rather than hardware anyway).
Even better: host this on a service like Netlify and not even have the 30 day cache timeout Troy has here (which means 30 days old info in case of new breaches). Just regenerate the entire set on the dev box whenever there's a new breach (should be fast enough, it's a linear search & split) and push it to Netlify, it'll invalidate all edge caches automatically.
[1] https://docs.microsoft.com/en-us/azure/architecture/patterns...
Here is how it sounds like it works now when someone visits https://haveibeenpwned.com/Passwords
1) User enters abc123 in the form
2) The frontend translates that to the hash prefix 61ee8
3) The frontend interpolates that into the URL for the function, https://api.pwnedpasswords.com/range/{hashPrefix}
4) The frontend requests https://api.pwnedpasswords.com/range/61ee8
5) The Azure function interpolates the hash prefix into the URL for the response in blob storage, something like http://pwnedpasswords.blob.core.windows.net/foo/{hashPrefix}...
6) The Azure function requests http://pwnedpasswords.blob.core.windows.net/foo/61ee8.txt
7) The Azure function returns that to the frontend
Here is what I was proposing
1) User enters abc123 in the form
2) The frontend hashes that to 61ee8
3) The frontend interpolates that into the URL for the response in blob storage, something like http://pwnedpasswords.blob.core.windows.net/foo/{hashPrefix}...
4) The frontend requests http://pwnedpasswords.blob.core.windows.net/foo/61ee8.txt
As an aside, the article talks a bit about Brotli and it's worth noting that Brotli is nothing more than LZ77 with a dictionary pre-seeded with a 119KB static dictionary of commonly seen web text. It is of course going to be fantastic for compressing an HTML document, where much of the content is verbose and common, but would do nothing above gzip for the hash result data. I would be surprised if it yielded a single byte of savings in that case. Brotli is supported by most browsers as it was snuck into the WOFF 2.0 standard, so browsers that support the new web font standard automatically have to support Brotli.
https://dennisforbes.ca/index.php/2016/01/28/eat-your-brotli...
A 16GB of ram server could basically serve responses sub-millisecond at line rate for like $25/month.
https://www.scaleway.com/pricing/ has 16GB just over $20
Sure, if the machine dies, my services die. But it's still dirt cheap.
It's really not that bad...
[1] https://blog.cloudflare.com/incident-report-on-memory-leak-c...
This makes CF seem fine for your different variants of popcorn.gif, your (subresource integrity checked) Javascript implementation of the VIC-20 computer, or a public blog post, and NOT so great for patient access to histology results, private web forums, banking, and many other things on the Web.
1) Injecting themselves on the application layer (the current model)
2) Injecting themselves on the network layer, passing through only encrypted traffic between the client and your servers
Not every feature they currently offer would still be possible in model #2, but most of them (including DDOS protection) can still work in a limited fashion.
+1 for being interested in expanding this
You could still run a volume analysis on the reply. If it's very short, you can guess it's a 404. If it isn't, you might be able to get which prefix was queried... \end{tin foil hat}
> https://api.pwnedpasswords.com/range/aaaaa = 28.8KB
> https://api.pwnedpasswords.com/range/01234 = 28.5KB
> https://api.pwnedpasswords.com/range/af0fa = 23.2KB
The experiment is left as an exercise to the reader :)
They're presenting sites over HTTPS to visitors while tunneling the full request in plain text over HTTP across the internet back to the origin server. Because of this, web browsers like Chrome will allow access to sensitive APIs like Geolocation despite the end to end communication being insecure.
If I could, I'd personally blacklist all "Flexible SSL" sites from my daily browsing.
2 of Cloudflare's 3 SSL options generate an insecure setup yet look perfectly fine to the user with a shiny green padlock in the address bar. That really isn't acceptable.
While Redis or a VM would be faster, that's way more overhead compared to a few cloud functions and table storage. This whole thing is event-driven and easy to build with just your browser, along with having cheap and granular billing. Cloudflare also already caches the responses so there's really no need for the origin to be perfect.
https://blog.cloudflare.com/validating-leaked-passwords-with...
P.S.: As a non-native speaker had to look those words up to check them, as I trusted the spelling from an official blog post.
https://www.pastery.net/wwzqua/
The bash one was fine, I just prefer the readability of Python to make sure I know that only my truncated hash version is ever sent.
https://blog.cloudflare.com/validating-leaked-passwords-with...
False positives Size (MB)
0.1 285
0.01 571
0.001 857
0.0001 1120
0.00001 1390
0.000001 1670The real problem is that the current API returns a count of the number of times each particular password has appeared, and AFAIK there's no good way to do that with a bloom filter.
Also, a Bloom filter has a smaller page cache footprint and disk space usage than using a precise set.
In order to increase the count for a given key, you expand the key into your probe sequence, find the minimum counter across all of the probed locations, and then increment all of the values equal to that minimum value. One generally uses saturating addition to avoid overflow. If you want to support removing items, you actually increment the values at all of the probe locations, at a cost of increasing the expected deviation from correct counts.
To read the count for a given key, you generate your probe sequence and return the minimum of the values stored at the probed locations.
Note that a regular Bloom filter is just a counting Bloom filter using 1-bit counters.
In this case, I presume one would generate a counting bloom filter and then either store logarithm or quantile of the count, since there isn't a common use case for distinguishing between 4,096 and 4,095 occurrences of a given password.
But for one of the calls (checking a whole password against what's stored), which probably accounts for most of the usage of the API, a bloom filter seems like a perfect fit.
Just send a hash from the client and have the bloom filter built offline with the sames hashes, no big deal. You'd never ask clients to download it.
I’m certainly not saying I think this is an issue! I’m just academically curious about the number and how to go about calculating it.
If we splice off the first five digits (which Troy originally used as the database partition key), we get 1,048,576 five digit values each (16^5). Then we continue calculating with the sixth position as the new first position in the string.
The math from here is a straightforward function mapping 16^n -> 16^(n - 5):
* 16 six digit values match any given five digit partition key, p,
* 16^2 = 256 seven digit values match any p,
* 16^3 = 4,096 eight digit values match any p,
* 16^4 = 65,536 nine digit values match any p,
* 16^5 = 1,048,576 ten digit values match any p,
* 16^6 = 16,777,216 11 digit values match any p,
* 16^7 = 268,435,456 12 digit values match any p,
* 16^8 = 4,294,967,296 13 digit values match any p,
* 16^9 = 68,719,476,736 14 digit values match any p,
* 16^10 = 1,099,511,627,776 15 digit values match any p,
* 16^11 = 17,592,186,044,416 16 digit values match any p.
So in general, to calculate how many n digit SHA-1 digests correspond to any m digit prefix, we simply calculate (16^n)/(16^m), which yields 16^(n - m). Thus we have (16^[6..16]) / (16^5) for the five digit prefix case. Hopefully that elucidates it for you!
Your answer seems to be for the case where the alphabet of the input string is hex digits.
I.e., I think we want Sum[A^i,{i,6,16}]/16^5, where A is the size of the alphanumeric alphabet.
For A=62, this is 4.6x10^22 or 2^75.3.
For A=95, this is 4.2x10^25 or 2^85.1.
Sum[A^i,{i,1,N}] = (A^(N+1) - 1) / (A-1).
Sum[A^i,{i,M,N}] = (A^(N+1) - A^M) / (A-1).
Yes, I've stared at permutations for far too long, but I can't have been the first to notice the pattern. It must be in plenty of textbooks.
Another cute combinatorics question: using an alphabet of size A, generate the Nth largest M-character sequence where no two adjacent characters are equal. A simple count-and-check algorithm takes O(N) time, but there's a simple O(M) algorithm (that is, constant time if the number of characters is fixed), assuming constant-time basic arithmetic operations.
Now, I assume you mean "five character prefix of the hex-encoded 160 bit hash"? One hex digit is half a byte; a nibble or 4 bits. 5 * 4=20 bits, leaves 160-20=140 bit hash. Which can represent 2^140 different values.
För a password of 1 to 16 characters from our alphabet, we have 64^16 passwords. The five character prefixes account for 64^5 of those.
64^16=2^(6 * 16)=2^96
64^5=2^30.
(2^96-2^30) < 2^140.
So, if I understood your question: all of them could (should) have unique representations in the remaining hash.
But I think you meant how many would collide in the prefix?
That'd be (2^96-2^30)/(2^20).
I think, it's getting to be bed time. But at least I should be sufficiently wrong for someone to correct me ;)
Btw, indexing can be done cheeper with Google I think.
There is also another way (probably better) and that is to use s3. 1tb can be stored for as little as $20 - the rest is endpoint caching.
Luckily for all of us it is easier than ever to single-handedly scale to millions of users at minimal cost.
* first paragraph links to https://www.troyhunt.com/ive-just-launched-pwned-passwords-v... ;
* first paragraph of that links to https://haveibeenpwned.com/.
> imagine if you wanted to check whether the password "P@ssw0rd" exists in the data set. [...] The SHA-1 hash of that string is "21BD12DC183F740EE76F27B78EB39C8AD972A757" so what we're going to do is take just the first 5 characters, in this case that means "21BD1". That gets sent to the Pwned Passwords API and it responds with 475 hash suffixes (that is everything after "21BD1") and a count of how many times the original password has been seen.
"Another idea I'm toying with is to use the Cloudflare Workers John mentioned earlier to plug directly into Blob Storage. Content there can be accessed easily enough over HTTP (that's where you download the full 500M Pwned Password list from) and it could take out that Azure Function layer altogether. That's something I'll investigate further a little later on as it has to potential to bring cost down further whilst pumping up performance."
How to read this? The full list will be downloadable? Users can do queries locally on the 500M file instead of over the internet? It would be nice to avoid having to submit queries over an untrusted network (the internet), but I doubt that is what is being considered in this paragraph.
Yes, the whole dataset is available. The first paragraph mentions the release of the v2 dataset and you can read the full blog post here: https://www.troyhunt.com/ive-just-launched-pwned-passwords-v...
You can get the 8.8gb file directly here: https://haveibeenpwned.com/Passwords
That page acknowledges the issue, which is all I was curious about:
"Getting back to the online search, being conscious of not wanting to send the wrong message to people, immediately before the search box I put a very clear, very bold message: "Do not send any password you actively use to a third-party service - even this one!""
Can't we find something other than 4chan language to describe this?
At this point the term pwned seems far too well known (in the industry) to change it.
For example, it seems to be in my iPhone’s internal dictionary.
https://hn.algolia.com/?query=troyhunt.com&sort=byDate&prefi...
This search shows four results within the last week and then it starts to drop off. How different are these search results from other popular sites? Ars Technica, Techcrunch, Anandtech, Bloomberg, LWN? Even if you focus on individuals, maybe it's not too different from the articles of Bruce Schneier, ESR, Linus, Theo de Raadt, etc?
Generally the sites you listed have unrelated articles posted which are all on the subject of some distinct topic. The articles posted here in the past week have all been about the compromised password tool.
It's beatifully elegant, because...
What? This is also the same company that spilled memory all over every cache everywhere.
This would allow you to simply look up whether the password was pwned based on form submits.
[edit] ok, I understand what you are saying, Troy's service allows some password privacy due to api design and happens to use cloudflare stuff. Sorry I was so slow.
I was conflating two unrelated things; a) what happens when you submit a password through cloudflare and b) what happens when you happen to use a specific password checking api which uses cloudflare.
It could be a value added service for all your customers.
[Sorry for the late edit, not being evil here].
That doesn't work because only the first five characters of the hash are sent to the API. The API then returns a list of all the hashes that have that prefix that it knows about. The client then (privately) is able to see if their password hash is in that list.
Granted, your password was compromised already if it was in that list, so it needs to be changed anyway, but there's some information revealed by the hash (of course, how else could it be checked?).
In effect, Troy's service never knows the password. It doesn't even know if it existed in the list you received.
I definitely believe it is illegal and was surprised that during his recent visit to the US that the FBI did not arrest him.
In an better world existence of such dataset would be unnecessary.
In the less ideal one you have to look at it's existence in a broader context.
- it provides a clearly beneficial service to owners of those email accounts bridging the gap in the legal systems (disclosure requirements)
- it's exposed in a way that keeps the risk of 3rd party exploitation low: doesn't leak information unless you have access to email account
- it has not to my knowledge been abused in any way and public is keeping check on that - there would have been an outcry that would not go unnoticed
- it's less of a high value target than you'd think - it's built from data that is already in the wild and could be pieced together by a sufficiently motivated actor, especially in the light of the recent combined lists with hundreds of millions of emails surfacing..
Quite frankly if you look at just that it scores better than most datasets gathered by websites requiring user registration.
The only thing missing here really is the consent to be included in that list, but given the sources of the data and the points above I find lack of it more than sufficiently justified.
- Section 58 of the Terrorism Act[0] which makes it illegal to possess information "likely to be useful to a person committing or preparing an act of terrorism", though the law provides "reasonable excuse" as an explicit defence.
- Section 3A of the Computer Misuse Act[1] "making, supplying or obtaining articles for use in unauthorised access to computer material" [my paraphrasing]
It feels like Troy has a pretty strong defence of "reasonable excuse" to my lay understanding though.
[0] https://www.legislation.gov.uk/ukpga/2000/11/section/58 [1] https://www.cps.gov.uk/legal-guidance/cybercrime-prosecution...