The Difficulty Of Private Contact Discovery
whispersystems.org
The Difficulty Of Private Contact Discovery
1–10 of 76 posts
Re: The Difficulty Of Private Contact Discovery
#2I think there is a big difference between private contact discovery and contact discovery that isn't brute forceable like we are seeing with SnapChat and others. One change that could be made for these very small pre image corpuses would be to ask the target user if they should be exposed to the searcher.
1) I upload the hashes of my contacts which enqueues a request to those that match the hashes
2) The target of the request dequeues those requests and is given the option to expose themselves to the other user
3) If approved, the original uploader gets access to that user on the service
This would stop the massive discovery issue and would only put a medium amount of friction into the growth engine. It obviously doesn't cover the issue that the service itself has access to the contacts which means they could potentially be exposed. However, if the service discards hashes without matching queues and removes matches when dequeued, the risk to the user is much reduced from the full address book storage case.
This was written off the top of my head, so forgive me if I have left a big hole somewhere.
Re: The Difficulty Of Private Contact Discovery
#3In a similar discussion, I said something about hashing phone number pairs. The graph has a lot more edges than nodes.
Still doesn't stop someone from attacking a single number though.
Re: The Difficulty Of Private Contact Discovery
#4Interesting problem!
> It’s also possible to compress “updates” to the bloom filter. The server just needs to calculate the XOR of the version the client has and the updated version, then run that through LZMA (the input will be mostly zeros), and transmit the compressed diff to the client.
> Unfortunately, for a reasonably large user base, this strategy doesn’t work because the bloom filters themselves are too large to transmit to mobile clients. For 10 million TextSecure users, a bloom filter like this would be ~40MB, requested from the server 116 times a second if every client refreshes it once a day.
Wait, the LZMA-compressed daily diffs would be still be ~40MB? If the 40MB is just the initial bloom filter download, that's not so bad. If 40MB is the daily diff, I'd be interested in seeing the calculation for that.
Re: The Difficulty Of Private Contact Discovery
#5I think there is a big difference between private contact discovery and contact discovery that isn't brute forceable like we are seeing with SnapChat and others. One change that could be made for these very small pre image corpuses would be to ask the target user if they should be exposed to the searcher. 1) I upload the hashes of my contacts which enqueues a request to those that match the hashes 2) The target of th…
RTFA. He addresses that in the first few paragraphs. Because there are 10^10 possible phone numbers (approximately), it is very easy to build a rainbow table of all hashed phone numbers and back-track a hash to it's phone number.
Re: The Difficulty Of Private Contact Discovery
#6So don't do it. I know I'm probably in the minority here but I've never given another app permission to use my facebook or twitter account to "Find Friends" and I personally find the whole practice offensive. Just have an option to invite people by their email address/number/whatever, but not in bulk.
Re: The Difficulty Of Private Contact Discovery
#7So don't do it. I know I'm probably in the minority here but I've never given another app permission to use my facebook or twitter account to "Find Friends" and I personally find the whole practice offensive. Just have an option to invite people by their email address/number/whatever, but not in bulk.
You seem to dislike inviting a bulk of friends to a service. But the article doesn't talk about invites. The problem is securely discovering who's already invited. It's not offensive in my opinion.
Re: The Difficulty Of Private Contact Discovery
#8[deleted]
Re: The Difficulty Of Private Contact Discovery
#9What about this?
1) Client uploads a bloom filter with all contacts on phone
2) Server responds with a bloom filter with all registered contacts that match the client's bloom filter
3) Client displays contacts that match server's bloom filter
You can optionally trade contacts back and forth again with a larger bits/contact ratio to decrease false positives.
I think it works out so that in exchange for 7 bits of information about each contact from the client, you can reduce the server's response by a factor of 128.
Re: The Difficulty Of Private Contact Discovery
#10I think there is a big difference between private contact discovery and contact discovery that isn't brute forceable like we are seeing with SnapChat and others. One change that could be made for these very small pre image corpuses would be to ask the target user if they should be exposed to the searcher. 1) I upload the hashes of my contacts which enqueues a request to those that match the hashes 2) The target of th…
RTFA. He addresses that in the first few paragraphs. Because there are 10^10 possible phone numbers (approximately), it is very easy to build a rainbow table of all hashed phone numbers and back-track a hash to it's phone number.
Well, actually I did read the article and address that in my comment that I don't think that it is important to hide the address from the server but it is important to hide them from the brute force attacker. I believe that my suggestion stops a brute force attacker from pulling the whole database like you can today with many of these systems.