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

21–30 of 76 posts

Re: The Difficulty Of Private Contact Discovery

#21

Post by MagicWishMonkey »

herge wrote: post #5
spullara wrote: post #2

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

Phone numbers are not unique values, you should never assume that a phone number alone (or even a phone number and last name) is enough information to uniquely identify an individual.

Case in point: I work with a guy who used to work at his dads office. He and his dad both have the same name, and they both had the same office number. This algorithm would incorrectly identify both people as being the same person when in fact they are not.

Re: The Difficulty Of Private Contact Discovery

#22

Post by MagicWishMonkey »

jokull wrote: post #20
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?

It's not public yet (focused on the enterprise space right now), I'll send you a pm to our website.

edit not sure how to do a pm here, if you use reddit send me a private message user/MagicWishMonkey

Re: The Difficulty Of Private Contact Discovery

#23

Post by cristiantincu »

> Building a social network is not easy. Social networks have value proportional to their size, so participants aren’t motivated to join new social networks which aren’t already large. It’s a paradox where if people haven’t already joined, people aren’t motivated to join.

Value is relative. For stakeholders, value is indeed given by the network’s size. For users (participants), it’s very debatable whether size equals value. The author seems to be mistaking the two perspectives for a single one. No paradox here.

Re: The Difficulty Of Private Contact Discovery

#24

Post by abentspoon »

sigil wrote: post #11
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.

First, it looks like this scheme is broken due to cpu constraints. However...

It had looked more like the encrypted bloom filter was intended to prevent the client from obtaining the list of registered users.

With (1) + (2), the server only has a few bits of information about each of the phone's contacts. It would be analogous to just having the area codes.

Re: The Difficulty Of Private Contact Discovery

#25

Post by moxie »

jcampbell1 wrote: post #17

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.

This post is about building untrusted servers, which is somewhat orthogonal to "the snapchat problem."

The best a privacy preserving protocol can hope to achieve is to match the characteristics of its non-privacy preserving equivalent.

Asymmetric PIR (the server transmits an unencrypted bloom filter) falls short of the non-privacy preserving equivalent, since the user makes offline queries that can't be rate limited by the server. Symmetric PIR (the server transmits an encrypted bloom filter) provides identical properties to the non-privacy preserving equivalent, since the user needs to make queries that can be rate limited by the server, even though the queries leak no information to the server.

How that rate limiting (or unlisted numbers, or whatever) works is outside the scope of the protocol, just as it is in the non-privacy preserving case. For TextSecure, you'd need to verify 1 million phone numbers in order to perform your attack. Whether you can do that or not isn't really the point: we simply want to do as least as well as everyone else, without revealing information to the server.

Re: The Difficulty Of Private Contact Discovery

#26

Post by sln »

MagicWishMonkey wrote: post #21
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.

Phone numbers are not unique values, you should never assume that a phone number alone (or even a phone number and last name) is enough information to uniquely identify an individual. Case in point: I work with a guy who used to work at his dads office. He and his dad both have the same name, and they both had the same office number. This algorithm would incorrectly identify both people as being the same person when…

Phone numbers are unique values when you need to call a phone or send an SMS, which is what this software does. If you were trying to do your taxes, sure...but in this case a phone number is exactly enough.

Re: The Difficulty Of Private Contact Discovery

#27

Post by mtrimpe »

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 biggest problem with that is:

1) Client uploads a bloom filter consisting entirely of ones.

2) Server responds by sending its entire contact database.

Re: The Difficulty Of Private Contact Discovery

#28

Post by moxie »

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…

Our feeling is that 40MB for an initial download is not acceptable on mobile devices, particularly in many of the areas we'd like to support. Maybe we're wrong, but it seems like too much on edge networks, particularly given that it's only going to grow as more users join. Ideally we'd have 100MM or 500MM, not just 10MM.

We can definitely make lightweight diffs happen, but that initial download is tough, and is going to get tougher.

Re: The Difficulty Of Private Contact Discovery

#29

Post by MagicWishMonkey »

sln wrote: post #26
MagicWishMonkey wrote: post #21

Earlier quoted context omitted.

Phone numbers are not unique values, you should never assume that a phone number alone (or even a phone number and last name) is enough information to uniquely identify an individual. Case in point: I work with a guy who used to work at his dads office. He and his dad both have the same name, and they both had the same office number. This algorithm would incorrectly identify both people as being the same person when…

Phone numbers are unique values when you need to call a phone or send an SMS, which is what this software does. If you were trying to do your taxes, sure...but in this case a phone number is exactly enough.

Lots of folks still use land lines.

Re: The Difficulty Of Private Contact Discovery

#30

Post by nwzpaperman »

I probably need to build a quantum shor computer so the brightest minds can get back to engineering optimizations and efficiencies for our very finite lives so we can all experience rich non-Internet lives again.

TCP/IP is the original decentralized communication system. With the exception of the Thaler, the Internet has the largest social graph.

Obfuscating communications with ever increasing orders of complexity in the quest for internet privacy is a wasteful endeavor according to Goedel's incompleteness theorem.

This is just Rado's busy beaver game by a different name. At the halt, we will have moxie talking to himself. How social is that?

We've lost two decades of PhDs to structured finance and now we look poised to lose a couple more decades worth in pursuit of Internet privacy only to realize public places are not private places.

http://www.youtube.com/watch?v=YIkoSPqjaU4

Post reply on HN