Hacker News Reader

Comment by level | Hacker News Reader

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.

View on HN

would a per user salt help with the rainbow table issue?

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.

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?

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.

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....

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-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_gues...

So ya. If it is a per-word hash, there is no real security value if you have the salt.

"Why doesn't that simplicity apply for salted hashed passwords?"

It does. Don't store salted hashes for passwords.

Huh? What do you store instead?

My understanding of why this doesn't work for passwords is because the number of possible passwords (the size of the rainbow table needed for each salt) is much larger than the number of words in the english language.

Look up "bcrypt" and "scrypt". Using salted hashes for storing passwords is still common, but only for legacy reasons. It's considered insecure nowadays. Machines have got very very good at hashing over the last few years.

bcrypt is still a hash, it even incorporates a salt. Of course sha256 is too fast to compute, bcrypt fixes that.

I feel that this whole thread is based on cargo-culting. There are plenty of or (interesting) blog posts with misleading titles like "you shouldn't use hashes for passwords", which are correctly explaining why the cryptographic hash functions are not well suited to hashing passwords.

However, the solution is to use another method to hash the password. But it's still a hash.

A key derivation function used to process a password, produces a hash if you intend to use it as a hash, i.e. to compare it with another hash. If you use it to encrypt something then that would be a key.

Even the scrypt paper (http://www.tarsnap.com/scrypt/scrypt.pdf) says:

"Password-based key derivation functions are used for two primary purposes: First, to hash passwords so that an attacker who gains access to a password ﬁle does not immediately possess the [..]" (emphasis mine)

We say "don't just store salted hashes" because when people hear that, they think one run of SHA256 (or MD5 or whoknows) with a salt. You shouldn't do that. You should use a prepared method, because it's easy and (much more likely to be) correct. If you want to bodge together your own solution based on some large iterations of SHA256, you can, but it will take you much longer than just dropping in (b/s)crypt, and even longer if you have to match the (b/s)crypt feature set it provides out of the box. And you still have to face the fact that your SHA256 solution may not be as secure as you think because it's still a fast hash function, and an adversary may be able to process it much faster than you expect, whereas the (b/s)crypt have considered that in their design.

Pretty much by definition, advice provided to low-crypto-knowledge people can not depend on high levels of crypto knowledge. So, yes, pedantically you can point out that (b/s)crypt still produces a hash by the technical definition of hash. But you only muddy the waters for the low-knowledge people by doing so, and you probably shouldn't hold your breath waiting for plaudits from the high-knowledge people for doing so.

Since the original topic was how to build an server side index that can let users find relevant documents in an encrypted corpus without revealing the corpus to said server (e.g. [1]), I think that whoever diverts the thread into a discussion about the right function to use with passwords is the one being pedantic and missing the point.

Is it possible to build a index for an encrypted corpus that preserves the user privacy even in case the server is taken over?

I don't know ([2], [3]?). But I certainly know that the main weakness is not that it's impossible to hash terms in such a way that a weak machine cannot reverse significant portions of the index in minutes/days.

Seeing the word "hash" in this context clearly doesn't specify a particular hash function. Saying that using a salt fixes the issue with rainbow tables too doesn't specify whether we are talking about naive md5/sha salted hash or a KDF. These details were irrelevant to the discussion.

1. http://people.csail.mit.edu/akiezun/encrypted-search-report.... 2. http://rd.springer.com/chapter/10.1007%2F11496137_30 3. http://www.cs.ucla.edu/~rafail/PUBLIC/SSE.ppt‎

Thanks for the info, I will take a look at those.

There are only probably a million or so frequently-appearing terms in English-language email messages (including the most common proper nouns, though of course not all of the long tail). Computing a million hashes with a custom salt is still trivial for modern computers.

The plain text is dictionary words, given that the hash and the salt is known it will be really quick to hash every dictionary word for a single user. There are 99171 words in /usr/share/dict/words and off the shelf hardware can do 1300 million SHA1 hashes per second [0]

[0] http://security.stackexchange.com/questions/8607/how-quickly...

So store the salt on the client, and reindex if the salt is lost?

Reply on news.ycombinator.com