Hacker News Reader

Comment by tptacek | Hacker News Reader

NO THEY AREN'T.

This is a great example of a bona fide awful trade press article: some guy with a column-inch quota sees a piece by another trade press hack who is in turn digesting a blog post by someone who is "allergic to command line utilities" writing up someone else's GPU password cracking tool. And so, strong passwords are useless!

Except that this has nothing at all to do with why passwords are bad. The problem GPU crackers exploit was solved over a decade ago with adaptive hashing. GPU crackers cannot crack scrypted passwords of any real complexity in tenable amounts of time.

Once again: http://codahale.com/how-to-safely-store-a-password/

View on HN

I really hated that phrase 'allergic to command line utilities'. It reminds me of this odd attitude, which used to be a bit more common, that ignorance about computers is virtuous or amusing.

Bcrypt seems to have a big design oversight. Given a password stored with cost factor C1 that you would like to increase to cost factor C2, it seems to me that you have to have the plaintext password to do this. Thus, you have to wait until that user next provides the password, verify it, and then re-store it with cost factor C2.

That's no bug, its a feature!

Seriously though, this is a design decision that cannot be easily solved with any non-reversible encryption. If you were able to increase the cost factor, the you'd open the algorithm to attacks that reverse that process.

Err, no, that's actually not true. Take the case of PBKDF2 -- if you apply 1000 rounds of PBKDF2 to password X to get X' then apply 1000 rounds to PBKDF2 to password X' to get X'', applying 2000 rounds of PBKDF2 to password X == X''. You could increase the cost factor (number of rounds) every time the password is used, for instance.

Unless you run C2 on top of C1.

bcrypt doesn't work like that. The outline is:

    work * costfactor
    finish

The finish step is irreversible, so you can't unwind it and add more work later. In practice though, even low cost factors for bcrypt are tons more work than MD5 or SHA. It's not a big deal.

He didn't say "unwind it". He said "on top of it".

  bcrypt( bcrypt( "foo", c1 ), c2 )

I think what he means by run C2 on top of C1 is something like this. Let b(k,w) mean bcrypt with work factor w on input k.

So, initially, you are storing b(pass,C1). Running C2 on top of C1 would mean replacing that with b(b(pass,C1),C2).

Later, when you want even more work, another layer could be added: b(b(b(pass,C1),C2),C3) and so on.

ugh, no thank you.

Dear down voters, parent is accurate (except possibly for saying "big").

That's just not true. To oversimplify a bit, let's say BCrypt is a function b(data, cost) that returns a hash.

Right now, I have b(password, c1) = hash_a stored in my database. To increase the cost to c1+c2, I just replace that with b(hash_a, c2) = hash_b in my database. To verify a user's login, I just compute b(b(password, c1), c2) and compare it to the hash_b I have stored.

Am I missing anything?

Yes. That's not how bcrypt really works.

I've read the usenix paper, and I'm reasonably sure I'm right. Care to elaborate on what I'm mistaken about? I (and a few other people I've talked to about schemes isomorphic to this about) may learn something new :-D

OK, so you can chain bcrypt in theory, but if you look at the API and how it stores rounds/salt, I don't think you'll enjoy implementing the code to do so. You can't just store hash_b, you'll need to store hash_a too. It's not worth it.

Basically, the assumption that bcrypt is just a function that returns a hash oversimplifies the detail of how salt is stored in practice.

I wrote a comment to the effect of "you can just chain bcrypt" but deleted it because I didn't want to wade into exactly this tarpit. If a client asked me how to upgrade the cost of their password hashes, I'd probably tell them to validate incoming plaintext and then create a fresh hash.

I agree: this is not a big deal in practice. bcrypt with a cost factor of 10 is so much slower than SHA1 that this is just not going to be an issue.

Or you can wait until the user signs in again and create hash_b at login with the plaintext password after you validate it against hash_a. I believe that is how the bcrypt documentation recommends you do it.

That is much less preferable though.

I would say that, given how 'cheap', you could slowly increment the cost-factor over time. You could also ask a user to replace their password after a certain time period, or after the cost factor gets too 'low' - you can even allow the same password to be entered. Having a different cost-factor for every password is a bit of a logistical nightmare though.

The fact is that any significantly high cost factor is much better than md5, sha1 or any other normal hashing function, and should prevent password cracking for 5-10 years. This is a reasonable period of time.

Codahale's article is misleading with salts. Bcrypt can't also protect against brute-forcing or dictionary attacks. Please don't spread that link as an example of good password storage security.

Edit: Since I can't reply to poster. I don't see bcrypt using a unique salt for each password. It's the equivalent of exchanging a SHA256 + Same Salt for Bcyrpt + Built-in-Salt.

Does bcrypt use a unique salt per account?

No; you're incorrect.

You can find the answers to your bcrypt questions at the Usenix paper which is the first link in the article you're advising people not to read.

I did, it uses a preset list of salts at the time. That doesn't seem unique per account salting raising the possibility of collisions to me.

bcrypt uses 128 bit salts. Every bcrypt library I've seen will generate the salt for you.

    [8:48pm:~] RIDGELAND:tqbf [1:45]% irb -rrubygems -rbcrypt
    >> BCrypt::Password.create("test password")
    => "$2a$10$KyxzQ6ZlAAYdLWwpgCbyjuqo53.LzPbsaSK2BiTnzpYEpRVZOHAAy"
    >> BCrypt::Password.create("test password")
    => "$2a$10$d0uUieyk0NWsU7E9CmQNwOsveyznwKwplphsF73yILdEyStmoUGgG"

Notice how they aren't the same hash? And, how I didn't have to go mine pink salts from the Himalayas?

By spreading the notion that there is something wrong with Coda's article when you really aren't familiar with bcrypt, you're doing people a disservice. They are going to go use SHA1 with a big random salt instead, because they've heard of SHA1 before and it therefore sounds more secure. And they will thus be terribly vulnerable to brute-force attacks.

A preset list of salts would still show a different hash for 2 consecutive bcrypt executions. Your example proves nothing.

I'm not saying you're wrong. I'm saying you didn't demonstrate proof, so you shouldn't act like you did.

I'm extremely interested why bcrypt is much more secure than SHA1 + extremely long hash, so perhaps you could shed some photons on that?

Also, in order for bcrypt to generate a unique salt on two different computers, it needs a unique source of randomness. Obviously seeding by "current time" is insufficient, as this would generate the same salt for two different computers at the same time. So what does it use? Mac address of network card + current time?

I don't need to prove that bcrypt has a "preset list of salts". Read the paper. Or even just Coda's summary of the paper. What an extremely silly objection to raise. Why would any cryptosystem embed a preset list of nonces?

How frustrating to have to argue about a system with someone who clearly hasn't done any reading on it at all. It's a Usenix paper. It's not a EUROCRYPT paper full of math. It was written by systems programmers, then from the OpenBSD project. You think the OpenBSD programmers devised a password scheme with a "preset list of nonces"?

"MAC address of the network card plus the current time"? To get a random number?

> Mac address of network card + current time?

you're trolling, right?

If not, begin your journey to enlightenment at http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html (15 years old now!), http://www.schneier.com/paper-prngs.pdf and the kernel source for your favourite OS' /dev/random (the OpenBSD one is pretty well commented)

Read the bcrypt paper: http://www.usenix.org/events/usenix99/provos/provos_html/ind...

The algorithm requires (cost, salt, password) as input, and the output hash includes the cost and salt. When generating a hash for a new password you should of course be choosing this salt randomly, and when checking a password be using the stored cost and salt.

In particular see the Implementation section:

An important requirement of any bcrypt implementation is that it exploit the full 128-bit salt space. OpenBSD generates the 128-bit bcrypt salt from an arcfour key stream, seeded with random data the kernel collects from device timings.

Ah. The original article was saying that it was all built-in (salt), only the password is the input. I misread that.

Reply on news.ycombinator.com