Can bcrypt’s computational expense be reduced on the server side?

(Caution: Amateur security research ahead.  Using it in a live system is not recommendable.)

I recently read “How to Safely Store a Password”, an article by Coda Hale. For years I’ve thought that salting and hashing passwords with MD5 or SHA-1 prior to storage was sufficient to thwart password-cracking efforts (in cases where the user-account database table is stolen or publicly divulged). Apparently, this approach is not much better than simply storing plaintext passwords (a practice widely scoffed at). It was fascinating to find out about a better approach, that of using bcrypt instead of ordinary hash functions. Unfortunately, it seems to me that bcrypt creates a new problem even as it solves an old one…

The New Problem

The use of bcrypt turns password-cracking into a computationally-prohibitive task for attackers. However, bcrypt also hurts defenders, for whom password-hash generation or verification is now much more expensive than with ordinary hash functions. A popular online service having thousands of users might need to acquire additional processing power simply to process user log-ins. Moreover, by using bcrypt a service would become more vulnerable to denial-of-service attacks. Attackers could tie up its servers’ CPUs through numerous, automated log-in attempts. (These would make the servers call bcrypt repeatedly, once for each of the many log-in requests.) Addressing this threat would seem to require problematic tradeoffs between security, cost and convenience.

Could there be a way of lowering a service’s computational bill while retaining bcrypt’s advantages? This article presents a system which might accomplish this. I haven’t heard of this approach and would like to know if I’m on to something (or if others have already devised equivalent systems). Be forewarned, I am not a computer-security expert. (Thank you for reading this article anyway.)

A Potential Solution

The following protocol attempts to reduce the frequency with which bcrypt is called by an online server. It ensures that clients also pay for the cost of using bcrypt. (The server still has to pay, but the client now has to “split” the computational bill with it. This could reduce the appeal and effectiveness of brute-force or dictionary attacks on live systems.) This protocol redesigns the account-creation, account-log-in, and password-reset processes for an online service.

Account Creation

  1. Joe Turing, a user (or a bot, perhaps), visits the account-creation page for SecureR, a hypothetical (yet surprisingly-popular) online service.
  2. Turing types in his desired username and password and submits them (securely) to SecureR.
  3. The SecureR server creates a bcrypted hash from the password, using a random salt value and the cost parameter currently mandated by SecureR’s security policy.
  4. The username, password, salt, cost, and bcrypted hash are stored in a record in SecureR’s user-account table. The record also includes at least two verification fields. One indicates whether the password hash has been verified (successfully computed by the client). The other indicates whether the account as a whole has been verified. Both fields are initially set to “false”.
  5. SecureR sends the salt and cost parameters used to bcrypt Turing’s password back to Turing.
  6. Turing (that is, his web browser) computes the bcrypt hash corresponding to his password and submits it to SecureR.
  7. SecureR compares Turing’s hash with the hash previously computed by SecureR itself. If the two hashes match, the password-hash-verification field is set to “true”.
  8. Once other essential checks (such as e-mail-address verification) have been successfully performed the account-verification field is to “true”. Turing’s account is now fully verified and active, and he can start using SecureR’s services. (For now I won’t suggest when and where additional verification steps should take place, since bcrypt is my focus here.)

Account Log-in

  1. Turing types his username and password into the SecureR log-in page.
  2. Turing’s browser sends his username to SecureR.
  3. SecureR looks up the salt and cost parameters contained in Turing’s user-account record.
  4. SecureR sends the salt and cost values to Turing’s browser.
  5. The browser uses these parameters and Turing’s typed-in password to generate the bcrypt hash for Turing’s password.
  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.

Password Reset

  1. Turing types his username into SecureR’s password reset page and clicks the Submit button.
  2. SecureR sends a verification link to Turing’s e-mail address. (This link is to verify that Turing himself initiated the reset process. This password-reset system never generates nor sends temporary passwords to the service’s users.)
  3. Turing checks his e-mail, and opens up the link with his web browser.
  4. The page brought up by the browser has a password field, into which Turing enters his new password and clicks on a Submit button.
  5. The password is hashed and verified using a process analogous to steps 3 through 8 in the account-creation process.

Observations

According to this protocol, SecureR’s server only runs bcrypt when an account is created or when a password is reset. During log-in attempts, it is the client (Turing’s browser) and not the server which runs bcrypt. The server performs a computationally-inexpensive direct comparison between the client-submitted hash and the hash stored in its database. Thus the server avoids paying the bcrypt bill when processing a log-in request. (In theory, the client could also avoid calling bcrypt during log-ins. The bcrypt hash could be stored by the client after generating it during the account-creation phase. The client wouldn’t necessarily have to recompute the hash each time the user logs in. In practice, it’d be easier to design the client-side code so that it recomputes the bcrypt hash based on the user’s plaintext password, rather than dealing with hash storage and retrieval. The bcrypt-induced client-side log-in delay is tolerable to each individual user anyway.)

Relocating bcrypt invocations from a frequent process (account log-in) to other, less frequent processes (account-creation and password-resets) reduces the risk of a successful DoS attack. It doesn’t eliminate the risk completely, though. The account-creation and password-reset processes are the new weak spots, and must be hardened. This is why the password-reset process is more complex (and mildly annoying to legitimate users) under this protocol. Additional security methods (such as CAPTCHAs and rate-limiting) could also help harden the system against attack.

A Request for Feedback

My proposed protocol omits certain security-related details which would be important in a production system. I’ve also omitted some tweaks which could further improve the protocol’s security. However, I’d first like to make sure that this protocol is essentially sound. Please let me know if you find any logic errors or problematic side-effects I’ve failed to account for. As I said before, I am not a computer-security professional, and would appreciate assistance from others who are further along.

Share Button

5 Comments

  1. Robin Message
    Jun 28, 2011

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

  2. Andres
    Jun 28, 2011

    This article is being disccussed on Hacker News. Be sure to check it out:

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

  3. Andres
    Jun 28, 2011

    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.

  4. Skyborne
    Aug 13, 2012

    Hi there, found your article looking for attacks on bcrypt (found nothing yet) but in the wake of the Blizzard hack:

    If you have the luxury of running native code on the client, then I think the best way would be to run a modified SRP: instead of deriving x=sha1(salt + sha1(username + “:” + password)), insert your expensive hash of choice there. Such as x=sha256(pbkdf2(hmac_sha256, username + “:” + password, salt, iters)).

    Then the verifier (g^x % N stored on the server) is expensive for the attacker to try brute-forcing due to the cost of x, while it doesn’t consume server CPU at authentication time because it was precomputed. (Of course it consumes client CPU as it has to derive x from the given password.)

    But if you’re writing a web app instead, I don’t know of any reliable JS SRP implementations, and doing crypto in JS is rather slow. I can bcrypt with 09 work on a virtual machine in under 100 ms, while doing the same in JS is 300ms (chrome 22) to 1100ms (ie9) on the bare metal. If anyone shows up using IE8, ouch. And that doesn’t even get into mobile devices.

  5. Alan Chandler
    Mar 3, 2013

    I came across this web site whilst researching using bcrypt for a project I am involved with. I was going to comment that getting the client to do the hashing effectively means that the hash is the password, and you’ve got that stored in plaintext in your database – not so secure. But I see others got there before me.

    But, your main thought, make the client pay something to make use of the servers bcrypt function made me think of an issue I was pondering a couple of years ago – how do you make a javascript based chat client talk across the open internet and ensure privacy. Unless the key is generated in the client, it will be seen when the source of the client is loaded on the initial web page.

    I then researched and finally implemented something in which I got the client to compute an Asymmetric Key Pair, pass the Public Key to the server, who then encrypted a des key with it and passed it back to the client, who then encrypted his messages with it. The REAL problem in all of this was getting the client (browser) to computer the key pair – it was expensive and needed a special implementation technique (see http://www.chandlerfamily.org.uk/2010/06/the-making-of-mbchat-v3-part-1-introducing-non-structured-programming/)

    What if you implement something like this

    ACCOUNT CREATION
    1) Client calculates Asymmetric key pair and sends public key to server
    2) Server stores public key against that client’s account and generates a random des key which it encypts with the public key of the client
    3) Client decrypts des key with his private key of the pair and uses the des key to symetrically encrypt password to go back to server for storage
    4) Server bcrypts this password and adds it to the database.

    USER LOGIN
    1) Client creates a (MUST BE DIFFERENT) key pair and sends public key to server along with username
    2) Server checks public key received IS NOT THE SAME AS BEFORE, or TOO MANY ATTEMPTS are being made too fast -it marks that it will ultimately reject the password
    3) If the key is different, this gets stored, along with time of last access
    4) Server generates random des key, encrypts with public key (even a repeated one) and sends back to client
    5)Client decrypts with his private key and then encrypts his password with des key and sends back to server.
    6) if server finds previous public key was not a fresh one, or too many requests are coming, it says the passwords don’t compare without even computing the bcrypt.
    7) Otherwise it does the bcrypt and compare and returns the result of that comparison.

Submit a Comment

Your email address will not be published. Required fields are marked *