3 ms·
Good catch. This is a weakness, but it may not be relevant to WhisperSystems' use case. If you provide an L0 with numbers whose hashes end with '1' (hex), and
by chrisdew 11y ago
Good catch. This is a weakness, but it may not be relevant to WhisperSystems' use case.
If you provide an L0 with numbers whose hashes end with '1' (hex), and I don't request L1/..1 shard, then you learn that I don't have any numbers whose hashes end with '1' (hex).
I have 1024 contact telno hashes.
Assuming I request only when the app is installed, and daily after that, it will take you:
16 days to learn which final nibbles my contact hashes have - probably all of them.
256 days to learn which final bytes my contact hashes have - probably all of them.
4096 days to learn which final 12 bits my contact hashes have - probably around a quarter of them.
Three years in, you know which 900-1024 of the 4096 12 bit combos match the last twelve bits of one or more of the telno hashes.
~950 * 4096 = 15,200 days to learn the final two bytes of hashes, of which there will probably be ~1000 unique values.
You now know 1000 buckets of 6 million numbers which contain one or more numbers from my contacts.
If you update the app, over the air, to query every second, this would take just a few hours. But then, you could just update the app to grab all my contacts and send it instantly.
The "server cheating" is a valid attack, but it may not be important, as there are easier attacks if we assume a malicious service.
I assumed that WhisperSystems were trying to limit the information they had, as a good actor, rather than ensuring complete app safety vs a malicious service provider.
i.e. their motivation is not to have the information to turn over, rather than to not be able to get it when compelled to modify their app. This is an important legal distinction in some jurisdictions.
- cvwright 11y agoI 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 agoThat 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...