4 ms·
k-Anonymity doesn't really work with non-uniform distributions. E.g. if x is your hash prefix and d is a particular domain that matches that prefix, then we can
by singron 7y ago
k-Anonymity doesn't really work with non-uniform distributions. E.g. if x is your hash prefix and d is a particular domain that matches that prefix, then we can apply Bayes rule:
P(d|x) = P(x|d) * P(d) / P(x)
P(x|d) is 1 in this case (the hash is deterministic), so the probability is just P(d)/P(x). E.g. if "facebook.com" doesn't have a hash collision with another similarly popular site, then you can be pretty sure that a request for hash("facebook.com") is a request for "facebook.com" for a high proportion of requests.
This also adds some overhead. E.g. 400 IPs+TTLs probably wouldn't fit in a 1500 MTU packet, so it might have to be split up or k reduced to fit.
From the ISP perspective, they can also tell which of the k you were interested in because you will probably send a SYN packet to that IP address. Unless you also send 400 SYN packets...