5 ms·

Signal uses the same process. When you first install, it uploads all your contacts to 'see' which of your contacts are Signal users. It then defaults to Signa

Signal uses the same process. When you first install, it uploads all your contacts to 'see' which of your contacts are Signal users. It then defaults to Signal messages to that contact. Any new Signal user on your contact list alerts you to the fact they are now using Signal and helpfully defaults to Signal messaging. When you uninstall, you have to remove your number from their central DB using their web-app to prevent your friends from sending you Signal messages you won't be able to open. An implied "find my friend" feature that I assume Sarahah uses.

tgragnato 9y ago
Signal truncates the hashed phone numbers, before sending them to the server. The server responds with the contacts that you have in common.
- StavrosK 9y ago
  Does it really? I suggested that exact scheme months ago, but moxie rejected it as "not meaningfully privacy-preserving" (probably not his exact words), IIRC. Edit: Here: https://github.com/WhisperSystems/Signal-Android/issues/4726 https://github.com/WhisperSystems/Signal-Android/issues/4726
  - epipping 9y ago
    Here’s what moxie said: „[..] Signal has always done contact intersection with an ephemeral query of truncated hashes of phone numbers.„ See also https://news.ycombinator.com/item?id=11979748 https://news.ycombinator.com/item?id=11979748
  - Canada 9y ago
    Yes, it really does. Signal takes the first 10 bytes of a SHA1 hash of the e164 number, base64s it. An array of these "tokens" are sent to the server at registration time and every 12 hours thereafter. You can confirm this on both client and server code on Github. The problem, which no one denies, is that the small number of possible valid e164 values leaves the scheme vulnerable. Also, last time I checked you could submit like 10k tokens at once, so using a modest amount of IP addresses and phone numbers to bypass the rate limiting it is feasible to determine every registered number in a city. Restricting this is hard because some people have huge address books. The Silent Circle method is slightly better in my opinion, but not by much so I understand why Moxie doesn't want to bother changing it. Back when Redphone was a separate app it used a bloom filter scheme. There are really no good solutions to this problem. The safer ones currently know just don't scale.
    - baystep 9y ago
      As someone who is going to implement "find-my-friends" in this way, and wants to do it conscientiously, may I ask why only the first 10 bytes of the SHA1? Isn't that just an incomplete hash that could collide with other valid numbers?
      - nfriedly 9y ago
        I think it's much less likely to have collisions because the input space is so restricted (just valid phone numbers).
        jsjohnst 9y ago
        SHA-1 has approximately Random distribution, so it doesn't matter what the input is really in practice.
        saurik 9y ago
        The point of the person you are responding to essentially comes down to pidgeon hole principle (the best principle), and absolutely applies to a cryptographically random function, and is agnostic to the input distribution: it is a relative measure of information/entropy between two sets.
        jsjohnst 9y ago
        I agree with what you said, but I don't agree that's what the person implied by their post.
      - jsjohnst 9y ago
        Git defaults to using 7 hex characters for short hashs and doesn't see collisions for 95+% of repos. Even the Linux kernel repo with all its objects only needs 12 characters to ensure uniqueness.
        9y ago
  - saurik 9y ago
    FWIW, it isn't just not meaningfully privacy-preserving: it offers essentially no privacy preservation at all. There are 10 billion possible US phone numbers, and we know from Bitcoin that you can search that space in something like ten seconds on a typical PC. You also only have to do this once to construct a lookup table that would only take a terabyte to store and index, and then you could offer anyone instantaneous reverse lookup from truncated hash to phone number. It is essentially meaningless "privacy theater".
    - StavrosK 9y ago
      Alright, here's my truncated, hashed phone number, in E.164 format and SHA1: 4bbd8 What's the full number?
    - colejohnson66 9y ago
      You wouldn’t even need a terabyte if you didn’t mind comparing against every hash to find the right one. 16 bytes/number at 10 billion numbers is only 160 billion bytes (160 GB). Store the hashes one after another in a flat binary file, then `i` in `file[16*i]` is your number. If you included the 10 byte phone number, that only adds 100 GB. Then just store each entry as a 26 byte hash/number struct sorted by hash.

tgragnato 9y ago

Signal truncates the hashed phone numbers, before sending them to the server. The server responds with the contacts that you have in common.

StavrosK 9y ago
Does it really? I suggested that exact scheme months ago, but moxie rejected it as "not meaningfully privacy-preserving" (probably not his exact words), IIRC. Edit: Here: https://github.com/WhisperSystems/Signal-Android/issues/4726 https://github.com/WhisperSystems/Signal-Android/issues/4726
- epipping 9y ago
  Here’s what moxie said: „[..] Signal has always done contact intersection with an ephemeral query of truncated hashes of phone numbers.„ See also https://news.ycombinator.com/item?id=11979748 https://news.ycombinator.com/item?id=11979748
- Canada 9y ago
  Yes, it really does. Signal takes the first 10 bytes of a SHA1 hash of the e164 number, base64s it. An array of these "tokens" are sent to the server at registration time and every 12 hours thereafter. You can confirm this on both client and server code on Github. The problem, which no one denies, is that the small number of possible valid e164 values leaves the scheme vulnerable. Also, last time I checked you could submit like 10k tokens at once, so using a modest amount of IP addresses and phone numbers to bypass the rate limiting it is feasible to determine every registered number in a city. Restricting this is hard because some people have huge address books. The Silent Circle method is slightly better in my opinion, but not by much so I understand why Moxie doesn't want to bother changing it. Back when Redphone was a separate app it used a bloom filter scheme. There are really no good solutions to this problem. The safer ones currently know just don't scale.
  - baystep 9y ago
    As someone who is going to implement "find-my-friends" in this way, and wants to do it conscientiously, may I ask why only the first 10 bytes of the SHA1? Isn't that just an incomplete hash that could collide with other valid numbers?
    - nfriedly 9y ago
      I think it's much less likely to have collisions because the input space is so restricted (just valid phone numbers).
      - jsjohnst 9y ago
        SHA-1 has approximately Random distribution, so it doesn't matter what the input is really in practice.
        saurik 9y ago
        The point of the person you are responding to essentially comes down to pidgeon hole principle (the best principle), and absolutely applies to a cryptographically random function, and is agnostic to the input distribution: it is a relative measure of information/entropy between two sets.
        jsjohnst 9y ago
        I agree with what you said, but I don't agree that's what the person implied by their post.
    - jsjohnst 9y ago
      Git defaults to using 7 hex characters for short hashs and doesn't see collisions for 95+% of repos. Even the Linux kernel repo with all its objects only needs 12 characters to ensure uniqueness.
      - 9y ago
- saurik 9y ago
  FWIW, it isn't just not meaningfully privacy-preserving: it offers essentially no privacy preservation at all. There are 10 billion possible US phone numbers, and we know from Bitcoin that you can search that space in something like ten seconds on a typical PC. You also only have to do this once to construct a lookup table that would only take a terabyte to store and index, and then you could offer anyone instantaneous reverse lookup from truncated hash to phone number. It is essentially meaningless "privacy theater".
  - StavrosK 9y ago
    Alright, here's my truncated, hashed phone number, in E.164 format and SHA1: 4bbd8 What's the full number?
  - colejohnson66 9y ago
    You wouldn’t even need a terabyte if you didn’t mind comparing against every hash to find the right one. 16 bytes/number at 10 billion numbers is only 160 billion bytes (160 GB). Store the hashes one after another in a flat binary file, then `i` in `file[16*i]` is your number. If you included the 10 byte phone number, that only adds 100 GB. Then just store each entry as a 26 byte hash/number struct sorted by hash.