Hacker News Reader

Comment by est31 | Hacker News Reader

There is a first step which uses bloom filters, and if the filter gives a result, it is hashed and the hash is sent to the google service to double-check.

That being said, a four byte / 32 bit hash is enough to almost uniquely identify a website. There number of 32 bit numbers and websites is roughly the same order of magnitude. It's a problem without a good solution because if you create many collisions then you also generate plenty of sites falsely reported as phishing and which admin would want that to happen on their site. If you avoid creation of collisions, you have this identifyability problem.

There is this CRLite proposal [1] using layered bloom filters to stop reliance on web services. Maybe it can be adopted for phishing sites, as well.

[1]: https://ieeexplore.ieee.org/document/7958597

View on HN

The safe browsing protocol computes (up to) 30 hashes of each URL, most of which include path components of the URL. So the space of URLs subject to hashing is far greater than 2^32, and the hash prefix alone tells you practically nothing.

Furthermore the protocol does not declare as URL as blocked just because the 32-bit hash prefix matches. If the prefix matches, the browser downloads the list of full hashes and checks the full hash against that list locally.

It's frustrating to see people jumping to erroneous conclusions about how Safe Browsing works when the spec is publicly available and quite clear. https://developers.google.com/safe-browsing/v4/

Just how large is the database?

Computing 30 hashes of each URL means you are sending a fuzzy hash... and 2^(32*30) is fairly precise...

[Disclaimer: I'm the TL of Safe Browsing in Chrome] You can check by going to chrome://safe-browsing/#db-manager

The purpose of my question is that a 4 byte hash is only privacy preserving if there are substantial number of collisions.

Since I’m replying to you, I might as well ask, is Google planning on creating a locally cacheable DNS scheme that includes safe browsing information?

Out of the box bloom filters let you set only false not-in-set probability to zero. The probability for false in-set probability varies, though it can be low if you choose parameters wisely.

What CRLite does achieves zero for both false positives BUT at quite a price. You need to know absolutely all the things that might ever be in the set before you start.

For CRLite they can almost wave that away by declaring that the set of things that might ever be in the CRL set is the set of logged certificates, so we can get that set from the log servers within 24 hours (the "Maximum Merge Delay" in public certificate transparency logs).

But you can't do that for URLs. The set of possible future phishing URLs has infinite size.

>That being said, a four byte / 32 bit hash is enough to almost uniquely identify a website. There number of 32 bit numbers and websites is roughly the same order of magnitude.

Why not send less bits (eg. 24 bit) of the hash?

The utility of the hash for a user and some potential attacker is the same. Yes, passing 8 fewer bits means that they have 256 times more possible sites you might have visited. But it also means that you get 256 times as many false positives of websites being labeled as phising. This is what GP meant by it being problem without a good solution.

One possible option is to do what haveibeenpwned does, where you give fewer bits and then locally check. That would be a good improvement to the system's privacy, but you probably want to avoid downloading the hashes of every malicious website that starts with the given 3 bytes (I'd assume the list is quite large) for every page load.

SafeBrowsing already does the thing you're describing as a "possible option".

Say I go to https://fakebank.example/security/login and Google has decided all of fakebank.example is a phishing site.

My browser computes [among other things] SHA256('fakebank.example') and then it snips off the first four bytes and compares that to a large dataset it got from Google. It fetches updates to this dataset every few hours. Sure enough the four byte prefix is present in the dataset.

So, we've got an alarm - it calls Google, but it doesn't tell them it's thinking about https://fakebank.example/security/login at all, it just tells them the 4 byte prefix. Google responds with a list of full SHA256 hashes beginning with that prefix that it considers _right now_ to be phishing. The list might be empty (maybe fakebank.example was actually a Greek yoghurt company subject to a PHP 4.x attack, and they upgraded PHP and removed the phishing site so now it's fine) but if it has the entire SHA256 hash we calculated then I get an alert telling me that my browser thinks this is a phishing site and I might want to not visit.

Why can’t the browser request the mapping of the hash to the malicious website that is known and then check if that mapping is indeed what it is seeing?

Reply on news.ycombinator.com