5 ms·

> 2. "Also, Google wouldn’t be able to scan and index the text of your e-mails. That’s a problem if you need to search for old emails not stored on your own mac

> 2. "Also, Google wouldn’t be able to scan and index the text of your e-mails. That’s a problem if you need to search for old emails not stored on your own machine. It could be a real issue for Google’s business model as well, which involves scanning the text of emails in order to place contextual advertising." Caveat: I am no expert whatsoever in crypto/CS so understand this is almost certainly non-workable for some reason (which is what I'm trying to understand). Why couldn't Google hash every word in an email and store the list of hashes alongside the encrypted version. Then when you search for something, the search terms are hashed as well and the service searches for the hashed search terms amongst the lists of hashes. Edit: Thanks everyone!

level 12y ago
Because that's not really making it private. If you have each word hashed and a rainbow table full of hashes matched to words, it's very easily reversible. It doesn't really introduce any privacy. Not to mention the computational and storage cost.
- ithkuil 12y ago
  would a per user salt help with the rainbow table issue?
  - mike-cardwell 12y ago
    No. With a list of the users hashes and their salt, you could reverse it all in a matter of minutes or seconds on even a single low spec machine. It would offer nothing over just storing the plain text.
    - ithkuil 12y ago
      are you sure? I can think of weaknesses caused by statistical properties of a large corpus of hashed terms (all with the same salt) clustered together in documents which follow a natural language distribution, but matter of minutes or seconds? Why doesn't that simplicity apply for salted hashed passwords?
      - DerpDerpDerp 12y ago
        There's only around a million (or a couple million if you're generous with conjugations, lulzspeak, etc) English words. If you figure passwords understand 75 characters, then one million passwords is around 3.2 randomly chosen characters. If you step up to 4 randomly chosen characters, you'd cover 31 million entries, and hence have about the same strength as reversing a hash of 31 million different words. A 4 character password is woefully weak by modern standards.
        ithkuil 12y ago
        the client can generate terms by combining a secret key with the term while hashing it (keyed-hash). See one particular approach in: http://people.csail.mit.edu/akiezun/encrypted-search-report.pdf http://people.csail.mit.edu/akiezun/encrypted-search-report....
      - opendais 12y ago
        In theory, passwords are random combinations of words and/or characters so you cannot 'guess' larger than a character at a time. This scales very quickly to the number of combinations. http://www.oxforddictionaries.com/us/words/the-oec-facts-about-the-language http://www.oxforddictionaries.com/us/words/the-oec-facts-abo... You can guess 90% of the words in the OEC with only 7,000 words in your rainbow table. I suspect that is a pretty fair representation of e-mails text. Even if it is the 1,000,000 number... [As of 2011, commercial products are available that claim the ability to test up to 2,800,000,000 passwords per second on a standard desktop computer using a high-end graphics processor.] http://en.wikipedia.org/wiki/Password_strength#Password_guess_validation http://en.wikipedia.org/wiki/Password_strength#Password_gues... So ya. If it is a per-word hash, there is no real security value if you have the salt.
      - jerf 12y ago
        "Why doesn't that simplicity apply for salted hashed passwords?" It does. Don't store salted hashes for passwords.
        shkkmo 12y ago
    - 7952 12y ago
      So store the salt on the client, and reindex if the salt is lost?
mike-cardwell 12y ago
Hashing only helps when the number of possible inputs is very very large. When the number of possible inputs is "the number of words in the dictionary", or "every IPv4 address" or "every phone number" etc, then it would take a modern home computer a few seconds to generate a raintable which would make the hashes instantly reversible.
- dublinben 12y ago
  >raintable I knew what you meant, but if anyone else was confused, the correct term is "rainbow table." https://en.wikipedia.org/wiki/Rainbow_table https://en.wikipedia.org/wiki/Rainbow_table
brown9-2 12y ago
In order to do this, Google would need access to the plaintext of the email message, which defeats half of the purpose of the supposed encryption initiative.
smsm42 12y ago
This requires what is called homomorphic encryption: https://en.wikipedia.org/wiki/Homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption There seems to be active research done in this field, e.g.: http://research.microsoft.com/en-us/people/klauter/cryptostoragerlcps.pdf http://research.microsoft.com/en-us/people/klauter/cryptosto... http://research.microsoft.com/en-us/um/people/senyk/slides/encryptedsearch-full.pdf http://research.microsoft.com/en-us/um/people/senyk/slides/e... I haven't read all those papers so I'm not sure how close it to working, but from what I have read I'm not sure if it even is practical for searching your own mail. For google indexing everybody's email, that would be contradictory as indexing an email basically reveals its content to the party that is using the index to look up.
- Spearchucker 12y ago
  Not sure such an approach is needed. The same key used to encrypt email could be used to encrypt a search catalog. The user decrypts the entire catalog when a search needs to be done. The risk of the catalog getting too big could be mitigated by making the indexer constrain the catalog to emails from the last 30 days or so, and making the complete catalog available offline. It can be tuned by letting users add important older emails to the catalog, and so on. It's an approach I've used with a store/forward database and worked well for me with that.
read 12y ago
> this is almost certainly non-workable for some reason Why is it necessary to have the ability to search past emails? Could there be any value in not looking back? (It's ok to laugh at this.)
arghnoname 12y ago
There is a lot of research in this area. Here is a paper on how to search on encrypted data: http://www.cs.berkeley.edu/~dawnsong/papers/se.pdf http://www.cs.berkeley.edu/~dawnsong/papers/se.pdf One thing you need to be wary of is plaintext attacks. Even if you use a salt and a difficult has but I send you an e-mail and know the contents and can obtain the ciphertext or its digests, you are vulnerable. There are ways past this, of course, but it is one example of a valid attack. The pdf I referenced has what seems to be a pretty workable approach to me and lets you do hidden searches, boolean searches, phrases, proximity queries, etc.

level 12y ago

Because that's not really making it private. If you have each word hashed and a rainbow table full of hashes matched to words, it's very easily reversible. It doesn't really introduce any privacy. Not to mention the computational and storage cost.

ithkuil 12y ago
would a per user salt help with the rainbow table issue?
- mike-cardwell 12y ago
  No. With a list of the users hashes and their salt, you could reverse it all in a matter of minutes or seconds on even a single low spec machine. It would offer nothing over just storing the plain text.
  - ithkuil 12y ago
    are you sure? I can think of weaknesses caused by statistical properties of a large corpus of hashed terms (all with the same salt) clustered together in documents which follow a natural language distribution, but matter of minutes or seconds? Why doesn't that simplicity apply for salted hashed passwords?
    - DerpDerpDerp 12y ago
      There's only around a million (or a couple million if you're generous with conjugations, lulzspeak, etc) English words. If you figure passwords understand 75 characters, then one million passwords is around 3.2 randomly chosen characters. If you step up to 4 randomly chosen characters, you'd cover 31 million entries, and hence have about the same strength as reversing a hash of 31 million different words. A 4 character password is woefully weak by modern standards.
      - ithkuil 12y ago
        the client can generate terms by combining a secret key with the term while hashing it (keyed-hash). See one particular approach in: http://people.csail.mit.edu/akiezun/encrypted-search-report.pdf http://people.csail.mit.edu/akiezun/encrypted-search-report....
    - opendais 12y ago
      In theory, passwords are random combinations of words and/or characters so you cannot 'guess' larger than a character at a time. This scales very quickly to the number of combinations. http://www.oxforddictionaries.com/us/words/the-oec-facts-about-the-language http://www.oxforddictionaries.com/us/words/the-oec-facts-abo... You can guess 90% of the words in the OEC with only 7,000 words in your rainbow table. I suspect that is a pretty fair representation of e-mails text. Even if it is the 1,000,000 number... [As of 2011, commercial products are available that claim the ability to test up to 2,800,000,000 passwords per second on a standard desktop computer using a high-end graphics processor.] http://en.wikipedia.org/wiki/Password_strength#Password_guess_validation http://en.wikipedia.org/wiki/Password_strength#Password_gues... So ya. If it is a per-word hash, there is no real security value if you have the salt.
    - jerf 12y ago
      "Why doesn't that simplicity apply for salted hashed passwords?" It does. Don't store salted hashes for passwords.
      - shkkmo 12y ago
  - 7952 12y ago
    So store the salt on the client, and reindex if the salt is lost?

mike-cardwell 12y ago

Hashing only helps when the number of possible inputs is very very large. When the number of possible inputs is "the number of words in the dictionary", or "every IPv4 address" or "every phone number" etc, then it would take a modern home computer a few seconds to generate a raintable which would make the hashes instantly reversible.

dublinben 12y ago
>raintable I knew what you meant, but if anyone else was confused, the correct term is "rainbow table." https://en.wikipedia.org/wiki/Rainbow_table https://en.wikipedia.org/wiki/Rainbow_table

brown9-2 12y ago

In order to do this, Google would need access to the plaintext of the email message, which defeats half of the purpose of the supposed encryption initiative.

smsm42 12y ago

This requires what is called homomorphic encryption: https://en.wikipedia.org/wiki/Homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption There seems to be active research done in this field, e.g.: http://research.microsoft.com/en-us/people/klauter/cryptostoragerlcps.pdf http://research.microsoft.com/en-us/people/klauter/cryptosto... http://research.microsoft.com/en-us/um/people/senyk/slides/encryptedsearch-full.pdf http://research.microsoft.com/en-us/um/people/senyk/slides/e... I haven't read all those papers so I'm not sure how close it to working, but from what I have read I'm not sure if it even is practical for searching your own mail. For google indexing everybody's email, that would be contradictory as indexing an email basically reveals its content to the party that is using the index to look up.

Spearchucker 12y ago
Not sure such an approach is needed. The same key used to encrypt email could be used to encrypt a search catalog. The user decrypts the entire catalog when a search needs to be done. The risk of the catalog getting too big could be mitigated by making the indexer constrain the catalog to emails from the last 30 days or so, and making the complete catalog available offline. It can be tuned by letting users add important older emails to the catalog, and so on. It's an approach I've used with a store/forward database and worked well for me with that.

read 12y ago

> this is almost certainly non-workable for some reason Why is it necessary to have the ability to search past emails? Could there be any value in not looking back? (It's ok to laugh at this.)

arghnoname 12y ago

There is a lot of research in this area. Here is a paper on how to search on encrypted data: http://www.cs.berkeley.edu/~dawnsong/papers/se.pdf http://www.cs.berkeley.edu/~dawnsong/papers/se.pdf One thing you need to be wary of is plaintext attacks. Even if you use a salt and a difficult has but I send you an e-mail and know the contents and can obtain the ciphertext or its digests, you are vulnerable. There are ways past this, of course, but it is one example of a valid attack. The pdf I referenced has what seems to be a pretty workable approach to me and lets you do hidden searches, boolean searches, phrases, proximity queries, etc.