Creating a Private Key using Human Intervention

Question

In a hypothetical system, lets say that a design requirement is that people who snoop around the database of a web application (sysadmin gone rogue, or what have you), do not have access to the plain text of private messages between users. An encrypted version of the text is stored instead.

The easy way to do this is to use a public-key/private-key encryption scheme. However it's (really) ineffective to store the private key in the system, or in the users browser given a strong-willed attacker. This leaves human intervention for generation.

Short of using a java-applet (or fancy HTML5/Javascript), it's hard to provide an instance for a human to provide random input to generate the private key, and there's still the issue of storing it. There's also a problem requiring humans to remember a 16 character random password using case sensitive alphanumerics and symbols. Private key dongles that companies tend to use are also out of the question.

So, the question is: How do I take a potentially insecure password and morph it into a secure private key? Is this even possible?

My ideas tend to float towards that it's not really possible until a user uses a decidedly secure passphrase (16+ characters, case sensitive with numbers), due to ease of brute-forcing these days. Also a problem would be the lack of a secure-enough cipher that uses it's own input to generate a key for it to use. Again, stemming from the problem with storing the key that is used in the generation.

Also, let's assume that proper techniques are being used in all other places of the system (SSL, up-to-date encryption algos, etc.)

Answer 1

Trying to write password resistance to brute force attacks as an equation: complexity * transformation cost = resistance. Your limiting bound on transformation cost is how long you want to work to verify (or generate a key from) a password each time it is valid. Poor passwords are hard to brute force if the derivation function takes a year to run, but that's also hard to work with as a legitimate case.

The "new traditional" method of generating a key from a password is to run it through PBKDF2. Bcrypt and scrypt are two "stronger" options. When choosing the number of iterations, benchmark and crank that thing up as high as you feel comfortable with based on predicted load. Too low and it's easy to crack. Too high and you'll denial-of-service yourself to death with legitimate operations. The basic litmus is "how many login attempts must I be able to handle per second?" Remember that unlike with password hashing, you cannot increase iterations at a later point in time (unless you re-encrypt everything -- you probably don't want to do that).

Store a random salt with your encrypted data (one for each password / key used) and use that corresponding salt with the password. That will ensure that each password must be individually attacked instead of the whole group at once.