4 ms·

I think it's a bit worse than that. Suppose the server wants to learn whether you have a certain number in your contacts. Then they simply put that number int

I think it's a bit worse than that. Suppose the server wants to learn whether you have a certain number in your contacts. Then they simply put that number into your lower-level Bloom filters for L0, L1, L2, ... even if that number is not really a member of the service. To prevent a final match, they only need to keep the target number out of the final BF. Then they passively watch which BF's you retrieve at L1, L2, ... etc. If you never retrieve the BF for Ln, despite the bits for the target number being present in the L(n-1) Bloom filter, then they know you don't have the target as a contact. Does that make sense? Of course, this attack and the previous one both go away if we assume the server is "honest but curious".

chrisdew 11y ago
That makes sense, but any malicious service could pretend that a particular telno was a user of the service, in order to see which users had that contact. I'm assuming the objective is to minimise the service's unnecessary knowledge of non-service-user contacts.
- cvwright 11y ago
  > I'm assuming the objective is to minimise the service's unnecessary knowledge of non-service-user contacts. Right, so an honest-but-curious adversary model sounds like it's a good fit for the server. Then all these attacks where the server lies about something are out of scope. Again, I like this idea so I think it's worth thinking about it some more. Not trying to nitpick here, just trying to help think through what you can do. What about the clients? Do you want to limit what they can learn? Given any telno, a client can quickly tell whether that telno belongs to the service, even if the client doesn't really have that number in its contacts. Does that matter? I guess we come to a sort of meta-point here. What does it mean for a number to be in someone's address book? Anything? A fundamental part of the problem seems to stem from trying to make this work with identifiers that come from a (cryptographically speaking) very small space. Extending the attack above, really the client can get a pretty decent approximation of the entire list of telnos in the service. If he checks all 10 billion telnos against the BF for L0, he gets a list that includes all subscribers and several false positives -- each number in the list is only 90% likely to be a subscriber. If he wants to refine his estimate for the likelihood that any given number is a subscriber, he retrieves the corresponding BF for L1. So he starts with a decent estimate of the subscriber list, and with each BF that he downloads, is estimate improves. How bad is that? I'm really not sure...
  - chrisdew 11y ago
    The number of downloads required to get each additional nibble is 16 times that of the previous nibble.
    - cvwright 11y ago
      Also -- I was too sloppy in my earlier analysis, and as a result, my numbers could be way off. The attacker might learn much less than I initially thought. It depends on how many users are subscribed to the service. After the client downloads the BF for L0 and hashes the entire space of 10 billion telnos, he knows 90% of the non-subscribers for certain. All the telnos that matched in the Bloom filter are either (a) subscribers of the service or (b) false positives from the BF. Let's say there are n subscribers. Then the attacker gets a total of n + 0.10 * (10^10 - n) hits on L0. The likelihood that a matching telno is actually a subscriber is n / (n + 0.10 * (10^10 - n)). So he learns something with each level of the Bloom filter, but getting to 90% certainty may require retrieving several levels of the BF.
      - chrisdew 11y ago
        Thanks for your questions and analysis.

chrisdew 11y ago

That makes sense, but any malicious service could pretend that a particular telno was a user of the service, in order to see which users had that contact. I'm assuming the objective is to minimise the service's unnecessary knowledge of non-service-user contacts.

cvwright 11y ago
> I'm assuming the objective is to minimise the service's unnecessary knowledge of non-service-user contacts. Right, so an honest-but-curious adversary model sounds like it's a good fit for the server. Then all these attacks where the server lies about something are out of scope. Again, I like this idea so I think it's worth thinking about it some more. Not trying to nitpick here, just trying to help think through what you can do. What about the clients? Do you want to limit what they can learn? Given any telno, a client can quickly tell whether that telno belongs to the service, even if the client doesn't really have that number in its contacts. Does that matter? I guess we come to a sort of meta-point here. What does it mean for a number to be in someone's address book? Anything? A fundamental part of the problem seems to stem from trying to make this work with identifiers that come from a (cryptographically speaking) very small space. Extending the attack above, really the client can get a pretty decent approximation of the entire list of telnos in the service. If he checks all 10 billion telnos against the BF for L0, he gets a list that includes all subscribers and several false positives -- each number in the list is only 90% likely to be a subscriber. If he wants to refine his estimate for the likelihood that any given number is a subscriber, he retrieves the corresponding BF for L1. So he starts with a decent estimate of the subscriber list, and with each BF that he downloads, is estimate improves. How bad is that? I'm really not sure...
- chrisdew 11y ago
  The number of downloads required to get each additional nibble is 16 times that of the previous nibble.
  - cvwright 11y ago
    Also -- I was too sloppy in my earlier analysis, and as a result, my numbers could be way off. The attacker might learn much less than I initially thought. It depends on how many users are subscribed to the service. After the client downloads the BF for L0 and hashes the entire space of 10 billion telnos, he knows 90% of the non-subscribers for certain. All the telnos that matched in the Bloom filter are either (a) subscribers of the service or (b) false positives from the BF. Let's say there are n subscribers. Then the attacker gets a total of n + 0.10 * (10^10 - n) hits on L0. The likelihood that a matching telno is actually a subscriber is n / (n + 0.10 * (10^10 - n)). So he learns something with each level of the Bloom filter, but getting to 90% certainty may require retrieving several levels of the BF.
    - chrisdew 11y ago
      Thanks for your questions and analysis.