News for hackers. Stuff that matters.
Re:Cheap GPUs rendering strong passwords useless? by tzs on Sunday June 05, 2011 @10:16PM (#2623446)
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.
Re:Cheap GPUs rendering strong passwords useless? by smanek on Sunday June 05, 2011 @11:27PM (#2623573)
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?

Re:Cheap GPUs rendering strong passwords useless? by zcid on Monday June 06, 2011 @01:20AM (#2623781)
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.
Re:Cheap GPUs rendering strong passwords useless? by VMG on Monday June 06, 2011 @02:24AM (#2623879)
That is much less preferable though.
Re:Cheap GPUs rendering strong passwords useless? by tedunangst on Monday June 06, 2011 @12:00AM (#2623653)
Yes. That's not how bcrypt really works.
Re:Cheap GPUs rendering strong passwords useless? by smanek on Monday June 06, 2011 @12:44AM (#2623718)
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
Re:Cheap GPUs rendering strong passwords useless? by tedunangst on Monday June 06, 2011 @12:59AM (#2623740)
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.

Re:Cheap GPUs rendering strong passwords useless? by tptacek on Monday June 06, 2011 @01:11AM (#2623763)
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.

Re:Cheap GPUs rendering strong passwords useless? by bradleyland on Sunday June 05, 2011 @10:45PM (#2623488)
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.

Re:Cheap GPUs rendering strong passwords useless? by daeken on Sunday June 05, 2011 @10:52PM (#2623506)
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.
Re:Cheap GPUs rendering strong passwords useless? by RyanMcGreal on Sunday June 05, 2011 @10:52PM (#2623503)
Unless you run C2 on top of C1.
Re:Cheap GPUs rendering strong passwords useless? by tedunangst on Sunday June 05, 2011 @11:09PM (#2623543)
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.
Re:Cheap GPUs rendering strong passwords useless? by tzs on Sunday June 05, 2011 @11:29PM (#2623575)
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.

Re:Cheap GPUs rendering strong passwords useless? by tedunangst on Monday June 06, 2011 @12:01AM (#2623657)
ugh, no thank you.
Re:Cheap GPUs rendering strong passwords useless? by palish on Sunday June 05, 2011 @11:26PM (#2623572)
He didn't say "unwind it". He said "on top of it".

  bcrypt( bcrypt( "foo", c1 ), c2 )
Re:Cheap GPUs rendering strong passwords useless? by keeperofdakeys on Monday June 06, 2011 @06:06AM (#2624225)
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.

Re:Cheap GPUs rendering strong passwords useless? by tedunangst on Sunday June 05, 2011 @11:11PM (#2623546)
Dear down voters, parent is accurate (except possibly for saying "big").