3 ms·

> The obvious problem with this method is that the hash of a user identifier can almost always be inverted. Regardless of whether the identifier is a phone numb

> The obvious problem with this method is that the hash of a user identifier can almost always be inverted. Regardless of whether the identifier is a phone number, a user name, or an email address, the “keyspace” of all possible identifiers is too small. What does "inverted" mean here? And why is the keyspace too small? And how do these problems relate to not trusting the server? The problem definition and proposed solution don't seem to match to me, even though what they have solved is cool.

chrissnell 9y ago
Take every possible 10-digit U.S. phone number, for example, and perform a SHA-256 hash on each. Put those phone numbers and their hashes in a lookup table. Now, when a hashed phone number comes in from an anonymous user, look it up in that table and you now know the actual phone number.
- abovemypaygrade 9y ago
  I'm not an expert, so bear with me. Could this be thwarted by, say, having Signal add a random salt to every registering number and then advertising the hash of (number)+(random salt) as the final contact, invisible to the end user? Or would that involve Signal maintaining too much information on their users? If that's the case, I could see that being a problem.
  - azdle 9y ago
    The problem with salting the hashes is that they then become useless for contact discovery. The only way I can think of to make it work would require sharing the salt with people trying to find you, but then at that point you just share a real user identifier and short-circuit the whole process happening here.
    - abovemypaygrade 9y ago
      The way I was initially picturing it would involve Signal keeping track of the salt they assigned to the contact number, with that specific salt maybe 'expiring' after a certain number of days (to get rid of salts where someone registered with Signal, didn't like it, and never registered again). After thinking about it some more, I realized that this would probably lead OWS to collecting big lists of registered users and their contact patterns, which goes against their policy of trying to retain as little data as possible.
jlgaddis 9y ago
Imagine you're storing a four-digit PIN (or even 10-digit phone numbers in the U.S.) and you decide to hash them with SHA256 because security. The key space -- the total number of all possible PINs -- is really small; there are only 10,000 of them. One could simply "pre-compute" the SHA256 hashes of all 10,000 possible PINs and store them in a table. When you receive a hashed value, it's really simple -- and, more importantly, very fast -- to just look up the hash in the table and get back the original PIN (a.k.a. "inverting" it). It's kinda the same thing as "rainbow tables", if you recall those.

chrissnell 9y ago

Take every possible 10-digit U.S. phone number, for example, and perform a SHA-256 hash on each. Put those phone numbers and their hashes in a lookup table. Now, when a hashed phone number comes in from an anonymous user, look it up in that table and you now know the actual phone number.

abovemypaygrade 9y ago
I'm not an expert, so bear with me. Could this be thwarted by, say, having Signal add a random salt to every registering number and then advertising the hash of (number)+(random salt) as the final contact, invisible to the end user? Or would that involve Signal maintaining too much information on their users? If that's the case, I could see that being a problem.
- azdle 9y ago
  The problem with salting the hashes is that they then become useless for contact discovery. The only way I can think of to make it work would require sharing the salt with people trying to find you, but then at that point you just share a real user identifier and short-circuit the whole process happening here.
  - abovemypaygrade 9y ago
    The way I was initially picturing it would involve Signal keeping track of the salt they assigned to the contact number, with that specific salt maybe 'expiring' after a certain number of days (to get rid of salts where someone registered with Signal, didn't like it, and never registered again). After thinking about it some more, I realized that this would probably lead OWS to collecting big lists of registered users and their contact patterns, which goes against their policy of trying to retain as little data as possible.

jlgaddis 9y ago

Imagine you're storing a four-digit PIN (or even 10-digit phone numbers in the U.S.) and you decide to hash them with SHA256 because security. The key space -- the total number of all possible PINs -- is really small; there are only 10,000 of them. One could simply "pre-compute" the SHA256 hashes of all 10,000 possible PINs and store them in a table. When you receive a hashed value, it's really simple -- and, more importantly, very fast -- to just look up the hash in the table and get back the original PIN (a.k.a. "inverting" it). It's kinda the same thing as "rainbow tables", if you recall those.