33 ms·
Why Searching Through 500M Pwned Passwords Is So Quick
- TorKlingberg 9y agoMinor complaint: Start the blog post with a link to the service you are talking about. I actually have trouble finding it.
- jwilk 9y agoIt's two clicks away: * first paragraph links to https://www.troyhunt.com/ive-just-launched-pwned-passwords-version-2/ https://www.troyhunt.com/ive-just-launched-pwned-passwords-v... ; * first paragraph of that links to https://haveibeenpwned.com/ https://haveibeenpwned.com/.
- TorKlingberg 9y agoThat's the wrong link though. I eventually found it at https://haveibeenpwned.com/Passwords https://haveibeenpwned.com/Passwords
- Quarrelsome 9y agoThat password header warning is the coolest security improvement I've seen online.
- jwilk 9y agoTL;DR why brotli is HTTPS-only: some middle-boxes mangle responses with content encodings they don't know.
- zxcmx 9y agoCloudFlare can read every password submitted through their service and here is why that's so great... It's beatifully elegant, because... What? This is also the same company that spilled memory all over every cache everywhere.
- jgrahamc 9y agoNope. 100% incorrect, Troy's service is using Cloudflare but you don't send the password to his API: https://blog.cloudflare.com/validating-leaked-passwords-with-k-anonymity/ https://blog.cloudflare.com/validating-leaked-passwords-with...
- zxcmx 9y agoMy apologies, I was wrong. I was assuming that you were terminating ssl and therefore in a position to read the plaintext of user requests. 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.
- jgrahamc 9y agoTroy's API doesn't work like that. Doesn't need to send the password at all.
- zxcmx 9y agoWonderful, thank you [edit] thinking this through.... but regardless of how the api works, is it not possible that you (cloudflare) could just have the list and check yourselves since you know the submitted password? It could be a value added service for all your customers. [Sorry for the late edit, not being evil here].
- sleepychu 9y agoSurprised Troy is so pro-cloudflare. I feel like they create a lot of security headaches.
- JosephRedfern 9y agoCan you elaborate on that?
- tempay 9y agoOP is probably referring to [1] or the general fact that they MITM most traffic that uses their services. [1] https://blog.cloudflare.com/incident-report-on-memory-leak-caused-by-cloudflare-parser-bug/ https://blog.cloudflare.com/incident-report-on-memory-leak-c...
- dingo_bat 9y agoTbf that's the actual service they offer. It's not like they are being sneaky.
- tialaramex 9y agoTo be sure, but anybody using CloudFlare needs to keep in the back of their head that everything going through CF is not only accessible to a hypothetical Bad Guy at CloudFlare it can also (and remember has, this is a real bug that happened) get exposed to unrelated parties on the Internet if CF mixes your data with somebody else's by mistake. 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.
- matthewmacleod 9y agoOf course they do that. How else would such a service possibly operate?
- barrkel 9y agoWhen you don't need transactions, don't have a cache invalidation problem, and are querying read-only data, then this architecture - or really any architecture that takes advantage of what makes HTTP scalable, mostly idempotent, cacheable responses to GETs - makes sense.
- endorphone 9y agoI do think it is a bit disingenuous that the author compares this to a classic web application and its data needs, when the needs here are so trivial. It is very well designed for what it does (the security needs of such a checker almost dictates the design), but is a model usable by very few applications. 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-revisiting-why-you-should-use-nginx-in-your-solutions/ https://dennisforbes.ca/index.php/2016/01/28/eat-your-brotli...
- byefruit 9y agoNot to mention that the dataset is relatively small. A 16GB of ram server could basically serve responses sub-millisecond at line rate for like $25/month.
- euroclydon 9y agoAnyone know, if we permute all 6-16 character length alpha numeric strings, how many would would have their sha-1 hash be a match for a given five character prefix? 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.
- dsacco 9y agoA SHA-1 hash digest is a 160-bit hexadecimal string. These are 40 digits long, with 16 possible values per digit, yielding a total search space of 16^40 possible values. 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!
- tzs 9y agoShouldn't the size of the alphanumeric alphabet used for the passwords be in there somewhere? The question was about how many permutations of all 6-16 character alphanumeric strings map to a given 5 digit SHA-1 prefix. 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.
- 9y ago
- StavrosK 9y agoHere's a slightly more easily auditable version of the checker, in Python: https://www.pastery.net/wwzqua/ 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.
- YTGRK 9y agohttps://youtu.be/XSpOTUKz3Ys https://youtu.be/XSpOTUKz3Ys
- darkport 9y agoI love the k-Anonymity model. Makes it actually feasible to check passwords against HIBP when carrying out password audits for clients. Shameless plug but I've added it to my Active Directory audit password tool: https://github.com/eth0izzle/cracke-dit https://github.com/eth0izzle/cracke-dit
- _pdp_ 9y ago...or CloudFlare/CloudFront plus DynamoDB table with primary key of the first/last n-number of characters from the hash with potential secondary index for filtering. 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.
- always_good 9y agoYou'd be paying a lot for bandwidth on S3 and Cloudfront.
- deleted 9y ago[deleted]
- zcam 9y agoWouldn't using a simple bloom filter make sense in their case? Just build the thing offline and your app loads it in RAM at startup.
- jgrahamc 9y agoHere's a quick table of sizes of the Bloom Filter with the FP rate False positives Size (MB) 0.1 285 0.01 571 0.001 857 0.0001 1120 0.00001 1390 0.000001 1670
- Ajedi32 9y agoThat's only if you're sending a bloom filter for the entire hash table though. If you just use the existing buckets you could reduce the API response sizes considerably. The 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.
- jgrahamc 9y agoI don't understand why everyone's obsessed with using a Bloom Filter for this. The median response size on the API is 12.2KB with 305 entries. A Bloom Filter with 305 entries and a 0.000001 false positive rate would be about 1KB. It seems to me you're introducing a lot of complexity (Bloom Filter vs. simple string match) and possibility of false positives to save 11KB.
- ericfrederich 9y agoA bloom filter can be pushed to clients. Everything is static and could be served from a CDN. If there is a hit you could then do a secondary request to perform an actual lookup. For passwords which have not been pwned there'd be a 100% savings on CPU.
- ianhawes 9y agoThis is slightly OT and probably not a popular opinion, but does anyone else feel that Troy having this massive dataset of emails is unethical? I definitely believe it is illegal and was surprised that during his recent visit to the US that the FBI did not arrest him.
- tyingq 9y agoCurious which specific US law(s) it violates. Sounds like he downloaded a few torrents and built a search interface.
- Griffinsauce 9y agoYou jumped to illegal before even explaining why it's unethical.
- mi100hael 9y agoSimply possessing the information (which is already freely available online) is not on its own unethical. It depends entirely upon what he does with the information, which in this case is protect the owners from malicious individuals who also have access to the information because it's freely available online.
- 2close4comfort 9y agoIt is if its stolen property...which most of that data belonged to the company that was hacked.
- emodendroket 9y agoI'm not going to pretend to understand the legal niceties here, but the analogy to "stolen property" rings false because 1) he's not depriving anybody of their passwords 2) the very fact they've been leaked means they aren't really of value anymore.
- snug 9y agoThese passwords were already publicly available, some with the email address associated with them.
- dx034 9y agoJust putting this on a vps or cheap dedicated server with 16gb ram would've led to sub-ms response times at much lower costs (if you don't get Azure and Cloudflare for free like him). At those response speeds, scalability is also not really an issue if you cache aggressively at the edge. 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.
- eropple 9y agoI'm not sure that you quite realize that Troy's intention here is to eventually be soaking a whole lot of zeroes with this. Add on to that that, if people are relying on this as a service, it had better not go down under any remotely plausible circumstances, and some growth-hacker's dedicated server from Hetzner or whatever is unsuitable. Edge caching only blunts sufficiently this if everybody's searching for the same passwords and proving that that's the case is a burden you have not shouldered. 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.
- m4lvin 9y ago> Edge caching only blunts sufficiently this if everybody's searching for the same passwords AFAIK caching already kicks in when people check different passwords that have same first five characters in their hash.
- eropple 9y agoSorry, you're right, I should have been clearer. The bigger concern is that caching doesn't replace fault tolerance and rolling your own disaster recovery. I didn't mean to suggest that caching was not being done or would not be helpful. A million keys would be pretty uniformly dispersed; intuitively it seems like you'd need to have a lot more traffic than he's currently got to the point where caching reliably soaks enough load off of "a VPS or cheap dedicated server" that you can afford to have the server blow up--because servers blow up. "A VPS or cheap dedicated server" is YOLO stuff. Not something you do when you want other people to rely on you.
- yupyup 9y agoSomewhat related (and nitpicky), but there are some spelling errors (derrivation, seperate...) on the Cloudflare post that explains k-anonimity: https://blog.cloudflare.com/validating-leaked-passwords-with-k-anonymity/ 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.
- Sir_Cmpwn 9y agoStarting to get a little uncomfortable with how hard this is being pushed on HN right now. https://hn.algolia.com/?query=troyhunt.com&sort=byDate&prefix=false&page=0&dateRange=all&type=story https://hn.algolia.com/?query=troyhunt.com&sort=byDate&prefi...
- wyldfire 9y agoIt's good to be skeptical, but everything I've read so far makes me believe Hunt's motives are good. His efforts are beneficial to HN readers and beyond. 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?
- Sir_Cmpwn 9y ago>How different are these search results from other popular sites? 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.
- yorby 9y agoI only see 1 post about it: https://hn.algolia.com/?query=https:%2F%2Fwww.troyhunt.com%2Fi-wanna-go-fast-why-searching-through-500m-pwned-passwords-is-so-quick%2F&sort=byDate&prefix=false&page=0&dateRange=all&type=story https://hn.algolia.com/?query=https:%2F%2Fwww.troyhunt.com%2...
- Sir_Cmpwn 9y agoI'm not sure if you're just being snarky or not, but use the link I gave in my comment. There are 3 articles this week about the "have I been pwned" tool.
- 9y ago
- draw_down 9y agoYeah, all those dumb old programmers are cargo culting when they pick a database. Why can’t those dummies just have a read-only dataset that doesn’t change?!
- skrebbel 9y agoCouldn't he just pregenerate all 1.048.576 responses, load them somewhere in RAM (or just a bunch of HTML files on an nginx with caching on) and be done with it? I mean he writes that a single response, gzipped, averages 10kb so that's only 1GB of RAM in total. 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.
- Bedon292 9y agoThe breach data isn't updated that often. It was 6 months between v1 and v2, so a long cache is totally fine. And then invalidate the cache if there is an update.
- skrebbel 9y agoThat.. sort of supports my argument :-) He could cache it indefinitely instead of 30 days if he's going to invalidate the cache anyway.
- Bedon292 9y agoI do appear to have misinterpreted what your point was. Sorry about that. Although I assume the idea was limiting how much is cached at any point on their part. Not sure it really matters though its not that much data.
- sciurus 9y agoIt sounds like he did pregenerate all the responses, then stored them in Azure Blob Storage. From the article I can't tell why he even needs to use Azure Function. Azure Blob Storage can be configured for public access over HTTP [0], so he could point Cloudflare directly at it. [1] https://docs.microsoft.com/en-us/azure/architecture/patterns/static-content-hosting https://docs.microsoft.com/en-us/azure/architecture/patterns...
- kpennell 9y agoWas expecting an Algolia ad but was delightfully surprised.
- frogpelt 9y agoHow am I supposed to pronounced 'pwned'? Can't we find something other than 4chan language to describe this?
- 8note 9y agohttps://en.oxforddictionaries.com/definition/pwn https://en.oxforddictionaries.com/definition/pwn
- slow_donkey 9y agoPowned. Literally owned then add a hard p
- MBCook 9y ago‘owned’ with a P on the front. 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.
- extra88 9y agoI'm not a fan of the term but "pwned" predates 4chan. http://knowyourmeme.com/memes/owned-pwned http://knowyourmeme.com/memes/owned-pwned
- zaroth 9y agoUmmm... because it’s an O(1) array lookup not a search at all? Infuriating. 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.
- th3byrdm4n 9y agoPrecisely my first thought. Static readonly data? Why isn't this just sitting in memory?
- mzzter 9y agoSounds reasonable, 500mil * 160 bits of SHA-1 would be 500 mb of space. Even with some metadata to manage it, the smallest instances should be able to handle that.
- lipnitsk 9y ago500,000,000*160bits/(8bits/byte)=10,000,000,000 bytes=9,536MB=9.313GB
- vortico 9y agoDon't filesystem caches basically do this for you?
- zaroth 9y agoYes but with a heck of a lot more overhead than; response.body = result[(int)hexCode];
- dullgiulio 9y ago
- manigandham 9y agoLots of suggestions in this thread about better architecture but they all seem to forget that this is designed to be minimal in cost, complexity and maintenance while delivering 100% availability and great performance. 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.
- aplorbust 9y agoWhat does he do with the logs of all the passwords submitted in searches?
- reificator 9y ago> What does he do with the logs of all the passwords submitted in searches? > 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.
- aplorbust 9y agoWhat about the logs from queries submitted via the HIBP website form? "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.
- manigandham 9y agoThe form on HIBP uses the same JS client hashing, you can check the HTTP requests yourself in dev tools. 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-version-2/ https://www.troyhunt.com/ive-just-launched-pwned-passwords-v... You can get the 8.8gb file directly here: https://haveibeenpwned.com/Passwords https://haveibeenpwned.com/Passwords