How secure is a system that retrieves encrypted private keys from a public database?

Question

The system in question is one with multiple users. Each user has a password associated with their account, and each user owns several public-private keypairs. A user's private keys are encrypted using the user's password, and stored in a publicly accessible database. A system like this would allow users to retrieve their public-private keypairs from any machine, and decrypt the private key using their password.

Assuming that a strong encryption algorithm was being used to encrypt the private keys (perhaps Blowfish/Twofish), what sorts of attacks might this system be vulnerable to?

PS: There are two ways I can think to encrypt the user's private keys.

• Each private key could be encrypted and stored individually
• The private keys could be aggregated into one file which is then encrypted and stored

In the first option, users would be able to retrieve keys individually, leaving the other keys encrypted and not risking their exposure. However this might lead to an association attack on the user's password, as there would be multiple cyphertexts all encrypted using the same key (the password). Aggregation of the private keys before encryption might help avoid this, but then the user would have to retrieve the entire file and decrypt all of their keys at once, potentially exposing all their secrets. Which of these two methods (or maybe there are more) would be more secure?

EDIT
So far, the answers to this question have mentioned deriving keys from the password and storing secret, randomly generated salts to be provided to the user upon login. These are great ideas that slipped my mind. However, what I failed to clarify was that the system database has all the data public with no stored, hidden fields. With such a system, it might be possible to implement this as a distributed P2P network, and would nullify the threat of data breaches (nothing to steal since it's all public).

With this requirement, storing secrets is impossible, and we should assume any algorithm used to derive keys from a password is public as well, to avoid security through obscurity. Because the deriving algorithm is public, it wouldn't add any security (in theory) to the private key encryption as opposed to just using the password as the key.

Lets say every user averages ~100 private keys. How realistic is an association attack on these cyphertexts encrypted with the same key if TwoFish were being used? Is brute forcing still the easiest path?

What about every user owning ~1 million keys? How many keys (about) would it take to make some sort of association attack plausible? And is there any way that this system could be hardened, like by somehow increasing the password entropy?

Answer 1

A user's private keys are encrypted using the user's password, and stored in a publicly accessible database.

A publicly accessible database like this can be easily corrupted through an offline dictionary attack because passwords often have very low entropy. This can be improved (but still hackable) by adding salts (that are also stored in the public database). This post introduces how to use salts to protect passwords: Can you help me understand what a cryptographic “salt” is?

On the other hand, I don't think encrypting a client's private keys with different keys (derived from the same password) help here because an adversary can easily crack all the derived keys if it finds the correct password.

Answer 2

Seems like the first option is much better. And you don't need to use the same password on each - you could derive a key from the password and use a random salt for the derivation for each private key being encrypted. Or use a reasonable encryption algorithm that takes a nonce, make sure it really is a nonce, and you shouldn't need to worry about using the same password for multiple keys (unless you're talking many millions of keys per user.)