Hacker News new | past | comments | ask | show | jobs | submit login
Can bcrypt’s computational expense be reduced on the server side? (hashcollisions.com)
2 points by domador on June 28, 2011 | hide | past | favorite | 4 comments



(as I commented on the site)

    > Account Log-in
    > 6 The browser submits Turing’s username and bcrypted hash to SecureR.
    > 7 SecureR directly compares the hash submitted by Turing with the one stored in his user record. If they match, account access is granted.
So, suppose I’ve stolen the password database of SecureR. Unfortunately, I can’t recover the password of the user. However, I only need the hash of it (which is stored in the database) to log in, so I don’t need to recover the password anyway.

This does protect against exposing the user’s password, so it’s not a total waste. An additional wrinkle:

You could store the hash of the bcrypted password in the database. The browser would submit the bcrypted password in 6, and the server would hash it in 7 before checking it. This makes recovering the password infeasible but logging in is cheap for the server, and the input to the hash function has high entropy, so it will still be hard to crack. At this point though, you need a security expert to evaluate it.


Robin,

Yes, if an attacker obtained the password database, they could use the password hashes to log in with any particular user's account. They wouldn't need to know that user's plaintext password.

Like you, I'd also thought about storing a second-level hash (a hash of the bcrypt hash). However, I didn't mention it because I don't currently understand the complexity of hash functions well enough. There are at least two issues that come to mind regarding the complexity of the second-level hash function:

1) If we used MD5 or SHA-1, would this cause the same problem Coda Hale warned against? A bcrypt hash would likely be longer and more complex than a typical user-defined 6 character password. Could a cracker feasibly produce the MD5 hashes for all the strings as long as a bcrypt hash? (I don't know how much slower MD5 gets with each additional input character, or how much slower it gets to produce MD5 hashes for all the strings of a given length.)

2) If we used bcrypt itself as a 2nd-level hash, wouldn't that cause the same problem I was trying to avoid (running bcrypt at log-in time)? Maybe this 2nd-level bcrypt hash could be configured to be less computationally expensive that the 1st-level hash (the one used on a user's plaintext password). Thus it'd be moderately inexpensive to verify a user's password, but more expensive to crack it (since the input string the password cracker is trying to find is a bcrypt hash, not a traditional, weak user-selected password). Like you said, I need a security expert (or several) to look into this.

Thank you for your feedback.


Not in this way. The bcrypted hash effectively becomes your plain text password, nulling the purpose of a hash in the first place.


lzm,

You're absolutely right! The bcrypted hash effectively become a plaintext password. This is obviously a problem. However, it also creates an interesting opportunity...

SecureR could be designed so that every so often it rehashes a user's plaintext password and creates a new bcrypt hash. This could happen every month, every week, every N successful user log-ins, etc. Now, users hate having to frequently change their passwords (and rightly so). However, with this system, each user could keep the same plaintext password, and the system could transparently generate a new bcrypt hash for it periodically. By cycling through bcrypt hashes, attackers would have a narrower window in which to steal a password table and use the stolen hashes. Maybe a 2nd-level hash could be used (as discussed in my reply to Robin_Message), so that the 1st-level hashes aren't completely exposed, and attackers need to not only steal a database but also crack it (all within a short time frame).

Unfortunately, after this adjustment, bcrypt wouldn't be invoked only on account-creation or password-resets. The bcrypt bill would be higher than in my original proposal. However, at least bcrypt wouldn't be invoked every single time a user logs in.

Maybe the cost of bcrypt can't be fully shifted from the log-in system to the account-creation and password-reset systems. Maybe it needs to be paid somewhere in between both areas, where you get as much secure encryption for passwords and denial-of-service protection as possible. (Both goals seem to be in conflict with each other.)

Ah, tradeoffs!




Applications are open for YC Winter 2022

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: