# Could completely public passphrase hashes ever be reliably secure?

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?

-
I think I saw some blog somewhere that sufficiently debunked the story that that kind of passphrase would be likely to be safe enough (well, that one is certainly not safe, but one that follows the same pattern) –  owlstead Sep 23 '13 at 23:00
@owlstead If you can dig it out I'd be interested to read it. All I found when Googling was this SE question and the consensus there seems to be that Randall's reasoning is largely accurate. –  Robin Winslow Sep 23 '13 at 23:13
I'll admit I'm not sure I fully understand your question. Is it reasonably certain that no-one could crack them? Well, that's sort of what all of the fuss about inefficient KDFs is supposed to ensure ... that is, the whole point of cryptography in password storage is to make sure that publicly available hashed passwords (after, say, a DB leak) aren't able to be easily cracked. The answer to your question is yes, then, by definition, since the 'very best cryptographic practices' seek to protect (reasonable) passwords from being cracked. Is that what you're asking? –  Reid Sep 24 '13 at 0:12
@Reid Yes I see your point - it's "what all the fuss is about" so it should be possible. So what I'm really asking is - if I wanted to have a 100% open app - all the source code and all the data publicly is available (not just through leaks - literally anyone can just download it) - could I still offer reliable authentication. I thought there might be a difference - in terms of the types of possible attacks - between a leaked set of password hashes and a publicly available one. –  Robin Winslow Sep 24 '13 at 8:49
@Reid I suppose my question should have been something like "what problems can you see with authentication within an application with 100% open and public source code and database data" –  Robin Winslow Sep 24 '13 at 8:52

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

-
Are you saying that for reliable security, human readable passwords must be at least ten words long? Holy crap we're all doomed. So in this day and age, with the fastest GPU-based cracking techniques, how long would it take to brute-force a password with 44 bits of entropy encrypted with a slow hashing algorithm and a salt? –  Robin Winslow Sep 24 '13 at 11:09
Slow hashing is about making the hash function as slow as possible for everybody. The honest server uses a PC (a server). The attacker may use several machines and buy specialized hardware. It then depends on the function; scrypt, for instance, tries to be memory-hard, which means that the best platform to compute scrypt is indeed a PC, not a GPU. If you crank the iteration count up, so that each password hashing takes 1 second on your server, and the attacker musters 200 times more CPU power than you, then he will break a 44-bit password in $2^{43}/200$ seconds on average (1400 years) –  Thomas Pornin Sep 24 '13 at 11:15
Right, so if I were to use a slow hash that takes 1 second on my server, surely a 44-bit password would be perfectly secure enough even with a public hash. –  Robin Winslow Sep 24 '13 at 11:18
@RobinWinslow You only start to get problems when lots of users at your server want to login at one time, like calculating the hashes once for each of $350000 \approx 2^{18}$ users will take about 4 CPU-days (and corresponding RAM resources if using scrypt). –  Paŭlo Ebermann Sep 24 '13 at 20:33
Okay so it's not so scalable at a 1-second algorithm. But presumably we could find a fairly happy medium. Since 44-bit at 1-second = 1400 years, so we clearly have some leeway. If I were to require 12-character passwords, how much entropy could I expect, on average? And then how fast could I make my algorithm if I wanted to keep expected brute force-able time above 10 years? –  Robin Winslow Sep 27 '13 at 8:20

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.

-
You employ a study about PIN numbers to make an argument about plain language passwords. You might not be able to remember the correct order for "correct horse battery staple" but then you didn't come up with it. If you were to pick a four-word password I think you'd probably pick something you can remember. I'd be very interested to see a study on the average entropy of user-chosen 10-character passwords, for example. I'm sure lots of people would use common phrases, like "I love you" = lower entropy. But that's still not terrible. –  Robin Winslow Sep 27 '13 at 8:11
To clarify - I don't think it's valid to apply your PIN study to passphrases because numbers are hard for humans and easy for computers, whereas words are easy for humans and hard for computers. –  Robin Winslow Sep 27 '13 at 8:29
Note the question by OP asked "public password hashes", not passphrase hashes. So the most of the answer applies to password (e.g. "D3aTh,R0W"). But, for some parts the idea applies to passphrases ("correct horse battery staple") as well. xkcd says that the passphrase has entropy 2^44. This amount of entropy means that if the password hash was public, it would be most probably broken in reasonable amount of time. This is because if you count the amount of entropy (2^44) p –  user4982 Sep 27 '13 at 13:57
I was saying if you count 2^(44+effect_of_iteration_in_scrypt_or_pbkdf), it is most likely still way less that recommendations for typical symmetric key. Robin: Have you read NIST SP 800-63, Appendix A? It is good reference for estimating amount of entropy in a password. (However, that document seems bit optimistic. It is so common to have password that is much worse; it looks good but actually contains a common substring). –  user4982 Sep 27 '13 at 14:03
Sorry I've replaced "password" with "passphrase" in the original question to satisfy your pedantry. See ThomasPornin's answer for a discussion of the security of a 44-bit passphrase. –  Robin Winslow Sep 27 '13 at 15:04