4 ms·

Downvoters who think that might be too much data don't know about Bloom filters.

morelisp 7y ago
People who think they know about Bloom filters should consider what attack vectors a false positive with such would allow. (The end result of the thought experiment will be basically what Google does now.)
robocat 7y ago
Bloom filters are likely useless in this situation - following facts for phishing only: 1. Phishing sites have a lifecycle of about 15 hours. 2. Most malicious links are hidden within benign domains. 3. About 400,000 phishing sites are created each month. From: https://www.itgovernance.co.uk/blog/4-eye-opening-facts-about-phishing https://www.itgovernance.co.uk/blog/4-eye-opening-facts-abou... I haven't run the numbers, but I am guessing that a clientside solution would have a lot of bandwidth sucking and avoiding false positives is very important. Also with a clientside solution, how are new phishing URLs detected? PS: perhaps try to assume HNers know what a Bloom filter is (I've seen them come up lots of times in comments).
- pmoriarty 7y ago
  400,000 sounds like a lot, but I wonder how many new URLs Tencent adds to its database each month. I expect they don't add every phishing URL but some small subset of them (possibly even a very small subset.. we'll proably never know). But let's say it is 400,000. I took the URL you linked and made a file of 400,000 copies of it. The file size was 28 MB. I didn't bother compressing that particular file since the URL is the same in each instance, but I expect a file full of actual phishing URLs would probably compress pretty well, so it would probably be significantly less than 28 MB. Considering that OS vendors regularly ship multi-gigabyte size updates, having to download less than 28 MB extra every month shouldn't even be noticeable. If updates needed to be done more frequently, the client could subscribe to get regular updates as they become available.
  - tomxor 7y ago
    > 28 MB extra every month shouldn't even be noticeable Parent comment suggests phishing site life-cycle <15hrs, at 400k a month that's 8333 every 15 hrs. To give an idea of how frequency sensitive this is, assume URLs are added equidistributed in time: that would be a new one every 154ms - for such time critical information it makes no sense to attempt to synchronize clients, it would require constant polling or push updates to have _any_ chance of catching a malicious URL. At such a frequency, efficiency becomes less about bandwidth and more about the overhead of continuously synchronising so many clients (think of that 28 MiB spread out over 400k separate messages over one month, one every 154ms, that not only inflates the size, but causes a constant network usage and processing that is far less efficient than a single 28MiB download). Or you could just send the URL hash when you visit a URL... (do you request any where near 8k URLs every 15hrs?, 1 URL every 154ms? no), it's so clearly a simpler solution that will be faster for everyone without letting bad URLs slip through before a latent sync.
    - pmoriarty 7y ago
      Do you really think Tencent is detecting a new phishing site every 154ms? I'd seriously question how many of the total new phising sites they detect to start off with, and then how frequently they do so. If a user only downloads the deltas periodically they'd risk being out of sync with the master list (which might not be updated even once a month or at all, for all we know), but that's the price they'd need to pay to have to send any information about their web browsing to parties they don't trust. One other thing to consider is the likelihood that the URL you happen to be surfing is both a phishing URL to begin with and one of the ones that just appeared since the last delta download you did, compared to the likelihood that it's one of those already in the entire phishing URL database you've already downloaded. I'd expect those odds to be very low.
      - tomxor 7y ago
        > the likelihood that the URL you happen to be surfing is both a phishing URL to begin with and one of the ones that just appeared since the last delta download you did, compared to the likelihood that it's one of those already in the entire phishing URL database you've already downloaded. I'd expect those odds to be very low. Ignoring the first condition (otherwise why bother with a list at all)... Consider that this information is very transient (average 15hrs), this is pretty simple: deltaT / 54000 This is still horrible, because your safety is determined by how frequently you can sync with the DB. > If a user only downloads the deltas periodically they'd risk being out of sync with the master list (which might not be updated even once a month or at all, for all we know). Being updated monthly doesn't match the statistic of average 15hr lifecycle, because it would be useless after that length of time. And while I don't claim to know 15hrs as a fact, it is intuitive that the average will become ever shorter as malicious URL checkers become updated ever faster. > but that's the price they'd need to pay to have to send any information about their web browsing to parties they don't trust. Full URL information need not be sent, a hash of the URL domain and path would probably suffice... if that's not enough then it's a dilemma, but that doesn't make continuous syncing a good or fail safe replacement.
- cryptonector 7y ago
  Google's safe browsing API is probabilistic too. The idea is that you do so many rounds of checking to get closer and closer to the mark. You start with a fairly high false positive probability, high-privacy check, then if you get a positive, you try a lower false positive rate check that also loses you some privacy, and the trade-off is that you don't have to have the full malicious site DB with you at all times (and keep it up to date). Why did you assume I'd not know about false positives?

People who think they know about Bloom filters should consider what attack vectors a false positive with such would allow. (The end result of the thought experiment will be basically what Google does now.)

robocat 7y ago

Bloom filters are likely useless in this situation - following facts for phishing only: 1. Phishing sites have a lifecycle of about 15 hours. 2. Most malicious links are hidden within benign domains. 3. About 400,000 phishing sites are created each month. From: https://www.itgovernance.co.uk/blog/4-eye-opening-facts-about-phishing https://www.itgovernance.co.uk/blog/4-eye-opening-facts-abou... I haven't run the numbers, but I am guessing that a clientside solution would have a lot of bandwidth sucking and avoiding false positives is very important. Also with a clientside solution, how are new phishing URLs detected? PS: perhaps try to assume HNers know what a Bloom filter is (I've seen them come up lots of times in comments).

pmoriarty 7y ago
400,000 sounds like a lot, but I wonder how many new URLs Tencent adds to its database each month. I expect they don't add every phishing URL but some small subset of them (possibly even a very small subset.. we'll proably never know). But let's say it is 400,000. I took the URL you linked and made a file of 400,000 copies of it. The file size was 28 MB. I didn't bother compressing that particular file since the URL is the same in each instance, but I expect a file full of actual phishing URLs would probably compress pretty well, so it would probably be significantly less than 28 MB. Considering that OS vendors regularly ship multi-gigabyte size updates, having to download less than 28 MB extra every month shouldn't even be noticeable. If updates needed to be done more frequently, the client could subscribe to get regular updates as they become available.
- tomxor 7y ago
  > 28 MB extra every month shouldn't even be noticeable Parent comment suggests phishing site life-cycle <15hrs, at 400k a month that's 8333 every 15 hrs. To give an idea of how frequency sensitive this is, assume URLs are added equidistributed in time: that would be a new one every 154ms - for such time critical information it makes no sense to attempt to synchronize clients, it would require constant polling or push updates to have _any_ chance of catching a malicious URL. At such a frequency, efficiency becomes less about bandwidth and more about the overhead of continuously synchronising so many clients (think of that 28 MiB spread out over 400k separate messages over one month, one every 154ms, that not only inflates the size, but causes a constant network usage and processing that is far less efficient than a single 28MiB download). Or you could just send the URL hash when you visit a URL... (do you request any where near 8k URLs every 15hrs?, 1 URL every 154ms? no), it's so clearly a simpler solution that will be faster for everyone without letting bad URLs slip through before a latent sync.
  - pmoriarty 7y ago
    Do you really think Tencent is detecting a new phishing site every 154ms? I'd seriously question how many of the total new phising sites they detect to start off with, and then how frequently they do so. If a user only downloads the deltas periodically they'd risk being out of sync with the master list (which might not be updated even once a month or at all, for all we know), but that's the price they'd need to pay to have to send any information about their web browsing to parties they don't trust. One other thing to consider is the likelihood that the URL you happen to be surfing is both a phishing URL to begin with and one of the ones that just appeared since the last delta download you did, compared to the likelihood that it's one of those already in the entire phishing URL database you've already downloaded. I'd expect those odds to be very low.
    - tomxor 7y ago
      > the likelihood that the URL you happen to be surfing is both a phishing URL to begin with and one of the ones that just appeared since the last delta download you did, compared to the likelihood that it's one of those already in the entire phishing URL database you've already downloaded. I'd expect those odds to be very low. Ignoring the first condition (otherwise why bother with a list at all)... Consider that this information is very transient (average 15hrs), this is pretty simple: deltaT / 54000 This is still horrible, because your safety is determined by how frequently you can sync with the DB. > If a user only downloads the deltas periodically they'd risk being out of sync with the master list (which might not be updated even once a month or at all, for all we know). Being updated monthly doesn't match the statistic of average 15hr lifecycle, because it would be useless after that length of time. And while I don't claim to know 15hrs as a fact, it is intuitive that the average will become ever shorter as malicious URL checkers become updated ever faster. > but that's the price they'd need to pay to have to send any information about their web browsing to parties they don't trust. Full URL information need not be sent, a hash of the URL domain and path would probably suffice... if that's not enough then it's a dilemma, but that doesn't make continuous syncing a good or fail safe replacement.
cryptonector 7y ago
Google's safe browsing API is probabilistic too. The idea is that you do so many rounds of checking to get closer and closer to the mark. You start with a fairly high false positive probability, high-privacy check, then if you get a positive, you try a lower false positive rate check that also loses you some privacy, and the trade-off is that you don't have to have the full malicious site DB with you at all times (and keep it up to date). Why did you assume I'd not know about false positives?