[whispersystems] Suggestion for partial fix of contact privacy issue.

[abc def]

Regarding this: https://whispersystems.org/blog/contact-discovery/

Sorry if this has already been addressed but a cursory search has not
turned up any new information.

The way I see it, the solution isn't algorithmic, it's simple data padding.
As put forth in the post, a single phone number is simply too short in
length to stop pre-computation attacks.

Since both users are required to be on Signal to connect with each other we
can assume that both users must have the phone number of the other.

If we use U.S. numbers as a simple example (I would recommend a
standardized international format for the actual implementation) then 2
phone numbers concatenated together doubles our message length to 18
digits; or 10^18 possibilities before excluding invalid number combinations.

Combine that with a standardized sort and any 2 users can find each other
as long as each has the other one's number.

For instance:

User A (299-555-0113) and User B (218-555-1945) both install Signal

User A concatenates their phone number with every other phone number in
their address book, sorting by trivial alphanumerics in a neutral collation.
When User A hits User B's phone number they end up with
218-555-0113/299-555-1945.
User A uploads the hashes of all the concatenated phone numbers.
For User B this would be Hash(218-555-0113/299-555-1945).

User B does the same and when User B hits User A's phone number, they end
up with the same hash due to sorting before concatenation and hashing.

User A and User B can now upload their contacts without an adversary being
able to tell which contacts User A or B has unless they already know the
connection between User A and User B exists.

Changing to an international phone number format helps even more as we now
end up with an even larger message of varying length.

Thanks

[Justin Tracey]

This is still far too little entropy to be practically useful. 20
decimal digits from two phone numbers provides *at most* 66 bits of
combinatorial space. This is "a lot" for someone's laptop or
something, but well within the realm of current feasibility. Hell,
it's only 2 bits more than DES. And unlike DES, this computation only
has to happen once, at which point someone can upload it to the
internet and the system suddenly provides almost no security at all.

And that's just a dragnet attack. You factor in a targeted attack,
where one of the two phone numbers is already known, and you're back
to brute forcing a 10 digit number (obviously, a trivial thing to do).
And if it's even more targeted, in that they want to know "Is Alice in
contact with Bob?" there's no overhead at all, other than what Alice
and Bob already have to do on their phones.

- Justin

[Laurence Berland]

Setting aside how it affects security or privacy, it would be a change to
existing semantics, in that I don't currently need to be someone's *mutual*
contact to send them signal messages. Eg today someone gives me their
number, I can message them by way of introduction so that they'll have my
number too. With this system we'd have to exchange numbers both ways
*before* we could message.

On Mon, Feb 15, 2016 at 3:31 AM, TiagoTiago <

Wouldn't this actually reduce privacy by creating a long lasting record of
who you have in your contacts list that is publicly accessible (anyone that
wants to check if you got a number in your contacts can pretend to be you
and send ask the server about the hash), instead of the brief disclosure
between you and the server of the current system that is only accessible to
an attacker that has compromised the server?

Post by Justin Tracey
This is still far too little entropy to be practically useful. 20
decimal digits from two phone numbers provides *at most* 66 bits of
combinatorial space. This is "a lot" for someone's laptop or
something, but well within the realm of current feasibility. Hell,
it's only 2 bits more than DES. And unlike DES, this computation only
has to happen once, at which point someone can upload it to the
internet and the system suddenly provides almost no security at all.
And that's just a dragnet attack. You factor in a targeted attack,
where one of the two phone numbers is already known, and you're back
to brute forcing a 10 digit number (obviously, a trivial thing to do).
And if it's even more targeted, in that they want to know "Is Alice in
contact with Bob?" there's no overhead at all, other than what Alice
and Bob already have to do on their phones.
- Justin