DISCLAIMER: I'm a web developer, not a cryptographer. I've had a passing interest in cryptography for the last few months, but I've never worked in the field. I learned about it by reading Cryptography Engineering (great book) and various HN comments and blog posts. So take the following with a grain of salt... and I hope someone knowledgeable can chime in. That being said, let's roll.

> What about Debian's reason for not using bcrypt, claiming the time it takes to hash is not a weak point in security of /etc/shadow?

That's a good question, but I'm not sure the discussion you linked to really explains why Debian does not use bcrypt. The first post is, ironically, the most interesting one: it links to Coda Hale's great article, and to a StackExchange question where we learn that bcrypt has been OpenBSD's default password scheme since OpenBSD 2.1 (http://www.openbsd.org/papers/bcrypt-paper.pdf). OpenBSD being well-known for its code quality and security focus, this would indicate that bcrypt is actually quite adapted for OS password hashing.

Some critics:

First, if you don't have the salt, but you do have the hash, then a rainbow table attack is completely pointless. Reason being is rainbow tables store hashes with a 1:1 ration to text. How the table is traversed is another story, but the fact remains that one hash will lead you to one piece of text. Now add a salt. If the salt is unknown, the length of the salt is 8 characters, and the characters used in the salt are [A-Za-z0-9./], or 64 characters, then there are effectively 64^8 possible hashes for one password. That's 281474976710656 hashes. Even moving at 700,000,000 passwords per second, you have to generate that many hashes per password. Point is, you have one massive keyspace to search through. Good luck.

Here, Aaron says that salts defeat rainbow tables because they are secret, thus increasing the keyspace. While not knowing the salt does complicate password cracking, this is not the reason we use salts. Rainbow tables let crackers trade time for space: they pre-compute password hashes once, and then use this table to avoid brute-forcing each password separately. A salt defeats this because it forces the cracker to either generate a very big rainbow table, which is impractical, or to generate a different rainbow table for each salt, which is the same as brute-forcing... This has nothing to do with the salt being secret. Your only goal here is to have a random salt (a nonce, ideally).

Lastly, the SHA1 and SHA2 algorithms were designed with security in mind. Sure, they're fast, but that's the point. If you're concerned about knocking a login prompt, you shouldn't be considering the speed of the algorithm. Instead, you should be spending your time learning PAM. If you're concerned about someone brute forcing an unshadow file, bcrypt isn't going to help you if the password is low in entropy (he gives an example of a 6-character password- seriously???). If your password is high in entropy, as it should be, then even if SHA1 could churn through 400GBps, it's not going to find it. Case in point, consider http://distributed.net hacking the 72-bit RSA key. 72-bits of entropy, and it would take them 1,100 years at their current rate to exhaust the keyspace entirely. That's only an 11-character password with [A-Za-z0-9] and [:punct:] as the possible characters. 1,100 years for an 11-character password.

Here, the argument is that there is no need to use bcrypt if the user chooses a password with a high entropy. That may be true, but then, what's the problem with making brute force attacks even slower by using bcrypt (or another slow hash function)? Low-entropy passwords would be harder to guess. High-entropy passwords would be impossible to guess.

The rest of the discussion focuses on the use of salts, and on how Debian stores these salts in the /etc/shadow file. At no point do they really talk about key stretching / bcrypt.

------------------------------------------------

Now, I decided to look at what Debian currently uses for password hashing. In the latest login.defs file ( http://anonscm.debian.org/viewvc/pkg-shadow/debian/trunk/deb... ), you can see:

# If set to MD5 , MD5-based algorithm will be used for encrypting password
# If set to SHA256, SHA256-based algorithm will be used for encrypting password
# If set to SHA512, SHA512-based algorithm will be used for encrypting password
# If set to DES, DES-based algorithm will be used for encrypting password (default)
# Overrides the MD5_CRYPT_ENAB option
#
# Note: It is recommended to use a value consistent with
# the PAM modules configuration.
#
#ENCRYPT_METHOD DES
#
# Only used if ENCRYPT_METHOD is set to SHA256 or SHA512.
#
# Define the number of SHA rounds.
# With a lot of rounds, it is more difficult to brute forcing the password.
# But note also that it more CPU resources will be needed to authenticate
# users.
#
# If not specified, the libc will choose the default number of rounds (5000).
# The values must be inside the 1000-999999999 range.
# If only one of the MIN or MAX values is set, then this value will be used.
# If MIN > MAX, the highest value will be used.
#
# SHA_CRYPT_MIN_ROUNDS 5000
# SHA_CRYPT_MAX_ROUNDS 5000

In my Ubuntu 11.04 install, ENCRYPT_METHOD was set to SHA512 (in /etc/login.defs). SHA_CRYPT_* is not specified, so the default number of rounds is used (5000). I think this means that, by default, Ubuntu hashes password by salting them and encrypting them 5000 times with SHA512. So, Debian uses salted stretched SHA512, which does slow down brute forcing a little... But is still not ideal when compared to bcrypt.

I see no real reason to avoid bcrypt when hashing OS passwords. Maybe they avoid it for backward compatibility? Maybe because it is not standard enough yet? Maybe they want to comply with FIPS 140-2?

Other great discussions on bcrypt / password hashing:

http://news.ycombinator.com/item?id=995634

http://news.ycombinator.com/item?id=1592007

http://news.ycombinator.com/item?id=266266

http://news.ycombinator.com/item?id=1091104