Tinkering about how to publish domain blacklists without immediately revealing the domains. Compressed bloom filters or Golomb-coded sets using hash functions whose complexity increases exponentially + a final memory hard hash?
-
Show this thread
-
A simpler approach would be to publish a set of truncated hashes of exponentially increasing work factor for each domain. Easier to do and update, but obviously less memory efficient than probabilistic structures.
3 replies 0 retweets 0 likesShow this thread -
Replying to @jedisct1
Maybe the tricky part in Bloomfilters is the management of the false-positive ratio. Also the canonization of the domains can be a source of issues. Not sure what the best data-structure is...
2 replies 0 retweets 0 likes -
Can't you check the full URL (or its hash) in case of a hit, to avoid (or at least reduce) FPs?
1 reply 0 retweets 0 likes -
Replying to @martijn_grooten @adulau
This is not acceptable. Someone must be able to look up “pictures-of-donald-trump-naked-when-he-was-a-kid\.com” without this being ever sent (and possibly logged) to a 3rd party if the filter was supposed to locally block it.
1 reply 0 retweets 2 likes -
Ah, that's fair enough of course.
1 reply 0 retweets 0 likes -
Replying to @martijn_grooten @adulau
But something computationally intensive to withstand offline attacks is fundamentally incompatible with routers and other small devices people typically use as gateways/proxies.
1 reply 0 retweets 1 like -
Not a showstopper, though. Blacklist publishers should adjust the work factor according to their needs.
1 reply 0 retweets 0 likes -
Replying to @jedisct1 @martijn_grooten
We did a similar experiment for
@MISPProject but it’s still in an early stage https://dial.uclouvain.be/memoire/ucl/en/object/thesis%3A10600/datastream/PDF_01/view … the code is onhttps://github.com/MISP/misp-privacy-aware-exchange …2 replies 0 retweets 1 like -
So, traditional bloom filter + pwhash. Good, but false positives have quite of a cost. Hence the suggestion using hash functions with increasing costs, so you can abort early when you hit a FP.
1 reply 0 retweets 1 like
There are obvious TMTO attacks here, but this is okay as long as the final hash requires enough work.
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.