Most Efficient way of Encrypted Chat

Question

I'm creating a server where people can come and talk to each other. I'm mostly doing it for a fun project. I'm using RSA for encryption/decryption, so only the clients will know what's being said. I don't want the server to handle any decrypted text.

My question is, what's the most efficient way of doing this? From my understanding, I'm going to have to give everybody each other's public keys. And once a client says something, it's going to have to encrypt it to each person individually using their respective public key, isn't it? To me that seems extremely inefficient.

Is there a better way to do this?

Answer 1

Public key cryptography can, in this case, be used to facilitate setting up a secure channel in which to transmit a symmetric key. Once the secure channel has been set up, it is not necessary to continue to encrypt and decrypt using the public/private keys. Instead, generate a symmetric key and use that to encrypt the traffic. You only have to distribute the symmetric key once, and the traffic need only be encrypted with this key rather than with each public key. The main challenge is when or if the symmetric key needs to be regenerated, revoked, etc.

Answer 2

The most efficient way is to have client's exchange their RSA public keys and then generate random "session keys" to use for conversations with each other. This avoids multiple encryption and doesn't require the server to be able to decrypt the data.

So if Jack is going to talk to Jill and Seth, Jack generates a random encryption key to use to talk to Jill and Seth. Jack encrypts this key with Jill's public key and Seth's public key and sends the encrypted keys to Jill and Set. The server cannot decrypt them. Now Jill and Set know the key Jack will use. Jack can now encrypt the messages once with this key and have the server relay them to Jill and Seth. Jill and Seth can decrypt the data with the session key. The server can never decrypt the data.

This means clients will have to keep session key tables and generate new keys for any distinct combination of clients they may wish to talk to.

Be warned that with all of these schemes, unless you use certificates they are vulnerable to an attack where the server simply substitutes its own keys for the client's keys and decrypts and re-encrypts all traffic, unbeknownst to the clients.

Answer 3

Run a jabber server and tell them to use pidgin with OTR

Answer 4

Generally, asymmetrically encrypted chat handshaking starts out with exchanging public keys. Ideally you should have some mechanism for tying the key to the owner (think SSL certs and signatures) to prevent MITM attacks. Easiest to just use an existing system (such as SSL certs or PGP keys) to avoid reinventing the wheel. What signatures you decide to trust depends on what sort of trust model you're interested in maintaining. A good place to start is to determine exactly what constitutes a user's identity, and what type of access an attacker would have to have to steal that identity.

Then, of course, use RSA to encrypt ad-hoc session keys used for symmetric crypto like AES, Twofish, RC4, etc. The efficiency lies in the fact that you're only using RSA to establish the identity of the party you're communicating with, and then you immediately switch to something more efficient.

On the other hand
If you're talking about using RSA in a broadcast medium (think IRC rather than Jabber), then yes, this is terribly inefficient. Encryption is necessarily point-to-point, rather than point-to-multipoint. Each stream is individually encrypted. So the number of encrypted streams streams a given client produces is equal to the number of destinations that message is sent to. Each one set up independently of the others. This is precisely why systems like IRC do not encrypt end-to-end between different clients. The overhead would be just too much. At the very most, they encrypt client-to-server, allowing each user to have a single secure channel, with the server handling the message distribution.

That's not to say that what you're doing is impossible or ill-advised. If you want to build it, then go ahead.

Answer 5

How about switching from RSA to a variant of Diffie–Hellman key exchange? Choose a prime (p) and base (g) shared between all participants, and then each participant picks their own private key (a) and publishes a public key (A=G^a mod p) derived from it. Then to communicate with some other participant, they just raise the other user's public key to their own private key (mod p), and they'll get a shared secret that those two participants can use to encrypt (with some appropriate symmetric cipher) messages between them.

This still requires everybody to know everybody else's public keys, and that a message with multiple recipients be encrypted and sent separately for each recipient; but it allows you to skip the step where each pair of participants has to negotiate a shared session key.

p.s. this method does have some security limitations; for example, if a user's private key is ever exposed, all of their past messages are trivially decryptable.