Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Difficulty Of Private Contact Discovery

whispersystems.org

Post reply on HN
Print view View original

11–20 of 76 posts

Re: The Difficulty Of Private Contact Discovery

#11

Post by sigil »

abentspoon wrote: post #9

What 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 infor…

The problem with this is that (1) + (2) means the server now knows the user's address book. They're trying to avoid that with encrypted bloom filters and blind signature queries.

Re: The Difficulty Of Private Contact Discovery

#12

Post by ash »

maxerickson wrote: post #3

In 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.

Interesting idea. But the address book "friends" must be mutual for this to work. You would miss those contacts that don't have you in the their contacts.

Re: The Difficulty Of Private Contact Discovery

#13

Post by ash »

abentspoon wrote: post #9

What 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 infor…

How would you do (2) without iterating over all registered contacts on the server?

Re: The Difficulty Of Private Contact Discovery

#14

Post by abentspoon »

ash wrote: post #13
abentspoon wrote: post #9

What 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 infor…

How would you do (2) without iterating over all registered contacts on the server?

Good point. Now I understand why they were suggesting bucketing.

I came up with this method for maintaining privacy while retrieving installed apps (to give app recommendations). Sounds like it might not translate across so well.

Re: The Difficulty Of Private Contact Discovery

#15

Post by mtrimpe »

spullara wrote: post #10
herge wrote: post #5

Earlier quoted context omitted.

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.

Properly implemented rate limiting would be a better way to achieve that though. That is were the 'blinding signature' part comes in: to give the server the possibility to intelligently rate limit.

Re: The Difficulty Of Private Contact Discovery

#16

Post by jen_h »

ash wrote: post #7
pyrocat wrote: post #6

So 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.

Not everyone wants to be found; and not everyone wants to find every single contact in their phone. Especially for something like RedPhone whose purported aim is user privacy and security...I'm not sure why they'd want to even touch 5000+ contacts from a single user (or why someone who used RedPhone would want to have them scan every contact on their phone), even if they do use some kind of magical unicorn encryption sauce.

Re: The Difficulty Of Private Contact Discovery

#17

Post by jcampbell1 »

I understand how the Encrypted Bloom Filter they describe keeps my contacts private from the service, but it seems to leak the entire contact list the same as the trivial solution:

I install millions of copies of the app, all with a different contact list. I do this signed query process for every possible phone number. I now have the complete list of users.

Re: The Difficulty Of Private Contact Discovery

#18

Post by mtrimpe »

sigil wrote: post #4

Interesting 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…

Indeed; if I understand it correctly encrypted data goes into a standard bloom filter.

If that's indeed the case then, assuming that users can never be removed, a daily update would just contain the indexes of the additional bits set by the newly registered users, which could never be 40MB.

It seems they also forgot to include lowering the p-value of the bloom filter as a trade-off, since it seems that a false positive means that a contact is sent to the server which shouldn't have been.

If you push that down to p=.95/.98/.99 or so you'd get a much smaller Bloom filter and many people might not object to a few % of 'collateral uploads' so to speak.

Minimizing the amount of information leaked through these various tradeoffs is an interesting problem though, since you'll have to leak something one way or the other.

Re: The Difficulty Of Private Contact Discovery

#19

Post by MagicWishMonkey »

This is great until you realize the average address book is a disgusting mess of spelling errors, wrong values in wrong fields, punctuation in places where punctuation isn't necessary (commas in phone number fields, digits in name fields, etc.)

The only field that might be fairly consistent is email address and even that is no guarantee. Sure, it's possible to clean up a contact before hashing, but when you consider the fact that the typical phone contains >500 contacts it's not something that can be done in a reasonable amount of time on a modern smartphone. For the last two years I've been working on a product that involves cleaning/organizing contacts and making them searchable, when I started I had no idea what a massive undertaking it would be.

So, hash till your hearts content, but if you have 10 different people with the same contact in their address book I would be willing to bet that you will get 10 different hashes because humans are not good at data entry.

Re: The Difficulty Of Private Contact Discovery

#20

Post by jokull »

MagicWishMonkey wrote: post #19

This is great until you realize the average address book is a disgusting mess of spelling errors, wrong values in wrong fields, punctuation in places where punctuation isn't necessary (commas in phone number fields, digits in name fields, etc.) The only field that might be fairly consistent is email address and even that is no guarantee. Sure, it's possible to clean up a contact before hashing, but when you consider…

Where can I find your app?
Post reply on HN