The Difficulty Of Private Contact Discovery • Hacker News Board

Re: The Difficulty Of Private Contact Discovery

#31

Post by josephlord » Fri, Jan 03, 2014, 9:58 PM UTC

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…

Could that mode be optional? Give the user the option protecting their contacts privacy at the cost of the large download or to trust your servers to delete the unmatched contacts.

Re: The Difficulty Of Private Contact Discovery

#32

Post by amix » Fri, Jan 03, 2014, 10:08 PM UTC

I don't really think you need to solve this problem using crypto. I think a simpler solution would be to use the "hash it" solution, but restrict how many lookups each client can do. You can either do this by the using the client's phone number, IP or other unique information etc. This way an attacker would have a very hard time brute forcing this.

Additionally you could use captchas (or other humanity tests, such as SMS verification) to limit hackers creating automated accounts (in order to fight automated bots spamming and polluting the network).

Re: The Difficulty Of Private Contact Discovery

#33

Post by sigil » Fri, Jan 03, 2014, 10:09 PM UTC

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…

So make contact discovery optional. My guess is most of your growth will come from that core of early adopters in the graph, and these folks have nice data plans / fast wifi and won't mind the 40MB download at all.

In the long term, where you're 10x or 50x where you are today, yes the filter size is a problem, but it's a "nice problem to have" as they say.

Side question: suppose I'm a less fortunate user of TextSecure, can I manually exchange keys with someone IRL? How does that work?

Re: The Difficulty Of Private Contact Discovery

#34

Post by [deleted] » Fri, Jan 03, 2014, 10:11 PM UTC

josephlord wrote: post #31

moxie wrote: post #28

Earlier quoted context omitted.

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…

Could that mode be optional? Give the user the option protecting their contacts privacy at the cost of the large download or to trust your servers to delete the unmatched contacts.

[deleted]

Re: The Difficulty Of Private Contact Discovery

#35

Post by mtrimpe » Fri, Jan 03, 2014, 10:13 PM UTC

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…

Aren't you essentially just offering the users to download as much data as they want to reduce the probability of 'collateral uploads' to levels that are acceptable for them?

Re: The Difficulty Of Private Contact Discovery

#36

Post by cortesoft » Fri, Jan 03, 2014, 10:16 PM UTC

amix wrote: post #32

I don't really think you need to solve this problem using crypto. I think a simpler solution would be to use the "hash it" solution, but restrict how many lookups each client can do. You can either do this by the using the client's phone number, IP or other unique information etc. This way an attacker would have a very hard time brute forcing this. Additionally you could use captchas (or other humanity tests, such as…

I think the point it to avoid having to trust the server. If you can trust the server not to do malicious things with the data, then you can do any number of techniques.

This post is about how to do contact lookup without having to trust the server to maintain privacy.

Re: The Difficulty Of Private Contact Discovery

#37

Post by milkshakes » Fri, Jan 03, 2014, 10:24 PM UTC

MagicWishMonkey wrote: post #29

sln wrote: post #26

Earlier quoted context omitted.

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.

They probably aren't trying to use TextSecure with their landlines though.

Re: The Difficulty Of Private Contact Discovery

#38

Post by fleitz » Fri, Jan 03, 2014, 10:32 PM UTC

It's not a technical problem it's a value prop problem. Most users don't care about privacy....

Fundamentally there is more value for the network operator to grow the network than for users to disclose their details. Email works perfectly fine without having to disclose your address book because no one owns the network and therefore do not care how many people are using email.

Alternatively one could just allow users to choose whether to make their info public and then the client can just search a directory.

Re: The Difficulty Of Private Contact Discovery

#39

Post by robrenaud » Fri, Jan 03, 2014, 10:32 PM UTC

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?

Re: The Difficulty Of Private Contact Discovery

#40

Post by amix » Fri, Jan 03, 2014, 10:36 PM UTC

cortesoft wrote: post #36

amix wrote: post #32

I don't really think you need to solve this problem using crypto. I think a simpler solution would be to use the "hash it" solution, but restrict how many lookups each client can do. You can either do this by the using the client's phone number, IP or other unique information etc. This way an attacker would have a very hard time brute forcing this. Additionally you could use captchas (or other humanity tests, such as…

I think the point it to avoid having to trust the server. If you can trust the server not to do malicious things with the data, then you can do any number of techniques. This post is about how to do contact lookup without having to trust the server to maintain privacy.

As I see it, the biggest current threat is bruteforcing of this service, at least based on the recent snapchat attack. And implementing rate limiting would solve this issue.

And given that this is a very hard problem to solve this kind of solution could be a good bandaid. Anyhow, this is at least my 2 cents on this issue.