4 ms·

> a hash of the message text This allows to restore the message if it is short. Let's say a typical user knows 2×10^4 words and the message contains 3 words. I

> a hash of the message text This allows to restore the message if it is short. Let's say a typical user knows 2×10^4 words and the message contains 3 words. If each word can be chosen with equal probability independently of others then one can guess the message content after an average of 4×10^12 attempts. And of course, one can check all the hashes at the same time. So the hash function is effectively reversible for short pieces of data, like phone numbers, DOB, card numbers, emails and so on.

yunohn 5y ago
Their investigation clearly shows that it’s a truncated SHA256 hash of the entire message text + a timestamp. I’m very sure that your method does NOT work. How are you assuming a known dictionary and a known word count? And for the other examples, you’re somehow assuming a fully precalculated rainbow table of all possible such PII. Seriously…? > sha256HashMsg value is a hash of the time, in hours since 1st Jan 1970, that the message was sent and of the message content i.e the message text, truncated to 128 bits.
- remus 5y ago
  > How are you assuming a known dictionary and a known word count? And for the other examples, you’re somehow assuming a fully precalculated rainbow table of all possible such PII. Seriously…? Obviously deciphering all messages is not feasible but I think GPs point was that you could put together a table that would get you some decent proportion of messages. For example, if you assume an alphabet of [a-zA-Z0-9 ] then you'd only need to calculate ~63.5 billion hashes to get all messages up to 6 chars. Similarly you could use a dictionary to put together tables for short sentences.
  - codedokode 5y ago
    Messages are usually composed from words, not from random letters, so you don't need to bruteforce all letter combinations. Also, some messages use a template, for example, a message from an online store like "Your order number XXXXX is ready for pickup" or a message from a bank saying "Your PIN code is XXXX". In this case, all you need to guess is a number.
  - yunohn 5y ago
    Could you link to some PoC hacks that prove feasibility? I’m not saying it’s theoretically impossible - mathematically it should be. I’m simply saying that the message content space is massive, and hence practically infeasible. Again, all of this is predicated on Google hashing messages client-side and then, secretly reverse-matching them server-side for very simplistic 1-3 word messages?
- codedokode 5y ago
  > How are you assuming a known dictionary If the user is from country A, there is high probability that they use language of country A. Regarding word count, you don't need to know it. First, try to calculate hashes of all one-word messages. Then, all hashes of two-word messages. And so on. Google also can collect statistics on which words and word combinations are used more often (for example, from gmail messages) and use this to accelerate bruteforce. > And for the other examples, you’re somehow assuming a fully precalculated rainbow table of all possible such PII. Seriously…? Let's take phone numbers as an example. Russian phone number starts with +7 which is followed by 10 random digits. Therefore, there can be maximum of 10^10 = 10 billions numbers. This answer [1] states that a GPU can calculate up to 10 billion MD5 or SHA1 hashes per second. Therefore, recovering a phone number from a hash would take approximately one second on a typical consumer hardware. Note that one could build a custom CPU optimized for calculating hashes and get higher throughput. Regarding credit card numbers, there is larger search space: you have to guess 15 digits (16th digit is a checksum). But it is not like there are 10^15 credit cards in the world. This search space can be significantly reduced, for example, by filtering by BIN (first 6 digits that identify the issuer bank). This is why hashing short identifiers (like phone number or card number) doesn't make much sense and such hash can be easily reversed. [1] https://security.stackexchange.com/a/38135 https://security.stackexchange.com/a/38135
  - yunohn 5y ago
    Thanks for the detail, though to be clear, I’m not doubting the mathematical theoretical possibility of an SHA256 rainbow table. I’m saying that even the example scenario you describe is a massive solution space in itself. And then to extrapolate this for all sorts of PII and combinations of words/letters to make this attack worthwhile, is quite a stretch. Again, a slight change in order of words or characters (even something like an extra space) will break your rainbow table lookup. People message in all sorts of weird ways, with abbreviations, typos, slang, or even mix languages. Even suggesting that “one could just” pre-calculate every 1,2,3,etc combination of words is hilarious. I categorically do not believe this attack is even remotely feasible.
    - bscphil 5y ago
Gasp0de 5y ago
Doesn't it say "a truncated hash"?
- charcircuit 5y ago
  Specifically "sha256HashMsg value is a hash of the time, in hours since 1st Jan 1970, that the message was sent and of the message content i.e the message text, truncated to 128 bits."
- codedokode 5y ago
  Yes, it is 128-bit hash. 128 bits are enough to recover a message made of 3-4 words. Some messages are build by template, for example, a message from a bank saying "Your PIN code is XXXX". In this case, it is possible to recover the PIN code using 128-bit hash as the number of possible PIN codes is less than 2^128.
  - RL_Quine 5y ago
    Probably given the sender is always the same for those, the work to recover the text is probably literally just the key space of the code. Like, 1M hashes in a lookup table for a normal bank 2FA code. Recoverable in microseconds.
  - yunohn 5y ago
    It’s a 256bit hash of message+timestamp truncated to 128bit. The attack you’re describing is literally impossible.
    - codedokode 5y ago
      I don't see how hash truncation prevents the attack. Regarding timestamp, precise timestamp is sent in clear text in another event field (currentTime_ms) so its presence doesn't prevent message content recovery.
      - yunohn 5y ago
        > its presence doesn't prevent message content recovery The TS is the “salt” & hence defeats rainbow tables, unless somehow it’s feasible to infinitely store them for every combination of message & time for the past/future. > how hash truncation prevents the attack It literally deletes half the information you have for the attack. You CANNOT /perfectly/ compute the original text for a truncated hash, you’ll have innumerable clashes. So yes, any attack is impossible/infeasible.
m463 5y ago
I wonder how many short messages are easily recognizable ("on my way", "eta?", "love you", "lol", ...)

yunohn 5y ago

Their investigation clearly shows that it’s a truncated SHA256 hash of the entire message text + a timestamp. I’m very sure that your method does NOT work. How are you assuming a known dictionary and a known word count? And for the other examples, you’re somehow assuming a fully precalculated rainbow table of all possible such PII. Seriously…? > sha256HashMsg value is a hash of the time, in hours since 1st Jan 1970, that the message was sent and of the message content i.e the message text, truncated to 128 bits.

remus 5y ago
> How are you assuming a known dictionary and a known word count? And for the other examples, you’re somehow assuming a fully precalculated rainbow table of all possible such PII. Seriously…? Obviously deciphering all messages is not feasible but I think GPs point was that you could put together a table that would get you some decent proportion of messages. For example, if you assume an alphabet of [a-zA-Z0-9 ] then you'd only need to calculate ~63.5 billion hashes to get all messages up to 6 chars. Similarly you could use a dictionary to put together tables for short sentences.
- codedokode 5y ago
  Messages are usually composed from words, not from random letters, so you don't need to bruteforce all letter combinations. Also, some messages use a template, for example, a message from an online store like "Your order number XXXXX is ready for pickup" or a message from a bank saying "Your PIN code is XXXX". In this case, all you need to guess is a number.
- yunohn 5y ago
  Could you link to some PoC hacks that prove feasibility? I’m not saying it’s theoretically impossible - mathematically it should be. I’m simply saying that the message content space is massive, and hence practically infeasible. Again, all of this is predicated on Google hashing messages client-side and then, secretly reverse-matching them server-side for very simplistic 1-3 word messages?
codedokode 5y ago
> How are you assuming a known dictionary If the user is from country A, there is high probability that they use language of country A. Regarding word count, you don't need to know it. First, try to calculate hashes of all one-word messages. Then, all hashes of two-word messages. And so on. Google also can collect statistics on which words and word combinations are used more often (for example, from gmail messages) and use this to accelerate bruteforce. > And for the other examples, you’re somehow assuming a fully precalculated rainbow table of all possible such PII. Seriously…? Let's take phone numbers as an example. Russian phone number starts with +7 which is followed by 10 random digits. Therefore, there can be maximum of 10^10 = 10 billions numbers. This answer [1] states that a GPU can calculate up to 10 billion MD5 or SHA1 hashes per second. Therefore, recovering a phone number from a hash would take approximately one second on a typical consumer hardware. Note that one could build a custom CPU optimized for calculating hashes and get higher throughput. Regarding credit card numbers, there is larger search space: you have to guess 15 digits (16th digit is a checksum). But it is not like there are 10^15 credit cards in the world. This search space can be significantly reduced, for example, by filtering by BIN (first 6 digits that identify the issuer bank). This is why hashing short identifiers (like phone number or card number) doesn't make much sense and such hash can be easily reversed. [1] https://security.stackexchange.com/a/38135 https://security.stackexchange.com/a/38135
- yunohn 5y ago
  Thanks for the detail, though to be clear, I’m not doubting the mathematical theoretical possibility of an SHA256 rainbow table. I’m saying that even the example scenario you describe is a massive solution space in itself. And then to extrapolate this for all sorts of PII and combinations of words/letters to make this attack worthwhile, is quite a stretch. Again, a slight change in order of words or characters (even something like an extra space) will break your rainbow table lookup. People message in all sorts of weird ways, with abbreviations, typos, slang, or even mix languages. Even suggesting that “one could just” pre-calculate every 1,2,3,etc combination of words is hilarious. I categorically do not believe this attack is even remotely feasible.
  - bscphil 5y ago

Gasp0de 5y ago

Doesn't it say "a truncated hash"?

charcircuit 5y ago
Specifically "sha256HashMsg value is a hash of the time, in hours since 1st Jan 1970, that the message was sent and of the message content i.e the message text, truncated to 128 bits."
codedokode 5y ago
Yes, it is 128-bit hash. 128 bits are enough to recover a message made of 3-4 words. Some messages are build by template, for example, a message from a bank saying "Your PIN code is XXXX". In this case, it is possible to recover the PIN code using 128-bit hash as the number of possible PIN codes is less than 2^128.
- RL_Quine 5y ago
  Probably given the sender is always the same for those, the work to recover the text is probably literally just the key space of the code. Like, 1M hashes in a lookup table for a normal bank 2FA code. Recoverable in microseconds.
- yunohn 5y ago
  It’s a 256bit hash of message+timestamp truncated to 128bit. The attack you’re describing is literally impossible.
  - codedokode 5y ago
    I don't see how hash truncation prevents the attack. Regarding timestamp, precise timestamp is sent in clear text in another event field (currentTime_ms) so its presence doesn't prevent message content recovery.
    - yunohn 5y ago
      > its presence doesn't prevent message content recovery The TS is the “salt” & hence defeats rainbow tables, unless somehow it’s feasible to infinitely store them for every combination of message & time for the past/future. > how hash truncation prevents the attack It literally deletes half the information you have for the attack. You CANNOT /perfectly/ compute the original text for a truncated hash, you’ll have innumerable clashes. So yes, any attack is impossible/infeasible.

m463 5y ago

I wonder how many short messages are easily recognizable ("on my way", "eta?", "love you", "lol", ...)