Public key cryptography with user-chosen passwords?

Question

The whole point is designing a simple system where users are able to send encrypted messages between them (with support from a server).

In this scenario, clients have no local storage, so I'm forced to use passwords that users will be able to choose, remember and type when needed. (I know this weakens the whole system but this is a hard requirement)

Another requirement is that the server cannot store cleartext private keys or any other data which can be used to decrypt messages (eg: only the user can read encrypted messages, server admins should not be able to).

My approach would be to generate an asymmetric keypair on the client, publish public key on the server along with an encrypted copy of the private key (encrypted with the user password). Users can then send encrypted messages to other users, using the recipient published public key; when a user needs to decrypt a message, his (encrypted) private key is fetched on the client from the server, decrypted with the password provided by the user and then used to decrypt messages.

Does this make any sense? Is there any flaw in this system design? (apart from the weakness derived from users choosing short or bad passwords) Is this approach already used in similar scenarios?

Thank you :)

Answer 1

If I understand correctly, you want to create a system where two users can initiate private communication through a server that they do not trust.

This won't work.

In the scenario you lay out, the server can generate its own key pair, and publish its public key in place of the users'. When a user encrypts a message, intending it for their partner, they can't detect that the server has substituted its public key. The server decrypts the message, presents it to the server admins, and re-encrypts it (or some new message that they fabricated) with the real partner public key, and forwards it to the destination.

What's missing here is a certificate authority. This is a trusted third party that digitally signs a binding between a public key and a user name. This binding is called a certificate. This way, when the server presents a public key to a client to use for encryption, the client can use the CA's public key to verify the certificate, and be assured that the public key they are about to encrypt with belongs to the intended recipient, and not an attacker.

The users have to trust the CA, which might be more palatable than trusting the server administrators. But, there must also be a tamper-proof way to store the CA certificate. In practice, this is often done using a password-based MAC (message authentication code). Or, the CA could be digitally signed with the user's private key (never seen this done, but it would work). But the tricky part would be getting the CA certificate from a trusted source, bypassing the untrustworthy server.

As far as encrypting the private key with the password, that is done very often, and is as safe as the password you choose.

Alternatively, if the users can share a secret with each other out-of-band, you don't need public key encryption. The client could encrypt the shared secret with a user-selected password, and store the cipher text on the server.

Answer 2

As described, the scheme seems reasonable in that it should allow someone to send another person a message that only the recipient can read. There are some items that come to mind that you may have already thought about but left out for brevity:

• When encrypting the private key, use something like PBKDF2 with salt and some fairly large number it iterations.
• This is probably implied, but rather than encrypt with the public key, it probably makes sense to generate a random key (e.g., 32-bytes of random data if using, for example, AES-256). Encrypt the message with that key, encrypt the key with the public key, and send both pieces.
• As described, there is no identification of the sender. It allows purely anonymous messages to be sent. This might be intended, but if not, then some kind of identification/authentication would be necessary.
• Somewhat similar to the previous entry, no message authentication is described. The attacker could change the encrypted message and the recipient would not be able to tell that it was changed. Although, if it is a text message, it would be pretty clear that it had been modified, because it would be just garbled text. There are some types of data, though, that might not be so easy to tell if it had been modified.

Answer 3

This sounds something like what hushmail did. However, there was a major problem in that, since they had the private key of the users (encrypted) they just had to push down a hacked java applet which would transmit the user's password to the server (which they did).

A much better solution is to avoid having that private key on the server at all. With the requirement of no local storage, that's out.

Why not use symmetric encryption via a pre-shared password? It can be done without storage on the client side. I believe this is what @erickson was saying in his last paragraph.

Answer 4

The major problem is that if the decryption code is downloaded from the server, one (either server admin or a hacker that has got to the server) can replace this code. The user on the client side should trust the server, but he has no way to verify the server in order to trust it.