Is there a way to use bcrypt with passwords longer than 72 bytes securely?

Question

From my understanding BCrypt truncates the password to 72 bytes. If a password is longer than 72 bytes, what is a way to store that password using bcrypt securely without compromising it? Or is this incorrect and we should just let bcrypt truncate it?

The reason why I ask is that I've seen some implementations where they SHA-256 the password first then enter it into BCrypt (e.g. PassLib bcrypt_sha256). However the SHA-256 output is a 32 byte digest. If the original password before the SHA-256 was longer than 32 bytes doesn't hashing it with SHA-256 compromise bcrypt by shortening it to 32 bytes?

If that is the case with SHA-256 would SHA-512 be a more secure option with 64 bytes?

I've seen in some places like Wikipedia and SE Cryptography where they say 56 bytes is the max password byte length. What password byte length is optimal for bcrypt passwords if it isn't 72 bytes?

If that is the case, then with passwords less than the optimal byte length is it better to hash them to a longer byte length?

Answer 1

Introduction

BCrypt is a password-based KDF (far from state-of-the-art, but better than PBKDF2, because BCrypt requires sizable RAM, which greatly increases the cost of hardware-accelerated password search).

Bcrypt is based on the block cipher Blowfish, with the initial processing of the password reminiscent of Blowfish's key preprocessing. Bruce Schneier's Description of a new variable-length key, 64-bit block cipher (Blowfish) (in the proceedings of the first FSE conference, held Dec. 1993) defines that Blowfish's key is of 4 to 56 bytes (32 to 448 bits), with this rationale for the maximum:

The 448 limit on the key size ensures that the every bit of every subkey depends on every bit of the key. (Note that every bit of $P_{15}$, $P_{16}$, $P_{17}$, and $P_{18}$ does not affect every bit of the ciphertext, and that any S-box entry only has a $.06$ probability of affecting any single ciphertext block.)

Using more than 56 bytes of key for Blowfish is against its definition and design rationale: key bytes beyond the 72^nd have no effect whatsoever, and the few before may have somewhat less diffusion (though not nearly as badly as the above quote suggests). Some Blowfish implementations nevertheless accept keys with any positive number of bytes.

Bcrypt, as defined in Niels Provos and David Mazières's A Future-Adaptable Password Scheme (in proceedings of Usenix 1999) accepts a key of 1 to 72 bytes; even with the lowest cost parameter, all key bytes have ample time to reach full diffusion. Bytes beyond the 72^nd (if any) have no effect whatsoever. The mapping of password to key is "defined" by:

take user-chosen passwords as keys

and implementations are known to vary wildly. ASCII only? Some 8-bit codepage extension? Replacement of gremlins with 0x3F bytes? Little-endian or Big-endian UTF16 or UTF32? UTF8, with or without BOM? Length byte, zero-termination? Your guess!

What should be done if the password can be more than 72 bytes?

If there was a formal requirement that it is impossible to exhibit equivalent passwords, or that every character in a password is significant, or with UTF32-encoded passwords (thus only 18 characters), it would be bad to just truncate a password/passphrase to 72 bytes.

The option of replacing Bcrypt's mapping of password to key by a cryptographically secure hash is excellent, if all the characters in the password make it to the input of the hash, and all the bytes in the hash's output make it to the key (I can imagine an implementation where bytes beyond the leftmost 0x00 in the hash, if any, are just ignored; that would be extremely bad, for one in 256 passwords could be replaced by any password with the first byte of its hash equal to 0x00).

The hash should be computationally collision-resistant to a degree significantly better than the strength of the requirement that it is impossible to exhibit equivalent passwords (thus with output of $h$ bits with $h$ significantly above $2k$ if aiming at $k$-bit security level, and unbroken from a collision-resistance standpoint; no MD5, or even SHA-1 from a theoretical standpoint). The strength of all other properties (minimum expected cost for password search by brute force, first and second preimage resistance, resistance to length-extension, and more generally computational indistinguishibility from a random oracle) demonstrably follow from Bcrypt's security.

If there is an entropy of $e$ bits in the input password, and for a hash of $h$ bits indistinguishible from a random oracle, it is expected that there are about $\max(e,h)$ bits of entropy in the key fed to Bcrypt, nearly exactly when $e\ll h$ or $e\gg h$, and within less than about $0.83$ bits in the worst case $e=h$ (see this).

SHA-256 (32 bytes) is thus perfectly fine in practice for any password/passphrase that a human types in (or even more so, memorizes); SHA-512 (64 bytes) can't harm. Ample entropy remains if there was enough in the first place.

Answer 2

I would feel perfectly safe with a 72 byte password.

Computing a shorter hash of a longer password is not necessarily weakening your scheme. Passwords are typically not truly random and contain only human readable characters, so that for instance a password of 60 bytes may have an entropy of only 32 bytes. See https://en.wikipedia.org/wiki/Password_strength .

Answer 3

Hashing a password does not necessarily weakens the password.

What is more important in this case is the collision resistance of the hash algorithm. As long as the collision resistance is given a hash values used is enough to get a high security.

Answer 4

Rather than:

String HashPassword(String password)
{
   return BCrypt.HashPassword(password);
}

use

String HashPassword(String password)
{
   //Pre-hash the long password down to a fixed 43 character base64 encoded password
   String hashedPassword = Base64Encode(SHA256(password.ToUtfBytes()));

   return BCrypt.HashPassword(hashedPassword);
}

Bonus Chatter

bcrypt is not a password-based key derivation function; it never claimed to be.

• You could use it as one
• as long as you only ever need 184-bit keys

The resulting "hash" that bcrypt generates comes from repeatedly encrypting the 24-byte text:

OrpheanBeholderScryDoubt
\______/\______/\______/
8-bytes 8-bytes 8-bytes

Which results is 24-byte encrypted text, e.g.:

8520af9f033db38c 085fd25e2daa5e84 a2b961d2f129c9a4

But then the canonical OpenBSD implementation, and every implementation that wants to be compatible with them, drops the final byte, leaving you only with 23-bytes (184-bits) of "key":

8520af9f033db38c 085fd25e2daa5e84 a2b961d2f129c9a4

tldr: BCrypt is not a KDF. You cannot ask it to generate n bits for you. Not 56-bits, not 128-bits, not 192-bits, not 256-bits. It is not a key derivation function.

Of course, nothing stops you from inventing one:

Byte[] bcryptKdf(String password, Int32 desiredNumberOfBytes)
{
   String prehash = Base64Encode(SHA256(password.ToUtfBytes()));

   String hash = BCrypt.HashPassword(prehash);

   //Use PBKDF2 for it's ability to generate an arbitrary number of bytes.
   //We're not using it for it's strength (which is good, it has none). 
   //BCrypt supplied the strength. PBKDF2's job is to vomit out bytes
   return PBKDF2_SHA256(hash, "", desiredNumberOfBytes, 1);
}

This using of PBKDF2 for its ability to generate an arbitrary number of bytes is the approach used by scrypt:

Byte[] scrypt(String password, String salt, Int32 desiredNumberOfBytes)
{
   Byte[] expensiveSalt = AllTheExpensiveStuffThatMakesUpScrypt(password, salt);
   
   return PBKDF2_SHA256(password, expensiveSalt, desiredNumberOfBytes, 1);
}