Hacker News Reader

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?

http://groups.google.com/group/linux.debian.user/browse_thre...

I think they use this:

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

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

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.

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...

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.

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.

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.

Regarding your question on the differences between bcrypt and iterated SHA-2, I think it's better if I link to comments by crypto / security experts:

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...

I know very little about security, but is there something wrong with using a hash in the client side and then using bcrypt on the server so that you never receive the plain text password?

I'm no security expert either, but I'm guessing the real solution is SSL. If you hash passwords in javascript, a middleman could easily just look up the source of your application and decrypt the hashed password coming over the wire.

>If you hash passwords in javascript, a middleman could easily just look up the source of your application and decrypt the hashed password coming over the wire.

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).

Of course, if you're doing the hashing on the client, there's no need to reverse the hash anyway. An attacker can just replay the hash they sniffed. You can do some additional things to avoid this (like using a nonce as part of the hash), but the best solution is still to just use SSL.

An attacker in that position could also capture the password coming over the wire. Both are of equal security in that situation. SSL is also middleman-able.

If the client sends hash(password) to the server, hash(password), for all intents and purposes, _is_ the password.

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.

This.

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

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

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

On the upside, it is an improvement for the use-the-same-password-on-many-services users, assuming the hash is not trivial to reverse like md5.

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.)

I'm no crypto expert but wouldn't using a nonce allow this approach to work?

How would you check the nonce? All your server gets is a black box hash.

Not a security expert here.

Doesn't http://en.wikipedia.org/wiki/Digest_access_authentication do this? Also the server could store the nonce in a session.

Hashing passwords on the client indicates that the salt is available to the client. In the event of a database compromise it's guaranteed then that the attacker will have the salt and be able to crack your passwords.

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.

Salts are suppose to be considered public. For the most part, they are defenses against rainbow tables and to make an attacker have crack each password individually.

Exactly; Having a secret hash is just another example of futile security through obscurity. You want an attacker to be able to know as many parts of the puzzle as possible and still be thwarted.

Agreed, but an important part of the article was that even public salted md5 passwords are ineffective.

not storing the password in sql has nothing to do with obscurity. In fact, it's smart. You do not understand what "security through obscurity" means.

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?

That's not what I said. Some amount of secrecy might better than none. But, you should not depend on it.

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

Many developers need to read and understand this.

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>