http://groups.google.com/group/linux.debian.user/browse_thre...
http://www.akkadia.org/drepper/sha-crypt.html
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
> 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
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.
Refs
1. SHA512 vs. Blowfish and Bcrypt - http://stackoverflow.com/questions/1561174/sha512-vs-blowfis...
2. Schneier on SHA-512 variants http://www.schneier.com/blog/archives/2011/02/nist_defines_n...
- 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.
tptacek talked a little about this in one of the posts I linked above: http://news.ycombinator.com/item?id=1091445
------------------------
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:
http://news.ycombinator.com/item?id=1091465
http://news.ycombinator.com/item?id=995685
http://chargen.matasano.com/chargen/2007/9/7/enough-with-the...
------------------------
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.
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.
http://news.ycombinator.com/item?id=1091465
> 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...
After all, an attacker does not need to recover the password from the hash, all he has to do is capture the hash and replay it.
Also, tptacek made a few interesting comments about client-side cryptography:
http://news.ycombinator.com/item?id=1755713
http://news.ycombinator.com/item?id=1756394
At this point, I'm less worried about somebody getting access to some random startup I signed up for than I am about them using the leaked password to gain access to my other accounts.
(I've recently changed my password scheme to using a different one for every service, but this just puts me within a minority.)
Doesn't http://en.wikipedia.org/wiki/Digest_access_authentication do this? Also the server could store the nonce in a session.
If the salt is stored on the server, in a login.php script for example, and there is (just) a database compromise then an attacker will be at a disadvantage because they will need to figure out the salt first before cracking any of the passwords.
In fact, this is something being ignored here quite a bit. A number of potential attacks only lead to the database - or part of it - being exposed. If you have a large enough salt stored in your unaffected code base then an attacker is going to have a hard time.
Hashing ≠ Encryption.
Unlike encryption, where an encrypted message is intended to be decrypted by a trusted party, a hashed password is never intended to be 'unhashed'. Rather, the hash of the password supplied by the user is compared against the hash value stored in the database. Given a sufficiently strong password P, it should be computationally infeasible for anyone to compute the value of P from hash(P).
Following your train of though, we should display the salt and the hash publicly. That is extremely dumb.
Put your passwords in your post, otherwise you'll be doing security through obscurity! oh snap?
If you use a "clever" scheme to store / generate your salt, you make your system more complex in an attempt to hide something that does not really need to be hidden. You might also end up introducing implementation flaws.
That's why bcrypt uses nonces for its salts, and simply appends them to the encrypted passwords.
Also see http://en.wikipedia.org/wiki/Kerckhoffs%27s_Principle
I note that the question was migrated from StackOverflow to security.stackexchange.com. After all, this is an issue that the security nerds care about. Why bother ordinary developers with it? </sarcasm>
The other day, I saw the following post about password hashing in my RSS feed: http://isc.sans.org/diary.html?storyid=11110
- No mention of bcrypt (though the posts mentions key stretching using SHA1)
- "When selecting an algorithm to hash passwords, it is important to select carefully as it is difficult to change the algorithm later. You will have to ask users to change their password if you do as you no longer know what password they picked." --> seriously? you can update the password the next time they log in...
- "You could also add a secret, in addition to the salt. If the secret is not stored in the database, it would not be easily reachable via a SQL injection exploit (yes, you can use them to read files, but it requires sufficient privileges)." --> security through obscurity, nice
- "For the paranoid, you may want to do the hashing on the client side (javascript) . This way, the server never receives the plain text password. We do this here for the ISC website on our login form [2]." --> oh noes...
Note that the blog has ~15k subscribers according to Google Reader...
---------
I also launched a debate on StackOverflow the other day. A self-proclaimed "security expert" (he later edited his post to remove this part) was advising against using bcrypt, arguing that it would facilitate DOS attacks against the login page... He prefers security through obscurity, using a secret salt:
http://security.stackexchange.com/questions/4781/do-any-secu...
I thought it was a bad idea to leave this answer unchallenged, so I tried arguing with him. I was met with arguments of authority such as "Wow you are out of your element and could not be more misguided on this topic" or "you disagree because you don't understand. Show me an exploit you have written, then I'll pay attention to you.". Happily, some (more experienced) people got in on the debate. I hope this will help developers make an informed choice, if they stumble upon his answer...
(edit: list formatting)