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

61–70 of 76 posts

Re: The Difficulty Of Private Contact Discovery

#61

Post by goatslacker »

stormbrew wrote: post #54
robrenaud wrote: post #39

Is this a real problem? Is it reasonable to trust for me to trust you to you run some arbitrary binary on my phone that does some magical black box computation on my contact list and then phone home to your service, but not trust to that you will just not be a dick with the raw data? Stated more simply, if I am paranoid about my privacy, then why am I running your apps and letting you read my contact list at all?

Agreed. The whole thing seems to really miss the problem Snapchat exposed, turning an access control problem into a cryptographic problem. At least I assume this is being posted now because of snapchat. The problem with how snapchat failed isn't so much that they weren't storing the information securely but that they had absolutely no gate on getting the information aside from a global api key. If you're running thei…

They are two separate problems.

The problem is that an application requests your contacts, uploads them to their server, and then who knows what they do with that information afterwards; maybe they store it, perhaps later that database is leaked, or they sell the stored information in the future.

If you trust the service you're using fully (you trust the server will not be compromised, the owners of the servers will not cave to demands to store/release data, the owners will not be malicious with your data) then this isn't a problem at all. Transmit the raw data over SSL then perform the checks and do not store the data.

Re: The Difficulty Of Private Contact Discovery

#62

Post by Strilanc »

40 MiB for ten million users? I think you should ditch the bloom filter if the false-positive rate is set so low it takes that much space.

Assuming you can map phone numbers onto the integers from 0 to ten billion, trivial compression of the is-a-user/is-not-a-user bit sequence should easily fit in ~14MiB [1].

See also: succinct data structures [2] for accessing data without decompressing it.

(This is obviously a short term solution. Growth will overcome the savings.)

1: http://www.wolframalpha.com/input/?i=%28-p+lg_2%28p%29-%281-...

2: http://en.wikipedia.org/wiki/Succinct_data_structure

Re: The Difficulty Of Private Contact Discovery

#63

Post by MagicWishMonkey »

ww520 wrote: post #57
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…

There similarity hash algorithms that takes a fuzzy approach to hashing slightly different values to the same hash value.

The SHA256 algorithm described in the article is not a fuzzy algorithm.

Re: The Difficulty Of Private Contact Discovery

#64

Post by russellsprouts »

jahewson wrote: post #48

Could you use an enormously expensive hash function so that building a lookup table is infeasible?

Assuming you want to try every phone number in the US, that would be almost 10 billion phone numbers. An above average user may have about 1,000 contacts. We want this to run on phones in a reasonable time for 1000 contacts, but be infeasible for 10 billion using any hardware the attacker uses.

Bitcoin gives an idea of the relative speeds. I looked up the speeds of some Android bitcoin miners. All were on the order of 10Khash/s.

The attacker is not constrained to use phones. Custom hardware for BitCoin mining can be on the order of 1Thash/s.

This means that the custom hardware can reach 10^8 times faster, but the work to be done -- 10 billion hashes vs. 1000, is only 10^7 times as much. If the slow hashing algorithm used was anything like the one for BitCoins, a determined attacker could calculate the entire table faster than the person looking up their contacts.

This is not the whole story -- this could be mitigated using better hashing algorithms that are designed to not scale well with better hardware, but the user will only wait maybe a minute, while an attacker could spend weeks.

Re: The Difficulty Of Private Contact Discovery

#65

Post by napoleond »

ash wrote: post #12
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.

It seems to me like that fits somewhere in the space between "small compromise" and "bonus feature". This idea seems like a very good practical solution--I'm very curious what moxie's take on it would be.

Re: The Difficulty Of Private Contact Discovery

#66

Post by jahewson »

russellsprouts wrote: post #64
jahewson wrote: post #48

Could you use an enormously expensive hash function so that building a lookup table is infeasible?

Assuming you want to try every phone number in the US, that would be almost 10 billion phone numbers. An above average user may have about 1,000 contacts. We want this to run on phones in a reasonable time for 1000 contacts, but be infeasible for 10 billion using any hardware the attacker uses. Bitcoin gives an idea of the relative speeds. I looked up the speeds of some Android bitcoin miners. All were on the order o…

This is a great answer.

Re: The Difficulty Of Private Contact Discovery

#67

Post by danielrhodes »

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…

This times a million.

Phone numbers in particular can be a horrid mess to deal with. Some decent libraries have come out to normalize them, but in general it remains difficult.

For example:

013811234 +88-1-3811234 3811234 0118813811234 008813811234

are all be the same number.

To hash them, you could naively just strip off the area codes and country codes, but that is only if you can know ahead of time they are indeed area or country codes. Some countries have 7 digit numbers, others have 9, some have 6, or even 5 digits. Sometimes you don't even know the country to apply these rules to.

Re: The Difficulty Of Private Contact Discovery

#68

Post by stormbrew »

goatslacker wrote: post #61
stormbrew wrote: post #54

Earlier quoted context omitted.

Agreed. The whole thing seems to really miss the problem Snapchat exposed, turning an access control problem into a cryptographic problem. At least I assume this is being posted now because of snapchat. The problem with how snapchat failed isn't so much that they weren't storing the information securely but that they had absolutely no gate on getting the information aside from a global api key. If you're running thei…

They are two separate problems. The problem is that an application requests your contacts, uploads them to their server, and then who knows what they do with that information afterwards; maybe they store it, perhaps later that database is leaked, or they sell the stored information in the future. If you trust the service you're using fully (you trust the server will not be compromised, the owners of the servers will…

Yes, this is what I'm saying. It is two separate problems but the only one people seem interested in addressing is the one that is probably not the problem for most people.

Like it or not, people do overtrust companies like snapchat. We need to change that too.

But in the mean time, snapchat's biggest and first mistake was to leave their database an open book without even having to compromise their service or servers. The people who did this used nothing that their client application doesn't use every day, and that is not an unsolvable problem at all. It's no different a problem than every single social network already has to solve, whether their users trust them to encrypt or otherwise obscure their data once obtained or not.

Re: The Difficulty Of Private Contact Discovery

#69

Post by Illniyar »

What about artificially increasing the size of the hash input. For instance: when finding out if a a contact exists the client sends 10 iterations of the contact (I.E. the contact number with another digit, each 0-9) hashed, the server keeps only one random hashed one to compare to (presumably the client hashes one of them randomly when sending it's own contact information).

That way you increase the size of the problem from 10^10 to 10^11 but only increase your bandwidth 10 fold.

It still keeps the need to balance the amount of bandwidth used, but the bandwidth is no longer determined by the amount of all the users in the system, only the increase in problem size and the amount of contacts a person has.

Is that a worthwhile solution?

Re: The Difficulty Of Private Contact Discovery

#70

Post by petermonsson »

moxie wrote: post #28
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…

Ideas

1) Bundle a snapshot of the global contact list with the APK. Assume that end users will be on 3G or WI-FI when installing the program. I suppose that is is worth looking at the assumption about what is the largest download that we can live with under EDGE. The current TextSecure APK is 2.5MB as far as I can tell. The best case for the APK download is 1.4 minutes (236kbit/s). If the size is essentially zero, then we need to move to idea 2.

2) Split the rate-limiter into an anonymous proxy controlled by a partially trusted third party. Open Whisper Systems controls the database, but not the proxy. Open Whisper Systems doesn't know where the request comes from. The rate limiter doesn't know what is requested.

Edit: forgot to complete a sentence

Post reply on HN