which the version of crypt(3) in glibc. It is almost the same as bcrypt. One difference is that it uses SHA256 or SHA512 instead of Blowfish. But that implementation has the same ability to expand the work factor like bcrypt.
So I'd say that the algorithm they're using is slow and is designed to be slow
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.
# 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:
Thank you, that is an excellent reply, covering all of the main points raised in the link.
My impression is that SHA512 with 5000 rounds is competitive with bcrypt (per Schneier in February, at least). But ... this is not the default on Debian, DES is, which I understand is not remotely competitive with bcrypt.
I checked my server, and it uses the default DES... time to harden the passwords.
I just thought about another reason why bcrypt might be more useful for a web app than for hashing OS passwords:
- when a webapp loses its user table, the devs will be responsible for compromising thousands of password (which user often re-use elsewhere). This is what happened with the Gawker hack and the recent lulzsec database dumps.
- when somebody accesses your /etc/shadow file, he likely already has root access to your machine, so you are pretty much owned anyway. Protecting your password might help a little, but it's less useful than in the above case.
Now, to address your point: stretched SHA512 (SHA512 iterated 5000 times) is indeed a lot better than calling SHA512 once. But bcrypt still has some advantages over it by design, which makes it even better for password hashing. Some links:
Regarding your second link (Schneier on SHA-512 variants), I don't see anything about bcrypt or password hashing there. He talks about the advances of hash functions, but those are fast hash functions. Fast hash functions are very useful in cryptography, but they are the opposite of what you want for a password hashing scheme.
why is multi-iteration sha-2 less ideal than bcrypt, even if the work factors between the two are calibrated to require the same amount of computation?
the only argument i've heard is that sha-2 can be implemented in specialized hardware (well-funded attacker) that is much much faster than CPU/GPU, whereas this is not as easy for bcrypt?
however, with multi-iteration hashing, you can strengthen the hash further w/o the user having to log in again.
> the only argument i've heard is that sha-2 can be implemented in specialized hardware (well-funded attacker) that is much much faster than CPU/GPU, whereas this is not as easy for bcrypt?
Yep. I think that's one of the main reasons. As tptacek said in the above link:
"There's a difference: bcrypt (and moreso scrypt) were designed to be hard to speed up, while SHA1 was designed at least in part to be easy to speed up."
In my opinion, the main advantage of bcrypt is the simplicity. It handles everything for you: salting, "slow" hashing, password checking. You simply have to specify a work factor and you are good to go. No need to implement any crypto yourself.
> however, with multi-iteration hashing, you can strengthen the hash further w/o the user having to log in again.
That's a very good point, I hadn't thought about that. I wonder if we can do this with bcrypt too.
IMO, as long as you use either bcrypt, scrypt, PBKDF2, or password stretching, you are good to go...
http://groups.google.com/group/linux.debian.user/browse_thre...