Pre-hash password before applying bcrypt to avoid restricting password length

Question

Good practice is not to unnecessarily restrict password length, so that appropriately-long passphrases (perhaps 35-45 chars for 6/7 dicewords) can be used. (See e.g. Should I have a maximum password length? where a maximum of 1K is suggested, to protect against DoS without restricting users' ability to set long passwords.)

bcrypt is also commonly recommended (see e.g. Do any security experts recommend bcrypt for password storage?, http://chargen.matasano.com/chargen/2007/9/7/enough-with-the-rainbow-tables-what-you-need-to-know-about-s.html)

It is also recommended to use a salt (random, and stored with the password hash) -- I believe 32-bits (4 characters) is often recommended. (I understand the salt-size rationale to be "enough that the number of combinations is much bigger than the number of user records AND is enough to make rainbow tables infeasibly large" -- 16 bits is enough for the second part but may not be enough for the first.)

But AIUI bcrypt only hashes 55 bytes -- with 4 chars for the salt that leaves 51 for the password.

I'm guessing that we shouldn't just bcrypt(left(password,51)) and ignore the last characters.

Should we just limit users to 50 characters in their password (enough for nearly everyone, but not definitely enough)?

Should we use something like bcrypt(sha256(salt+password)) instead, and allow up to 1K characters? Or does the addition of the sha256 (or sha512?) step reduce the overall security somehow?

Do scrypt or PBKDF2 have similar length restrictions?

(The last question is just for interest, really -- I realise that the space-hardness/FPGA-resistance, and relative newness of scrypt, and the GPGPU-resistance of bcrypt compared with PBKDF2 are far more important considerations in deciding which hash to use.)

Answer 1

Using a secure hash function to preprocess the password is secure; it can be shown that if bcrypt(SHA-256(password)) is broken, then either the password was guessed, or some security characteristic of SHA-256 has been proven false. There is no need to fiddle with the salt at that level; just hash the password, then use bcrypt on the result (with the salt, as bcrypt mandates). SHA-256 is considered to be a secure hash function.

The point of a salt is to be unique -- as unique as possible, so that no two hashed passwords use the same salt value. 32 bits are a bit low for that; you should use a longer salt. If you have n bits of salt, then you will encounter collisions (two hashed passwords using the same salt) as soon as you have more than about 2^n/2 hashed passwords -- that's about 65000 with n = 32, a not too high value. You'd better use 64 bits or more of salt (use 128 bits and you can cease to worry about it).

Answer 2

Bcrypt uses a 128-bit salt AND a 55 character (max) password. You do not need to add any other salt values; bcrypt handles that.

The designers of bcrypt felt that the 55 character limit on the password wasn't an issue since the hash has a 128-bit output. If your password is greater than 55 characters, the designers assumed that you are already providing more than 128-bits of entropy so this isn't a problem. On the contrary, the NIST guidelines would count this as only 77 bits of entropy. The NIST guidelines are based on the fact that pass phrases have less entropy per character than random passwords and on the assumption that users will use pass phrases for longer passwords. To better ensure that you get a full 128-bits of entropy, you could allow longer passwords and hash them using SHA-256 or SHA-384 to compress them to an acceptable length. You could also just simplify things by using scrypt or PBKDF2 which do not have length limitations. Scrypt is designed to be "memory hard" in addition to being computationally time-consuming; that would be my choice of algorithms.