How to hash long passwords (>72 characters) with blowfish

Question

The last week I read a lot articles about password hashing and Blowfish seems to be (one of) the best hashing algorithm right now - but that's not the topic of this question!

The 72 character limit

Blowfish only consider the first 72 characters in the entered password:

<?php
$password = "Wow. This is a super secret and super, super long password. Let's add some special ch4r4ct3rs a#d everything is fine :)";
$hash = password_hash($password, PASSWORD_BCRYPT);
var_dump($password);

$input = substr($password, 0, 72);
var_dump($input);

var_dump(password_verify($input, $hash));
?>

The output is:

string(119) "Wow. This is a super secret and super, super long password. Let's add some special ch4r4ct3rs a#d everything is fine :)"
string(72) "Wow. This is a super secret and super, super long password. Let's add so"
bool(true)

As you can see only the first 72 characters matter. Twitter is using blowfish aka bcrypt to store their passwords (https://shouldichangemypassword.com/twitter-hacked.php) and guess what: change your twitter password to a long password with more than 72 characters and you can login to your account by entering only the first 72 characters.

Blowfish and Pepper

There are a lot different opinions about "peppering" passwords. Some people say it's unnecessary, because you have to assume that the secret pepper-string is also known/published so it doesn't enhance the hash. I have a separate database server so it's quite possible that only the database is leaked and not the constant pepper.

In this case (pepper not leaked) you make an attack based on a dictionary more difficult (correct me if this isn't right). If your pepper-string is also leaked: not that bad - you still have the salt and it's as good protected as a hash without pepper.

So I think peppering the password is at least no bad choice.

Suggestion

My suggestion to get a Blowfish hash for a password with more than 72 characters (and pepper) is:

<?php
$pepper = "foIwUVmkKGrGucNJMOkxkvcQ79iPNzP5OKlbIdGPCMTjJcDYnR";

// Generate Hash
$password = "Wow. This is a super secret and super, super long password. Let's add some special ch4r4ct3rs a#d everything is fine :)";
$password_peppered = hash_hmac('sha256', $password, $pepper);
$hash = password_hash($password_peppered, PASSWORD_BCRYPT);

// Check
$input = substr($password, 0, 72);
$input_peppered = hash_hmac('sha256', $input, $pepper);

var_dump(password_verify($input_peppered, $hash));
?>

This is based on this question: password_verify return false.

The Question

What is the safer way? Getting an SHA-256 hash first (which returns 64 characters) or consider only the first 72 characters of the password?

Pros

• The user can't login by entering just the first 72 characters
• You can add the pepper without exceeding the character-limit
• The output of hash_hmac would probably have more entropy than the password itself
• The password is hashed by two different functions

Cons

• Only 64 characters are used to build the blowfish hash

Edit 1: This question adresses only the PHP integration of blowfish/bcrypt. Thank's for the comments!

Solution 1

The problem here is basically a problem of entropy. So let's start looking there:

Entropy Per Character

The number of bits of entropy per byte are:

• Hex Characters
  • Bits: 4
  • Values: 16
  • Entropy In 72 Chars: 288 bits
• Alpha-Numeric
  • Bits: 6
  • Values: 62
  • Entropy In 72 Chars: 432 bits
• "Common" Symbols
  • Bits: 6.5
  • Values: 94
  • Entropy In 72 Chars: 468 bits
• Full Bytes
  • Bits: 8
  • Values: 255
  • Entropy In 72 Chars: 576 bits

So, how we act depends on what type of characters we expect.

The First Problem

The first problem with your code, is that your "pepper" hash step is outputting hex characters (since the fourth parameter to hash_hmac() is not set).

Therefore, by hashing your pepper in, you're effectively cutting the maximum entropy available to the password by a factor of 2 (from 576 to 288 possible bits).

The Second Problem

However, sha256 only provides 256 bits of entropy in the first place. So you're effectively cutting a possible 576 bits down to 256 bits. Your hash step * immediately*, by very definition loses at least 50% of the possible entropy in the password.

You could partially solve this by switching to SHA512, where you'd only reduce the available entropy by about 12%. But that's still a not-insignificant difference. That 12% reduces the number of permutations by a factor of 1.8e19. That's a big number... And that's the factor it reduces it by...

The Underlying Issue

The underlying issue is that there are three types of passwords over 72 characters. The impact that this style system has on them will be very different:

Note: from here on out I'm assuming we're comparing to a pepper system which uses SHA512 with raw output (not hex).

• High entropy random passwords

  These are your users using password generators which generate what amount to large keys for passwords. They are random (generated, not human chosen), and have high entropy per character. These types are using high-bytes (characters > 127) and some control characters.

  For this group, your hashing function will significantly reduce their available entropy into bcrypt.

  Let me say that again. For users who are using high entropy, long passwords, your solution significantly reduces the strength of their password by a measurable amount. (62 bits of entropy lost for a 72 character password, and more for longer passwords)

• Medium entropy random passwords

  This group is using passwords containing common symbols, but no high bytes or control characters. These are your typable passwords.

  For this group, you are going to slightly unlock more entropy (not create it, but allow more entropy to fit into the bcrypt password). When I say slightly, I mean slightly. The break-even occurs when you max out the 512 bits that SHA512 has. Therefore, the peak is at 78 characters.

  Let me say that again. For this class of passwords, you can only store an additional 6 characters before you run out of entropy.

• Low entropy non-random passwords

  This is the group who are using alpha-numeric characters that are probably not randomly generated. Something like a bible quote or such. These phrases have approximately 2.3 bits of entropy per character.

  For this group, you can significantly unlock more entropy (not create it, but allow more to fit into the bcrypt password input) by hashing. The breakeven is around 223 characters before you run out of entropy.

  Let's say that again. For this class of passwords, pre-hashing definitely increases security significantly.

Back To The Real World

These kinds of entropy calculations don't really matter much in the real world. What matters is guessing entropy. That's what directly effects what attackers can do. That's what you want to maximize.

While there's little research that's gone into guessing entropy, there are some points that I'd like to point out.

The chances of randomly guessing 72 correct characters in a row are extremely low. You're more likely to win the Powerball lottery 21 times, than to have this collision... That's how big of a number we're talking about.

But we may not stumble on it statistically. In the case of phrases the chance of the first 72 characters being the same is a whole lot higher than for a random password. But it's still trivially low (you're more likely to win the Powerball lottery 5 times, based on 2.3 bits per character).

Practically

Practically, it doesn't really matter. The chances of someone guessing the first 72 characters right, where the latter ones make a significant difference are so low that it's not worth worrying about. Why?

Well, let's say you're taking a phrase. If the person can get the first 72 characters right, they are either really lucky (not likely), or it's a common phrase. If it's a common phrase, the only variable is how long to make it.

Let's take an example. Let's take a quote from the bible (just because it's a common source of long text, not for any other reason):

You shall not covet your neighbor's house. You shall not covet your neighbor's wife, or his manservant or maidservant, his ox or donkey, or anything that belongs to your neighbor.

That's 180 characters. The 73rd character is the g in the second neighbor's. If you guessed that much, you're likely not stopping at nei, but continuing with the rest of the verse (since that's how the password is likely to be used). Therefore, your "hash" didn't add much.

BTW: I am ABSOLUTELY NOT advocating using a bible quote. In fact, the exact opposite.

Conclusion

You're not really going to help people much who use long passwords by hashing first. Some groups you can definitely help. Some you can definitely hurt.

But in the end, none of it is overly significant. The numbers we are dealing with are just WAY too high. The difference in entropy isn't going to be much.

You're better off leaving bcrypt as it is. You're more likely to screw up the hashing (literally, you've done it already, and you're not the first, or last to make that mistake) than the attack you're trying to prevent is going to happen.

Focus on securing the rest of the site. And add a password entropy meter to the password box on registration to indicate password strength (and indicate if a password is overlong that the user may wish to change it)...

That's my $0.02 at least (or possibly way more than $0.02)...

As Far As Using A "Secret" Pepper:

There is literally no research into feeding one hash function into bcrypt. Therefore, it's unclear at best if feeding a "peppered" hash into bcrypt will ever cause unknown vulnerabilities (we know doing hash1(hash2($value)) can expose significant vulnerabilities around collision resistance and preimage attacks).

Considering that you're already considering storing a secret key (the "pepper"), why not use it in a way that's well studied and understood? Why not encrypt the hash prior to storing it?

Basically, after you hash the password, feed the entire hash output into a strong encryption algorithm. Then store the encrypted result.

Now, an SQL-Injection attack will not leak anything useful, because they don't have the cipher key. And if the key is leaked, the attackers are no better off than if you used a plain hash (which is provable, something with the pepper "pre-hash" doesn't provide).

Note: if you choose to do this, use a library. For PHP, I strongly recommend Zend Framework 2's Zend\Crypt package. It's actually the only one I'd recommend at this current point in time. It's been strongly reviewed, and it makes all the decisions for you (which is a very good thing)...

Something like:

use Zend\Crypt\BlockCipher;

public function createHash($password) {
    $hash = password_hash($password, PASSWORD_BCRYPT, ["cost"=>$this->cost]);

    $blockCipher = BlockCipher::factory('mcrypt', array('algo' => 'aes'));
    $blockCipher->setKey($this->key);
    return $blockCipher->encrypt($hash);
}

public function verifyHash($password, $hash) {
    $blockCipher = BlockCipher::factory('mcrypt', array('algo' => 'aes'));
    $blockCipher->setKey($this->key);
    $hash = $blockCipher->decrypt($hash);

    return password_verify($password, $hash);
}

And it's beneficial because you're using all of the algorithms in ways that are well understood and well studied (relatively at least). Remember:

Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break.

• Bruce Schneier

Solution 2

Peppering passwords is surely a good thing to do, but let's see why.

First we should answer the question when exactly a pepper helps. The pepper only protects the passwords, as long as it stays secret, so if an attacker has access to the server itself, it is of no use. A much easier attack though is SQL-injection, which allows read-access to the database (to our hash-values), i prepared a demo of SQL-injection to show how easy it can be (click the next arrow to get a prepared input).

Then what does the pepper actually help? As long as the pepper stays secret, it protects weak passwords from a dictionary attack. The password 1234 would then become something like 1234-p*deDIUZeRweretWy+.O. This password is not only much longer, it contains also special characters and will never be part of any dictionary.

Now we can estimate what passwords our users will use, probably more users will enter weak passwords, as there are users with passwords between 64-72 characters (actually this will be very rare).

Another point is the range for brute-forcing. The sha256 hash function will return 256 bits output or 1.2E77 combinations, that's ways too much for brute-forcing, even for GPU's (if i calculated correctly, this would need about 2E61 years on a GPU in 2013). So we do not get a real disadvantage applying the pepper. Because the hash-values are not systematic you cannot speed up brute-forcing with common patterns.

P.S. As far as i know, the 72 character limit is specific to the algorithm of BCrypt itself. The best answer i found is this.

P.P.S I think your example is flawed, you cannot generate the hash with the full password length, and verify it with a truncated one. You probably meant to apply the pepper the same way for generating the hash and for verification of the hash.

Solution 3

Bcrypt uses an algorithm based on the expensive Blowfish key setup algorithm.

The recommended 56 byte password limit (including null termination byte) for bcrypt relates to the 448 bit limit of the Blowfish key. Any bytes beyond that limit are not fully mixed into the resulting hash. The 72 byte absolute limit on bcrypt passwords is therefore less relevant, when you consider the actual effect on the resulting hash by those bytes.

If you think your users would normally choose passwords over 55 bytes in length, remember you can always increase the rounds of password stretching instead, to increase security in the case of a password table breach (although this has to be a lot compared with adding extra characters). If the access rights of users are so critical that users would normally require a massively long password, then the password expiry should also be short, like 2 weeks. This means that a password is much less likely to be remain valid while a hacker invests their resources in defeating the work factor involved in testing each trial password to see if it will produce a matching hash.

Of course, in the case of the password table not being breached, we should only allow hackers, at most, ten attempts to guess a user's 55 byte password, before locking the user's account out ;)

If you do decide to pre-hash a password that is longer than 55 bytes, then you should use SHA-384, as it has the largest output without going over the limit.

Comments

[Frederik Kammer]

Thank you very, very much for this detailed answer. This really helps me!

[martinstoeckli]

My compliment for this answer. One little nit-pick though, it's the big majority of users, that use very weak passwords, words and derivates contained in a dictionary for cracking passwords, a pepper would protect them independend of entrophy questions. To avoid loosing entrophy, you could just concatenate password and pepper. However your suggestion about encrypting the hash-value is probably the best solution to add a server-side secret.

[ircmaxell]

@martinstoeckli: My issue with the concept of pepper is not in the value of it. It's in that the application of the "pepper" goes into uncharted territory in terms of the cryptographic algorithms. That's not a good thing. Instead, I believe that cryptographic primitives should be combined in a way that they were designed to go together. Basically, the core concept of a pepper sounds to me in my ears like some people who knew nothing about cryptography said "More hashes are better! We have salt, pepper is good too!". I'd just rather have a simpler, more tested and more straight forward impl

[martinstoeckli]

@ircmaxell - Yes, i know your point of view and i agree, as long as the hash-values will be encrypted afterwards. If you do not take this additional step, a dictionary attack will simply reveal too many weak passwords, even with a good hash algorithm.

[ircmaxell]

@martinstoeckli: I disagree there. Storing of secrets is not a trivial thing to do. Instead, if you use bcrypt with a good cost (12 today), all but the weakest class of passwords are safe (dictionary, and trivial passwords are the weak ones). So I would rather recommend people focus on educating the user with strength meters and getting them to use better passwords in the first place...

[martinstoeckli]

@ircmaxell - The weakest class of passwords is not the rarest one. To judge whether a password would be cracked in a real dictionary attack, a strength meter would require a dictionary on its own. A leaking database is a real threat (SQL-injection, thrown away backups, discarded servers...), so adding a server-side secret is not an academic step, it helps even if the key is stored hardcoded somewhere. Your solution with encrypting the hash-value would have another advantage, it allows to exchange the key if necessary, i like this idea.

[Sliq]

Regarding your P.P.S, i can just say: Yes, he can verify the truncated password with the hash of the non-truncated one and still get true. That's what this question is all about. Have a look yourself: viper-7.com/RLKFnB

[martinstoeckli]

@Panique - The problem is not the calculation of the BCrypt hash, it's the HMAC before. For generating the SHA hash, the OP uses the full length password and uses the result as input for BCrypt. For verification, he truncates the password before calculating the SHA hash, then uses this completely different result as input for BCrypt. The HMAC accepts input of any length.

[Daan Bakker]

I think you have to account for the possibility someone might need more than 72 characters. What if they to use the contents as a file for a key (grandma.jpg) and only the file header gets used? What if someones password gets compromised and (s)he only changes the last part of it? It would be better to throw an error if you don't want to support long passwords than to make silent assumptions like this.

[zaph]

"the password expiry should also be short, like 2 weeks" of "massively long password"s, really, why bother even saving the password then, just use password reset every time. Seriously, that is the wrong solution, move to two factor authentication with a token.

[Phil]

Thanks @zaph. Are you able to point me to an example of that? It sounds interesting.

[zaph]

[DRAFT NIST Special Publication 800-63B Digital Authentication Guideline]( pages.nist.gov/800-63-3/sp800-63b.html), 5.1.1.2. Memorized Secret Verifiers: Verifiers SHOULD NOT require memorized secrets to be changed arbitrarily (e.g., periodically). Also see Toward Better Password Requirements by Jim Fenton.

[zaph]

The thing is that the more often a user is required to change a password the worst the password choices become thus reducing security. User have a limited amount of good memorizable passwords and they run out, either choosing really bad passwords or writing them on post-it notes stuck to the bottom of the keyboard, etc.