I don't understand why there is so much effort placed on storing passwords. We already know what to do with passwords from the perspective of the server: discard them as soon as possible!
The password should be salted and hashed immediately, and it should never be stored in plaintext. So let's not store them at all: let the user remember the risky password, and encrypt it as soon as possible. It's a validated methodology, and it removes many/most of the trust issues of the user/server relationship: I don't care if the server fails to salt my password if it's already encrypted.
Now take this to the next step. The user-side "passwords" can be pretty weak, since they need to be memorable but not high-entropy. We don't want to re-use the same "password" everywhere (different sites/services), since that's a risk, but we can come up with a weak per-site salt that's easy to remember. Combine that with a relatively weak password and we have a winner
Use-everywhere password: invsqrt
Site: slashdot.org. "Salt": modmadness. Full password: invsqrtmodmadness
hashlib.sha256(getpass.getpass()).hexdigest()[::2][:16]
Password sent to server: "dee4ea048518f588"
Use-everywhere password: invsqrt
Site: stackexchange.com. "Salt": xyproblem. Full password: invsqrtxyproblem
hashlib.sha256(getpass.getpass()).hexdigest()[::2][:16]
Password sent to server: "be6065c67f055583"
Yes, I know it's just a hash, but this is a simple example. There's some loss of strength from key vs hash lengths, re-using "passwords" etc, and I've thrown in some complication, but I think the general idea is sound. The most important fact is that insecure, memorable, secret information never leaves my brain. Ok, in practice it does: I enter it onto an offline encryption device, but it never goes anywhere else.
- There is no private key to lose.
- I don't have to store private information.
- The public-side "passwords" are high-entropy and pseudo-random.
- The user-side "passwords" are highly memorable.
- An offline encryption device adds security, but it isn't necessary: in an emergency I can generate hashes nearly anywhere, since I carry my secure passphrases around with my in my brain.
You can stack additional levels of complication to make it more robust, but even the crudest implementation put you in the top 0.01% of hardest-to-crack passwords. For example, your encryption fob can contain a private key: smash the fob and you have securely destroyed the ability to re-create passwords. It also would make the outgoing passwords much more secure.