Really sorry about the edits! Thinking in real time :)
So about the size of the phone number space. Interestingly I guess you could at least limit it by country.
But, unless you already know the mobile phone numbers of the target's acquaintances, (in which case there is no real danger of 'leaking' your social graph),
you can't really limit it more, because mobile phone numbers are pretty random within each country's phone number space (I think).
So say the US has at least 0.5 billion assigned mobile numbers, and you don't know which are assigned, so the space could easily be 10^10 for just the US.
(I can't find any quick numbers on Google right now).
But even if we go down to say, 100 million, we would still get (10^7 * 10^7)/3600 ~ 2.7e11 hours worth of hashing to get all contact pairs. Which is still secure.
Now as far as limiting one end point to a single phone number - that would be a special case. I'm not sure if this isn't moving the goal post a bit.
As long as the server does not have access to your own phone number, it, or anyone who has hacked into the server,
cannot really use that to limit their computations. Unless they are already targeting you through other means (possibly you are a person of interest to someone), and so know your phone #.
In that case yes, they could reveal (part of) your social graph for a (maybe) affordable cost. But in that very special case, I think we are dealing with nation-state adversaries.
And in that case, the telcos probably already have a list of your phone # contacts. So it would probably be easier to simply get it from them.
The only thing left to be revealed would be that you communicated with a specific acquaintance using that particular app, at some particular time.
So a targeted attack could leak that metadata.
It's not perfect.. but I think it might just be good enough for most users.
If we go off the deep end with an attack tailored to a single phone #, we also have to worry about a whole lot of other attack vectors that are probably more important.
Lastly, note that the user (if sufficiently paranoid) could simply opt out of the automatic contact search post-install.
As for mobile phone numbers being randomly placed inside larger space of all phone numbers, while this makes some sense for US/NANP, in most of the rest of the world mobile numbers have some semi-well defined prefixes (as in "number that starts with 6 or 7 is certainly mobile phone, discerning what operator is sligthly non-trivial") and even for NANP there probably is some publicly available database that says whether given number is mobile or not.
I don't think it's moving the goalposts, the ability to focus an attack on an individual number is an important consideration for an individual evaluating the system. That only their contacts are revealed is not much consolation when their contacts are revealed.
The ability to move out to the phone network at observe metadata there does make the discussion somewhat academic.
So about the size of the phone number space. Interestingly I guess you could at least limit it by country. But, unless you already know the mobile phone numbers of the target's acquaintances, (in which case there is no real danger of 'leaking' your social graph), you can't really limit it more, because mobile phone numbers are pretty random within each country's phone number space (I think).
So say the US has at least 0.5 billion assigned mobile numbers, and you don't know which are assigned, so the space could easily be 10^10 for just the US. (I can't find any quick numbers on Google right now).
But even if we go down to say, 100 million, we would still get (10^7 * 10^7)/3600 ~ 2.7e11 hours worth of hashing to get all contact pairs. Which is still secure.
Now as far as limiting one end point to a single phone number - that would be a special case. I'm not sure if this isn't moving the goal post a bit.
As long as the server does not have access to your own phone number, it, or anyone who has hacked into the server, cannot really use that to limit their computations. Unless they are already targeting you through other means (possibly you are a person of interest to someone), and so know your phone #.
In that case yes, they could reveal (part of) your social graph for a (maybe) affordable cost. But in that very special case, I think we are dealing with nation-state adversaries.
And in that case, the telcos probably already have a list of your phone # contacts. So it would probably be easier to simply get it from them.
The only thing left to be revealed would be that you communicated with a specific acquaintance using that particular app, at some particular time.
So a targeted attack could leak that metadata.
It's not perfect.. but I think it might just be good enough for most users.
If we go off the deep end with an attack tailored to a single phone #, we also have to worry about a whole lot of other attack vectors that are probably more important.
Lastly, note that the user (if sufficiently paranoid) could simply opt out of the automatic contact search post-install.