http://codahale.com/how-to-safely-store-a-password/
It's really not more complicated than this. You can use scrypt instead of bcrypt if that makes you happy. The secret crypto keys in separate storage locations stuff is silly. Get the basics right.
A properly bcrypt'd password table is functionally useless in the hands of a non nation-state. Yeah, it's not something you'd prefer to have a BadGuy(TM) get, but other than embarrassment, it's not a big deal.
Here's my bcrypt with salt. Please, waste your time trying to crack this.
"$2a$19$xZrwzkut/fj2gToExgw8qevT9DtevnuKLEVj.kNiSMclzfFqQq9z."
Shame on you, Thomas! I thought you were a professional!
[1] Based on a remarkably unscientific test I just ran on an Ubuntu 12.04 VM on my laptop. 87.8 seconds.
That said, use bcrypt.
So, if say your backups are compromised and someone has all the user names and passwords they still need the salts before they can login to your service.
Edit: I am honestly surprised how much push-back people are giving this without saying why they actually disagree.
However, to quote from that post: "The author is correct assuming the attacker has direct access to your password store. This is a big assumption - most organizations go through great lengths to ensure access to say, databases, is levels of security 'deep' beyond just a web login form. Anyway, assuming that this might ever happen to you, how can you address the issue?"
Don't think for a second that certain government agencies can't brute force a BCrypt-based password hash, especially given they will know the cost factor and salt. If the hash is encrypted, and then chunked, if an attacker doesn't have the constituent encrypted chunks and/or the encryption key _for a valid time frame_, the possibility of a brute force attack with modern computing power is almost impossible.
While you may not care about such concerns, some of Stormpath's government agency customers do, and so we provide these additional safety measures. That an average website can benefit from them is icing on the cake.
It seems like some of the finer points of your concerns aren't being covered in this thread (e.g. # of iterations, if sufficiently high, will probably address your GPU concerns). Unfortunately for me, I can't read Hacker News all day and must move on, but if you'd like, definitely give us a call at Stormpath and we'd be quite happy to geek out and talk through the all of the details. (And I apologize if any of this came across as negative - no coffee today I guess).
This reads an awful lot like "If the attacker has not actually compromised the gateway." After all, the gateway needs to either be able to encrypt the password or decrypt the hash to do its job. That means the gateway needs either the key, or access to an oracle that has the key. Either way, you're compromised.
The data sharding has some merit, if only because it's more difficult to simultaneously steal systems from multiple datacenters. I suppose at some level that becomes a concern, but that's roughly the level where you start hiring people with guns to protect your computers.
I have no doubt that government agencies have much more powerful intelligence than people realize. But knowing the salt has no connection to their ability to brute-force; it only affects their ability to use rainbow tables.
(All it does is prevent them from matching up passwords by their hashed values, so for example, if one password is cracked, it protects everyone else who is using the same password.)
But it doesn't provide any protection against brute forcing. Nothing can, short of making the hash function slower (or the password domain larger).