Regarding timestamp, precise timestamp is sent in clear text in another event field (currentTime_ms) so 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.
Also, storing the hash means that messages are irrefutable.
But do you disagree with my claims? Do you have any sources to backup their invalidity?
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.
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.
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.
Easily available hardware can create 10 billion SHA-1 hashes per second. So to brute force every hash for every combination of one word message and timestamp, you need ... one hundredth of one second. No rainbow tables needed here. Just brute force it. For each hash, you just check every message hash stored on your server to find matches. If you find a match, you've uncovered the probable message text.
And so on for 2, 3 word combinations. Let's take 3 word combinations, assuming all three words are in the 10000 most commonly used English words. There are 10000^3 possible combinations of such words. Once again, the timestamp adds another 10000 possibilities (for the last year). How long does it take to brute force all 3 word combinations? One million seconds - less than two weeks. This is for a SINGLE person working on this with a SINGLE GPU. Not only will a serious attacker have better hardware, but context clues can help limit the possible options so that much longer combinations of words will be possible (if they are common combinations).
Sure, there will be slight punctuation or capitalization differences in some cases and that adds entropy, but not by enough to bother taking into consideration in terms of security.
I guess we're also assuming in all this that Google is not tagging each message with the time received on the server. Given that they already have that information, they might be able to recover the message content without needing the extra hashes for the timestamp.
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.
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?
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.
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.