Bcrypt - symmetric encryption

Stackoverflow is right: the last two bits are just padding, and not at all unpredictable. AES was not designed to work with a partially-known key, so I wouldn't recommend it.

Unlike bcrypt, PBKDF2 was explicitly designed for this purpose, so I'd recommend using that if you do go this route. It'll also get you a strong 256-bit key (in the correct variant). (If you really want to use bcrypt, just truncate at 128 bits and use AES-128, which is good enough. Really.)

Whether using bcrypt or PBKDF2, you'll want to use a salt, which should be stored in the database. Whether using bcrypt or PBKDF2, some users will choose pitifully weak passwords and allow their data to be decrypted (no password hash can save you if you pick "password" or "iloveyou"). You can more-or-less solve this by integrating e.g. http://www.openwall.com/passwdqc/.

All that said, I'm not sure this is a good idea:

- you expose yourself to DDoS by repeated logins, fixable only by setting the work factor for bcrypt/PBKDF2 dangerously low (100 POST "/create_new_account.php" requests per second is not much);

- if your front-end machines are compromised, the attacker can gather passwords from legitimate logins, so you still need to secure your front-end machines;

- encrypting everything that could be useful to an attacker means that you can only use your RDBMS as a networked hash table;

- crypto is hard, and easy to get subtly wrong.

Then again, implementing this would most likely increase your security quite a bit. Just don't rely on it.

[Sorry, I haven't forgotten about this message, but things are really hectic right now. I'll try to get to it tomorrow.]

Okay, here are my thoughts. The standard disclaimer (I'm actually a mathematician-cryptographer, I just play a security guy on the internet) applies: don't rely too much on me. I hear tptacek does security evaluations, for a fair price. ;-)

Here are some comparisons (because I don't have numbers for cracking speed either):

Block ciphers: 80-bit keys seem to be uncrackable for now (although pretty much everyone recommends 128-bit keys). You're a work factor of 2^80 / 2^64 = 2^16 away from that level of security, but PBKDF2 should be able to supply that (against every attack I can think of, at least). As a very rough guide, my laptop does ~3 million AES (which is not a 80-bit cipher, but should be of comparable speed) invocations on a small buffer per core per second, according to "openssl speed", so you'd aim for 3 million/2^16 ~= 50 crypts per second.

Passwords: passwords with 64 bits of actual entropy (e.g. 12 truly random uppercare/lowercase characters) are extremely rare - the typical entropy of a human-selected password seems to be ~18 bits, which causes security people lots of trouble. OpenBSD's bcrypt takes, again on my laptop and this time timed with a very imprecise 'for i in `jot 1000 0 0`; do encrypt -b6 foo >/dev/null; done', about 7 seconds per 1000 crypts (single-core). (Note that OpenBSD's value hasn't been increased for a long time.) So aiming for 100 crypts per second gets you about the same security as a very good password with a standard login procedure, and 10^5 crypts per second (10 milliseconds per crypt, equivalent to a password with ~54 bits of entropy and a standard login procedure) is still far better than typical for password-based systems.

Something like 50-200 crypts/second probably does allow DDoS attacks via repeated (attempted) logins. On one hand, I wouldn't worry too much: articles like http://www.itbusiness.ca/it/client/en/home/News.asp?id=54907 suggest that you could knock even a sizable dedicated server offline for a week or so on a budget of a thousand bucks, which is probably a more realistic threat (if only because it doesn't require much sophistication). On the other hand, as long as the attacker doesn't gain direct database access but has to go through your front ends, password-based systems seem to mostly work in the real world - rate-limiting helps a lot. (Of course, it also helps that the average Facebook account just isn't very valuable.)

If you do want security from brute-force attacks by attackers who do get access to your database, and if you are unwilling to go to 128-bit keys (which basically solves the issue), consider 80-bit keys: it's three more BASE64 characters, but 80-bit keys alone seem to be sufficient for now (NIST recommends phasing them out in 2015 at the latest, but I know of no real attacks, and there are almost certainly juicier targets). Adding a variable work factor via PBKDF2 makes sense, if only to be able to scale up later without too much hassle. The above 2^16 would get you security sort-of-equivalent to 96-bit keys; something like 2^4 should be essentially instant.

In the end, though, this is a lot of complicated code that you'll have to write (and tptacek would tell you not to do it), and even if you get it right "this guy implemented some nonstandard crypto" will set off some alarm bells.

I think the industry-standard solution is to hand out RSA keyfobs (or the YubiKey, which may end up cheaper once you consider RSA's server-side licensing); do note that RSA recently got completely hacked and handled it very poorly (Google has plenty of details), and that the YubiKey RFID (specifically, the other models are fine) includes a totally broken MIFARE Classic chip (famously used on the "OV-kaart" here in the Netherlands.) Truly paranoid customers may have epoxy'd all their USB ports shut, which would rule out the YubiKey. I don't see how to handle encrypted data with either of these solutions. (Note: I have no idea how well the YubiKey stands up to physical attacks. I'm not sure you care, but...)