4 ms·

Can't you just make the hash more expensive? Also, couldn't you regularly rotate salts?

by jsnathan 11y ago

geocar 11y ago
Ten character alpha numeric rainbow tables can be had for only a few thousand dollars.
- jsnathan 11y ago
  There cannot be precomputed tables for every custom hash computation. Especially an expensive one. Even less so if you add a salt. It could be made prohibitively costly for all but the most determined adversaries - and those could probably get your social graph much easier from other sources. Only problem I can see is it would take a few minutes after the app is installed to find your contacts..
  - maxerickson 11y ago
    You can't use a salt, the contact you want to match has to be able to compute the same hash. You can hash the contact pair instead of one side of it, but even then an attacker can rent X instances of some hardware that is Y times faster than your phone, so if you target a difficulty of ~1 second per contact on your phone, you get a difficulty of 2700 hours / XY for the attacker to recover all of your contacts So if Y is 10 times faster than your phone, you only need X=10 to recover the contacts for a given number in a day. If the attacker is willing to set X=1000, Y isn't even relevant.
    - jsnathan 11y ago
      > You can't use a salt, the contact you want to match has to be able to compute the same hash. I think the misunderstanding here is that I meant one salt for all users at a time, instead of one salt for each hash. And as long as stored hashes can be recomputed (by active users), the 'global salt' can be rotated over time. We can pre-compute hashes with future salts in case apps are not constantly online. Then we could rotate salts, say, once every 2 hours. The point being to make rainbow tables more expensive. > You can hash the contact pair instead of one side of it, but even then an attacker can rent X instances of some hardware that is Y times faster than your phone, so if you target a difficulty of ~1 second per contact on your phone, you get a difficulty of 2700 hours / XY for the attacker to recover all of your contacts > So if Y is 10 times faster than your phone, you only need X=10 to recover the contacts for a given number in a day. If the attacker is willing to set X=1000, Y isn't even relevant. I think this should be (10^10/3600 ~ 2.7 million hours) / XY. Also, let's say we can make it Y seconds (perhaps the hash is memory hard, etc). Then to compute a single table (per salt) we need 2.7e6 hours, at say $0.01 per hour, so $27k per table. Taken together that would mean to reveal the contacts of signups happening within a 2 hour window, would cost quite a sum. It's not secure, of course - but it does give some measure of privacy. If you think users are willing to wait more than an hour, you could 10x the cost too. But that's probably not practical anymore! Edit: Oh. I see I made a mistake here! If the server computes a single rainbow table it will be able to retroactively de-anonymize all users that are already active at that time! :( Sorry.
      - maxerickson 11y ago
        Yeah, somehow I missed a couple of zeros, it would be 2.7 million. Such a salt wouldn't tighten up the window though, for contact discovery to work, all the outputs have to be available to whatever is doing the matching.
        jsnathan 11y ago
        OK hold on. Say the rotating salt thing doesn't work, for whatever reason. But you yourself made a better suggestion! If we do hash (phone #) contact pairs, and every client publishes multiple hashes, one for each of its contacts, then a cheating server would need to compute (max) (10^10 * 10^10)/3600 ~ 2.7e17 hours worth of hashes. That would actually be secure, no? Edit: messed up the math myself this time; I think this is correct now though
        maxerickson 11y ago
        For the contact discovery to be private, the phone has to calculate the hash. So the server cost also depends on the performance differential (many entities would likely still spend $50,000 to discover the contacts of a high value target). Adding information increases the cost, but it also reduces the likelihood of a match. You've edited your comment since I wrote the above. Anyway, if the attack is directed at a single user, there's only one 10^10 involved (and really, the phone number space isn't that big).
        jsnathan 11y ago
        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.
  - dfox 11y ago
    The point is that the hash needs to be same for all users, so salts are out of question and custom hashing schemes does not help you as the assumed installed base is significant.
    - jsnathan 11y ago
      See my sibling comment about the salt. As long as hashes are computed client-side, I don't see why the size of the installed base matters?
      - dfox 11y ago
        Size of installed base matters because it is perfect argument for why using some weird custom hashing does not solve anything as all clients have to use the same algorithm and when your network is interesting target it is also big enough to account for whatever effort is required to break the hash by brute force or generate useful rainbow tables.
newman314 11y ago
As I noted in another comment, I don't think this is the right solution. I would argue that things need to be tied to an identifier other than the phone number. Therefore, if something does happen, it's much lower friction to simply reset the identifier. To deal with some of the UX pain, one could force a voice call requirement instead of just a fingerprint reverification.

Can't you just make the hash more expensive? Also, couldn't you regularly rotate salts?

geocar 11y ago

Ten character alpha numeric rainbow tables can be had for only a few thousand dollars.

jsnathan 11y ago
There cannot be precomputed tables for every custom hash computation. Especially an expensive one. Even less so if you add a salt. It could be made prohibitively costly for all but the most determined adversaries - and those could probably get your social graph much easier from other sources. Only problem I can see is it would take a few minutes after the app is installed to find your contacts..
- maxerickson 11y ago
  You can't use a salt, the contact you want to match has to be able to compute the same hash. You can hash the contact pair instead of one side of it, but even then an attacker can rent X instances of some hardware that is Y times faster than your phone, so if you target a difficulty of ~1 second per contact on your phone, you get a difficulty of 2700 hours / XY for the attacker to recover all of your contacts So if Y is 10 times faster than your phone, you only need X=10 to recover the contacts for a given number in a day. If the attacker is willing to set X=1000, Y isn't even relevant.
  - jsnathan 11y ago
    > You can't use a salt, the contact you want to match has to be able to compute the same hash. I think the misunderstanding here is that I meant one salt for all users at a time, instead of one salt for each hash. And as long as stored hashes can be recomputed (by active users), the 'global salt' can be rotated over time. We can pre-compute hashes with future salts in case apps are not constantly online. Then we could rotate salts, say, once every 2 hours. The point being to make rainbow tables more expensive. > You can hash the contact pair instead of one side of it, but even then an attacker can rent X instances of some hardware that is Y times faster than your phone, so if you target a difficulty of ~1 second per contact on your phone, you get a difficulty of 2700 hours / XY for the attacker to recover all of your contacts > So if Y is 10 times faster than your phone, you only need X=10 to recover the contacts for a given number in a day. If the attacker is willing to set X=1000, Y isn't even relevant. I think this should be (10^10/3600 ~ 2.7 million hours) / XY. Also, let's say we can make it Y seconds (perhaps the hash is memory hard, etc). Then to compute a single table (per salt) we need 2.7e6 hours, at say $0.01 per hour, so $27k per table. Taken together that would mean to reveal the contacts of signups happening within a 2 hour window, would cost quite a sum. It's not secure, of course - but it does give some measure of privacy. If you think users are willing to wait more than an hour, you could 10x the cost too. But that's probably not practical anymore! Edit: Oh. I see I made a mistake here! If the server computes a single rainbow table it will be able to retroactively de-anonymize all users that are already active at that time! :( Sorry.
    - maxerickson 11y ago
      Yeah, somehow I missed a couple of zeros, it would be 2.7 million. Such a salt wouldn't tighten up the window though, for contact discovery to work, all the outputs have to be available to whatever is doing the matching.
      - jsnathan 11y ago
        OK hold on. Say the rotating salt thing doesn't work, for whatever reason. But you yourself made a better suggestion! If we do hash (phone #) contact pairs, and every client publishes multiple hashes, one for each of its contacts, then a cheating server would need to compute (max) (10^10 * 10^10)/3600 ~ 2.7e17 hours worth of hashes. That would actually be secure, no? Edit: messed up the math myself this time; I think this is correct now though
        maxerickson 11y ago
        For the contact discovery to be private, the phone has to calculate the hash. So the server cost also depends on the performance differential (many entities would likely still spend $50,000 to discover the contacts of a high value target). Adding information increases the cost, but it also reduces the likelihood of a match. You've edited your comment since I wrote the above. Anyway, if the attack is directed at a single user, there's only one 10^10 involved (and really, the phone number space isn't that big).
        jsnathan 11y ago
        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.
- dfox 11y ago
  The point is that the hash needs to be same for all users, so salts are out of question and custom hashing schemes does not help you as the assumed installed base is significant.
  - jsnathan 11y ago
    See my sibling comment about the salt. As long as hashes are computed client-side, I don't see why the size of the installed base matters?
    - dfox 11y ago
      Size of installed base matters because it is perfect argument for why using some weird custom hashing does not solve anything as all clients have to use the same algorithm and when your network is interesting target it is also big enough to account for whatever effort is required to break the hash by brute force or generate useful rainbow tables.

newman314 11y ago

As I noted in another comment, I don't think this is the right solution. I would argue that things need to be tied to an identifier other than the phone number. Therefore, if something does happen, it's much lower friction to simply reset the identifier. To deal with some of the UX pain, one could force a voice call requirement instead of just a fingerprint reverification.