Could completely public passphrase hashes ever be reliably secure?

Question

This is a hypothetical question and I only have a basic understanding of Cryptography.

If one were to follow the very best cryptographic practices for storing passphrases, could it ever be possible to publish literally all information (the usernames, the hashes, the salts, the algorithms used) and still be reasonably certain that no-one could crack them?

I'm assuming there would have to be a minimum-length constraint - like 12, or maybe 16 characters minimum - and obviously if someone were to choose "1111111111111111" then it would be easily guessable, but assuming people choose sensible passphrases, like "correct horse battery staple", could this work?

Answer 1

For any value $x$ chosen randomly in a set of size $N$, and hash function $h$, publishing $h(x)$ allows for an exhaustive search on $x$ with average cost $N/2$. This is unavoidable.

The problem with passwords is that, by virtue of fitting in the brain of a human, they tend to come for a set of potential passwords of relatively small size $N$. We try to cope with that by making $h$ a slow function, and using a new variant of $h$ every time (that's what salts are about). See this answer for details on password hashing.

Now that's just an average. Though most humans will have trouble remembering many fat random passwords, a normal human can remember a really random password with enough entropy to defeat exhaustive search. This will imply some effort, so a lot of users won't do it.

Entropy is the key word. An entropy of $n$ bits means a set of passwords of size $N = 2^n$ (that's a simplification: I am assuming that all potential passwords have an equal probability of being selected). In the case of the famous comic which describes the "correct horse" method, an entropy of 44 bits is claimed. This is mathematically correct (see that answer for an analysis). However, 44 bits are not a lot, certainly not enough to defeat exhaustive search. Cryptographers have long required at least 80 bits, as a rule of thumb for "unbreakable through brute force"; and the relentless progress in technology, as well as an aesthetic appeal for powers of two, now make "128 bits" to golden rule. It can be argued that 128 bits of entropy ought to resist brute force for quite some time.

Basically, the "correct horse" password generation method assumes a list of 2048 words, and four words are selected randomly and uniformly in that list. That is, there are four successive selections of one word in the list, and the selections are independent of each other (so the same word can be selected several times). Make that twelve words instead of merely four, and your password will be rock solid, even if you publish the hash of it.

(If you use slow hashing with a salt and enough iterations, these twelve words can be reduced to, say, nine or ten words.)

Answer 2

Short answer to the question is 'no', if the users of the service can choose their passwords.

Details

If PIN or password is used?

There is no way to force people to select passwords that are secure. When password is long, at least some (lazy) users will make passwords that are long, but contain little entropy.

When password or PIN gets longer people tend to get even lazier. There is a article on PIN code selection: http://www.datagenetics.com/blog/september32012/. According to it 11% users with 4 digit PIN use the most used PIN code, 1234. 23% of users with 5 digit PIN used 12345. Overall, it seemed that with few guesses it is more likely to guess 5 digit PIN than 4 digit PIN. Now back to the answer to your question: This phenomena applies to passwords as well; if passwords get longer, the passwords do not neccessarily get better. Never underestimate tricks users use to invent "easy to remember" password.

For passwords, there was a large study on 2007, concerning password quality: http://research.microsoft.com/pubs/74164/www2007.pdf. Around 20% of users had password strength of around 20 bits. Thus, if attacker picks passwords to attack in random, they could expect that they'll confront password of such a low entropy with just few trials.

If passphrase is used?

In the famous Randall's comic the passphrase is randomically selected from dictionary. Thus people cannot choose to remember passphrase they'd like, but they need to use some secure random number generator (like 5 dice) and password list to get their password. If the users did not do that, words like 'i', 'love', 'password', 'horse', 'staple', etc are overly represented, and entropy expected will be factually somewhat lower. Also note: If I did memorize correct horse staple and battery, it would still be problematic for me to remember the correct order for staple horse battery and correct. And if it was stable or staple. Thus, even long passphrases have their problems.

But let's assume user had such passphrase, 11 bits security per word, four words. If we also assume that the attacker is able to retrieve the password or passphrase hashes, then attackers are able to try brute-forcing passwords/passphrases with any amount of parallelization they can afford. If the password hashing algorithm is perfect, the attacker will have same cost for trying single password than the password would ordinarily take to authenticate. In weak password hashes, (like just single SHA without salt), the cost is much less per attempt due to rainbow tables. However, now we'll assume that the password hash is perfect and attacker does not attain significant benefit for the amount of operations he'll do, then he'll in average have to do 2^(entropy_in_bits-1) trials before hitting the password/phrase.

Let's also make assumption that there was only one server making authentications and it took 1 seconds to authenticate user. 1 second for authentication is quite long time (because during rush time there may be many users willing to authenticate simultaneously).

The capability of attacker depends on your adversary, but let's consider it was Google for sake of argument. Google represent adversary that has fairly large amount of computing power. Let's also assume that their servers take the same time to check a password guess. According to Randall Google has 1.8 - 2,2 million servers. If all those servers would try to hack password with strength 44 bits of entropy, the password would in average break in around 1,6 months. (I used 2^43 / 2629800 / 2100000 to estimate.)

This comes to: against very powerful adversary, entropy 2^44 is not enough if they got the password hashes, no matter bcrypt, PBKDF2, or scrypt was used. Also note that entropy 2^44 is larger than you can passphrases used in practice to have. I don't know of large public study of passphrases factually used in the web sites, basically because sites seem to prefer passwords.

---

How much is enough?

If the worst passphrase used 64 bits of entropy (20 bits more than 44 bits discussed above), then very slow hashing would theoretically allow you to expect security of 80 bits, which according to some experts is still currently enough for most purposes. For instance, NIST (see SP 800-131A) is still allowing 80-bit security for a few months. For security in longer term, 112 bit or 128 bit security would be needed. This would translate to 10-12 words, just like Thomas Pornin also pointed out in his answer. 10-12 words is just bit too long to be practical (my point on "laziness" in the beginning).

---

Notice my comment in the beginning: If users are given chance to invent their own passwords.

Now suppose the service did generate passwords for all the users, using properly seeded, properly implemented random number generation (i.e. the passwords were generated just like they were keys). If service has relatively long passwords for all users, it can be seen that public password hashes could be reliably secure (but... why publish the hashes and salts anyway in any case?).

Note: There is lot detail involved on how to implement this option. PBKDF or scrypt can be used to reduce password length a little etc. But passwords will be long, hard to remember and will likely be written down on e.g. yellow paper notes by some users.