News for hackers. Stuff that matters.
Re:How To Safely Store A Password by sordidarray on Sunday January 31, 2010 @07:11PM (#1091402)
I disagree wholeheartedly. The article is based around the fallacy we've seen time and time again, of throwing more cryptography at a problem that cryptography alone cannot solve. In the end, a crappy password is a crappy password. Successfully discouraging your users from using a crappy password has much better repercussions (for the user, for you, and for the web in general) than switching from a hash-based authentication system to bcrypt. Use bcrypt for additional security, but do not use it in an attempt to solve the problem of crappy passwords that the article falsely claims bcrypt solves.

To be more technical, bcrypt, like PBKDF2 and other schemes of that nature, add a significant amount of additional computation by iteratively applying a primitive, but still maintain a relatively small circuit size (in comparison to the primitive itself, which is usually designed to fit onto smart cards and the like). Creating and using algorithms which are "memory-hard" or require larger circuits reduces the number of circuits one can place on some area of silicon and drives up the cost of an attack. In other words, mounting an attack on bcrypt or PBKDF2 is still cheaper and potentially much faster than we'd like it to be (which is the reason those algorithms are "tunable"--you scale the number of iterations up as computers become faster). This, along with some example memory-hard functions was the topic of Percival's paper, "Stronger Key Derivation via Sequential Memory-Hard Functions," which correctly cites Bernstein as the source of emphasis on practicality in measuring an attack not by computational complexity, but the cost of launching the attack. See http://www.bsdcan.org/2009/schedule/attachments/87_scrypt.pd... if you're interested in reading further.

Re:How To Safely Store A Password by tptacek on Sunday January 31, 2010 @07:43PM (#1091445)
The mistake you're making is thinking of bcrypt as a protection for end-users and their passwords.

It isn't. Bcrypt exists to protect application developers.

A user with a crappy password is getting his account busted one way or another. You're right to point that out. Cryptography won't solve that problem.

The problem crypto solves is this: a crappy web app that loses its user table is royally screwed if its devs settled for "salted hashes". At the whim of their attackers, hundreds or thousands of their user's passwords are going to hit Rapidshare. That's what the devs will be famous for.

Bcrypt keeps that from happening. You'll get famous behind losing 1000 passwords. You won't get famous behind losing 20.

Re:How To Safely Store A Password by sordidarray on Sunday January 31, 2010 @08:20PM (#1091504)
A poorly-written web app whose SQL database is compromised has bigger problems than protecting the integrity of poorly chosen passwords (especially if they store financial information).

Losing such a collection of salted hashes does not render one "royally screwed." Those hashes (or HMACs) are still cryptographically secure, which means it's computationally infeasible to find a first preimage provided the password doesn't suck. You seem to think (or are at least implying) that bcrypt is impervious to standard iterative bruteforce attacks, but that's just not the case. Much like PBKDF2, and other iterative hashing techniques, bcrypt is more resistant, but still "vulnerable" to such an "attack." bcrypt's main advantage over other iterative techniques, in my opinion, is the 4KiB of s-boxes used by Blowfish.

Re:How To Safely Store A Password by tsally on Sunday January 31, 2010 @09:05PM (#1091595)
A poorly-written web app whose SQL database is compromised has bigger problems than protecting the integrity of poorly chosen passwords (especially if they store financial information).

Are you suggesting that because a comprise is bad, nothing should be done to reduce the magnitude of the impact? This argument does not hold up in general, and it is especially weak when arguing about using encryption algorithms with freely available, high quality implementations. The developer effort required to use bcrypt is minimal.

Also, you seem to be making the incorrect assumption that only poorly written web applications get their databases compromised. Web applications with excellent security get their databases stolen for a variety of other reasons. Even if the programmers do everything right, a careless employee might get his/her password sniffed or stolen by a key logger. If a company uses external hosting, its database could get stolen because of a mistake by the hosting providers.

In summary, the risk of your database being stolen is always present, regardless of the diligence of the the programmers who implemented the web application. The fact that a compromise is bad is not justification for ignoring simple security measures that take minimal effort to implement.

Re:How To Safely Store A Password by sordidarray on Sunday January 31, 2010 @09:45PM (#1091648)
Of course I'm not suggesting such a thing.

The effort required to implement bcrypt in new systems is indeed small, and such a method is the suggested way to do, but depending on the amount of users, the effort required to port an existing database over to bcrypt (e.g., Facebook) could be immense, and the result disastrous if not done with great care.

Ptacek said, and I quote, "... a crappy web app ..." so why do you only cite me as making the "incorrect assumption that only poorly written web apps have their databases compromised?"

Again, I agree that is the case in new systems, but I disagree that one is "effed," as the article puts it, if they have a large database of salted hashes.

Re:How To Safely Store A Password by codahale on Monday February 01, 2010 @03:05AM (#1092009)
I should have been more precise in the article. Here:

A system which uses an adaptive hash function like bcrypt is ~6 orders of magnitude less effed in the event of a compromised database than a system which uses a standard hash algorithm and a salt, ceteris paribus.

I would hope you agree that those ~6 orders of magnitude could well be the difference between "not noticeably effed" and "profoundly effed."

Re:How To Safely Store A Password by codahale on Sunday January 31, 2010 @09:12PM (#1091606)
He's implying that using bcrypt (and other iterative hash functions like PBKDF2 and scrypt) raises the cost of mounting a dictionary attack compared to commonly-used and -recommended hash algorithms like SHA256.

Which, uh, is an objectively verifiable fact.

Re:How To Safely Store A Password by tptacek on Sunday January 31, 2010 @08:54PM (#1091574)
Losing a Unix password file in the 1990s would have been newsworthy. Password files were "secured" using Unix crypt(3), an algorithm that at least made a nod towards resisting brute force attacks --- so much so that when PHK wrote FreeBSD's md5 scheme, he iterated it PBKDF-style, because even then it was clear that using cryptographic hashes "straight" was a bad idea.

The biggest differences between Mindvox losing it's password file in 1995 and a webapp losing its user table in 2010 are:

* Web apps are getting fielded with straight SHA1 hashes, which is inferior even to FreeBSD's original MD5 hash scheme.

* Brute force attacks have gotten much faster.

The main advantage to bcrypt over, say, AES, is that the key setup is really slow. Mazieres spotted a weakness in Blowfish and turned it into a benefit.

Is there some real argument you have with me? I agree: if you lose your user table, you have real problems apart from losing password hashes --- though we could bicker about which of those problems is worse. Where are you disagreeing with me?

Re:How To Safely Store A Password by sordidarray on Sunday January 31, 2010 @09:20PM (#1091612)
I never said SHA-1, a cryptographically insecure hash, was a good choice. It's important to note in your differences that, for the most part, cryptographic hash functions in current use have gotten much slower (e.g., SHA-256 vs MD5), but are also getting much better (SHA-3 competition).

The argument I have is this: The passwords that are going to be hitting Rapidshare in your scenario are the crappy or short ones, whether you use bcrypt, scrypt, PBKDF2, salted hashes or HMAC. Encourage them to use bcrypt or some other iterative technique for the security benefits, but don't exaggerate and tell them that they're "effed" if they have salted hashes. They're still a long way away from storing passwords in plaintext.

Re:How To Safely Store A Password by tptacek on Sunday January 31, 2010 @09:24PM (#1091618)
You're arguing for the sake of arguing. The developing weaknesses in SHA-1 don't make it a poor password hash. That's an irrelevant factoid you threw in to cloud the argument.

Pick a number of passwords to lose from a table. Hash them with any of the SHA-3 contestants and a "salt": you will lose more. Hash them with bcrypt, you will lose less.

Again I'm left asking you: what's your point? What are you trying to prove? That you know that there's a SHA-3 contest? You haven't refuted anything this article says; in fact, you keep accidentally managing to validate it.

Re:How To Safely Store A Password by sordidarray on Sunday January 31, 2010 @09:36PM (#1091626)
I'm not "arguing for the sake of arguing." I'm trying to explain my point to you, and I'm doing so in a polite manner, which is exactly what I'd expect from you.

The weaknesses in SHA-1 make it a poor cryptographic hash, which make it a poor pseudorandom function, which has a significant potential to make it a poor password hash.

My point, for the second time, is that you're not "effed" if you use salted hashes.

I'm not trying to "prove" anything. I'm stating my opinion on the matter. This isn't a pissing contest, rather, a forum for discussion.

Re:How To Safely Store A Password by dfranke on Sunday January 31, 2010 @10:04PM (#1091675)
All public results against SHA-1 are collision attacks. Password hashing doesn't rely on collision-resistance, only one-wayness. Not even MD5 has any published preimage attacks against it. The known weaknesses in these functions have nothing to do with why they're poor choices for password storage.
Re:How To Safely Store A Password by tptacek on Sunday January 31, 2010 @09:40PM (#1091634)
I'd like you to explain how you'd exploit a problem with SHA-1, or, to make it more interesting, MD5 or MD4, to attack a "typical" hashed password (say, Keychain.app "memorable") more quickly than via iterated brute force.
Re:How To Safely Store A Password by sordidarray on Sunday January 31, 2010 @10:10PM (#1091678)
Currently such attacks are infeasible, but there are some very interesting, and very promising families of collision-based attacks (such as herding) which may yield results in that area, although such attacks may only work in specific cases.
Re:How To Safely Store A Password by codahale on Sunday January 31, 2010 @09:44PM (#1091645)
Uh. All of the current SHA-3 candidates are as fast or faster than SHA-1. That's one of the contest's design goals:

NIST expects SHA–3 to have a security strength that is at least as good as the hash algorithms currently specified in FIPS 180–2, and that this security strength will be achieved with significantly improved efficiency.

http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov0...

Re:How To Safely Store A Password by sordidarray on Sunday January 31, 2010 @10:03PM (#1091674)
Yes, that's why I specifically said, "in current use." No one should be using SHA-3 hash functions. SHA-256 and SHA-1 are much slower than MD5 and very much slower than MD4. The "Getting much better" comment was in reference to speed improvements as well as security improvements (such as removal of vulnerability to length-extension attacks).
Re:How To Safely Store A Password by codahale on Sunday January 31, 2010 @08:10PM (#1091485)
Also, you point out that "successfully discouraging your users from using a crappy password has much better repercussions." This is true, and I'm curious to know how you personally achieve this with your users, given that the vast majority[1] of users choose spectacularly crap passwords.

[1] http://www.imperva.com/docs/WP_Consumer_Password_Worst_Pract...

Re:How To Safely Store A Password by steveplace on Sunday January 31, 2010 @08:42PM (#1091540)
https://twitter.com/signup

Start typing in the pw box, if it's not strong enough, they'll let you know.

Also, try "123456" or "password"

Re:How To Safely Store A Password by bmj on Sunday January 31, 2010 @09:55PM (#1091665)
Ah, but "1password" is good.
Re:How To Safely Store A Password by moe on Monday February 01, 2010 @06:29AM (#1092178)
Rule of thumb: If you're going to look for a good implementation of X (anything) then scratch twitter.com from your list before you start.
Re:How To Safely Store A Password by run4yourlives on Monday February 01, 2010 @02:52PM (#1093272)
Why? In this case, it's better than most. The details need work, but the idea is sound.
Re:How To Safely Store A Password by codahale on Sunday January 31, 2010 @07:36PM (#1091431)
I'm familiar with cperciva's scrypt, and I think it's a great solution. That said, I've only seen C and Ruby bindings for it.

I'd love to recommend its use over bcrypt, as memory constraints are much more expensive than computational constraints, but recommending something most developers don't have access to would result in more weak hashing schemes in production.

Re:How To Safely Store A Password by dfranke on Sunday January 31, 2010 @09:42PM (#1091641)
In any language with sane FFI, scrypt is pretty easy to write new bindings for. At my previous job I wrote a complete scrypt plugin for Openfire in a weekend, and only a couple hours of that was for writing the JNI bindings.
Re:How To Safely Store A Password by codahale on Sunday January 31, 2010 @09:54PM (#1091663)
Toss it up on GitHub, man.
Re:How To Safely Store A Password by dfranke on Sunday January 31, 2010 @09:56PM (#1091667)
I wasn't able to convince my boss to let me open-source it.
Re:How To Safely Store A Password by codahale on Sunday January 31, 2010 @11:43PM (#1091798)
Awww. :(
Re:How To Safely Store A Password by mock on Monday February 01, 2010 @07:39PM (#1093934)
I'm no cryptographer, so maybe this is a silly question... Any reason why I shouldn't just reimplement it in the high level language of my choice and release it open source?
Re:How To Safely Store A Password by kelnos on Sunday January 31, 2010 @08:19PM (#1091502)
You're talking about a completely different problem.

Yes, many users pick crappy passwords. That's a social problem, one that is difficult to address with technology[1].

Storing passwords on the server is unrelated to whether or not the user picked a good password. If an attacker gets ahold of a copy of your database, they will have a much easier time of turning SHA1 hashes of passwords into actual passwords than of turning bcrypt-encrypted passwords into actual passwords (the latter being orders of magnitude more difficult, maybe to the point of being impractical as a target vector).

[1] You can always do things like require certain types of password complexity: minimum length, choice of characters from different character classes and cases, etc. But then you end up just moving the problem elsewhere: instead of using the crappy password they remember, the user has to write down their complex password, or maybe even store it in a text file on their hard drive.

Re:How To Safely Store A Password by sordidarray on Sunday January 31, 2010 @08:54PM (#1091573)
I'm not talking about a different problem.

The bruteforce attack described in the article primarily affects short and dictionary-based passwords. If the password is of sufficient length and complexity (the keyspace is large enough), then bruteforcing becomes computationally infeasible. What the article proposes is, essentially, to use a more computationally expensive algorithm for the benefit of protecting shorter, weaker, passwords. I disagree, and think that increasing the computational cost of the algorithm itself should be used to enhance the security of passwords, rather than having their security depend entirely on that increased cost.

Good passwords stored as a salted hash, or preferably, as an HMAC, are in no way insecure. I feel that implying otherwise is a disservice.

Re:How To Safely Store A Password by tptacek on Sunday January 31, 2010 @09:01PM (#1091588)
You sound like someone who has never run John the Ripper.

There clearly are passwords that are impractical to crack. To get one, just "head /dev/random | openssl sha1".

Nobody uses passwords like that. They're irrelevant. Instead, the smart ones use passwords that contain a combination of words, numbers, and punctuation. John the Ripper has been cracking those passwords for over a decade.

"Salted hashes" are insecure. They'd have been rejected by the FreeBSD team in 1997. If you choose to make a religion out of not using bcrypt, do what the RFC says and use PBKDF.