41

My model is one where I have several clients which wish to speak with some (but not all) of the other clients.

All messages will be sent through a server.

Only the two clients communicating with each other should be able to know the message. So the server AND the other clients should not be able to work out what message was sent.

Communication between two clients may start and end several times a day.

Messages will be plaintext with potentially unlimited length, but likely to be much less, think SMS style messages.

Given these circumstances, how should I encrypt the messages? I don't mind writing extra code if it leads to better speed or efficiency.

I know the rough basics of how RSA and AES work but I can't figure out what is best.

When you generate a public/private key pair for RSA, is there any situation where you would need to generate a new pair? Or can one client have one public key and give the same key to anyone that wants to talk to him and only him be able to (ever) read the messages, but they store the public key for all future messages?

Or should I have a separate symmetric AES key for pair of clients and simply share that when contact is first initiated and use that forever. Again, is there any circumstance where this would need to be generated again?

How would I store the key(s) so they persist if client crashes/shutsdown/reboots?

Steffen Ullrich
  • 184,332
  • 29
  • 363
  • 424
Cheetah
  • 511
  • 1
  • 5
  • 3
  • 7
    RSA is a public-key encryption algorithm (asymmetric), while AES is a symmetric key algorithm. The two algorithms work very differently, and often a cryptosystem will use both algorithms. For example, a cryptosystem may use RSA to exchange keys securely, while use AES to encrypt the actual messages. –  Dec 17 '11 at 23:50
  • I am asking from an implementation point of view, the programming side of things...what algorithm should I program the encryption of messages, how do I program the storage of key(s). –  Dec 17 '11 at 23:54
  • @Ben, You may also wish to consider an active eavesdropper, where either the server, or another client, are pretending to be the recipient of the message. I do not know how likely this is with your model, but something to consider. In fact, the eavesdropper could then echo the message on to the real recipient, and then again, I do not know if the real recipient would detect the changed fingerprint of the sender. – 700 Software Jan 23 '12 at 18:30

5 Answers5

47

Neither, unless it's both. You're asking the wrong question. You should not be thinking about a cryptographic algorithm at this stage, but about a cryptographic protocol.

Cryptographic protocols are hard to design, and a frequent source of security bugs. You don't fully understand public-key cryptography, so you aren't ready to use it in your own cryptographic protocol.

At a high level, your model is amenable to public-key cryptography (e.g. RSA). Let every client have its own private key and publish its public key to the other client. A client's private key does not change over time, unless the client has been compromised. Symmetric cryptography (e.g. AES) would not scale well here because each pair of clients would need to have its own secret key.

Use existing software whenever possible. Implementing cryptographic protocols is almost as tricky as designing them. For a model where clients occasionally send messages to one another, email-style, a tool that would work well is GnuPG. (For bidirectional communications, use SSL/TLS.)

So: for day-to-day operation, to send a message, call gpg, encrypt with the public key of the recipient, and while you're at it sign with the private key of the sender. When receiving a message, check the signature against the purported sender's public key, and decrypt with the private key of the receiver. In other words, send with gpg --sign --encrypt -r NAME_OF_RECIPIENT and receive with gpg --verify followed by gpg --decrypt.

The remaining problem is that of key distribution. After a client has generated its key pair, it needs to inform the other clients about it and distribute it without allowing the public key to be intercepted and replaced in transit by an attacker. How to do this depends a lot of your precise scenario. Don't neglect the security of this part.

If, and only if, invoking GnuPG proves to be too slow, then consider using a lighter-weight, perhaps home-made implementation of a similar protocol (going from e-mail range overhead to SMS range overhead). Under the hood, GnuPG generates a symmetric key for each message, because public-key cryptography is expensive for large messages; the public key algorithm is only used to encrypt the symmetric key and to sign a digest of the file. You should follow this model. Using AES for symmetric encryption, SHA-256 as the digest algorithm and RSA as the public key algorithm is a good choice.

Gilles 'SO- stop being evil'
  • 50,912
  • 13
  • 120
  • 179
  • "and decrypt with the public key of the receiver. " shouldn't it be "and decrypt with the private key of the receiver. "? – Sudhanshu Mishra Feb 05 '16 at 00:23
  • @Gilles Great answer, very helpful thanks! Have a look at `The Double Ratchet Algorithm` with regards to using AES-256 and scaling well, if not already. – Kevin Crain Nov 27 '16 at 20:35
  • DH should be used with AES. RSA can be used alone, plain and simple. Digest algorithm is always needed anyway. – KeyC0de Mar 05 '18 at 06:04
20

As already said by In silico, RSA and AES serve two different purposes. AES is a fast algorithm, suited to encrypt a whole conversation. But it has a problem: how to decide which key to use between two parties without the other ones knowing it?

RSA can be the solution to this. If every participant has the public RSA key of every other participant, anyone can start an encrypted communication with anyone else (by using the other participant's public key) and decide on a secret AES key to use. Once the AES key is decided, the rest of the conversation can be encrypted using AES. To prove that to participant B that it's really A which wants to talk to him, a digital signature can be used.

What I described is, grosso modo, what the SSL handshake does when a browser connects with an SSL-enabled web server.

Koray Tugay
  • 105
  • 4
JB Nizet
  • 301
  • 1
  • 3
  • 1
    Hi, I'm just wondering...why can't the client's just converse with one another using only RSA since it is already being used to decide upon the key for AES? Is it because RSA is somehow not suitable for exchanging secret messages? Thanks. – Eric Jan 01 '17 at 01:11
  • 4
    The first reason is that RSA is much slower, the second is that it's limited in size. More details here: http://security.stackexchange.com/questions/33434/rsa-maximum-bytes-to-encrypt-comparison-to-aes-in-terms-of-security – JB Nizet Jan 01 '17 at 07:33
6

Don't take this the wrong way but...

I know the rough basics of how RSA and AES work but I can't figure out what is best.

If you only know the basics you might not be the right person solve this problem (yet). Security is one of those areas where you must be very particular and careful or else you invalidate your entire security setup.

Additionally I don't believe we have enough information to give you a proper answer. The business contracts about security expectations will have to be known up front.

In most cases keys never leave the machine they are generated on for security reasons, so if you intend to "share" information then a public key solution is usually the right pick from a purely security stand point. The exception to this is if you can share a symmetric key in a secure manner such as sending the key to the person on a physical media.

  • I don't think business contracts ever specify encryption details, nor should they in most cases as business users may choose obsolete / inappropriate technology. See @Gilles answer for a concise answer "Neither, unless it's both" ... and protocol selection is most applicable now. – makerofthings7 Jan 23 '12 at 21:13
4

Basically, the use of public key encryption (such as RSA) is much more expensive than the use of symmetric key encryption (such as AES), and when there are many messages that pass from one to another, it is better to use a symmetric key.

Now, the creation and exchange of the symmetric key may be done using public key encryption.

For example:

Each client has a private-public key pair, and the public key is stored on the server. When two clients start communication session, each takes the public key of the other from the server and send an encrypted number to the other. Then each side hashes those two numbers and uses the result as the key to encrypt/decrypt the data from now on.

MByD
  • 141
  • 3
  • 1
    I understand that principle, what I wish to know is, does the symmetric key have to be generated each time communication commences, or am I safe to use the same key for that pair of clients day-in-day-out. –  Dec 17 '11 at 23:59
  • 1
    I would suggest not to use the same key even for two messages, instead, pass some random with the message and use a hash of the key from before with this random to create the message key. – MByD Dec 18 '11 at 00:00
2

If you use the PUBLIC/PRIVATE style (RSA with sufficient bits :)) you can set up the kind of secure communication you describe this way:

  1. Alice write a message
  2. Alice encrypts it using Alice's PRIVATE key
  3. Alice encrypts it again using Bob's PUBLIC key
  4. Alice sends the results to Bob.

Then:

  1. Bob receives a message (supposedly) from Alice
  2. Bob decrypts it using Bob's PRIVATE key
  3. Bob decrypts it again using Alice's PUBLIC key
  4. If all goes well, Bob reads the message.

Note:

  • Bob is the only one that can read this message.
  • Bob knows without any doubt that it came from Alice.

Getting both those attributes with AES is a little trickier.

Jesse Chisholm
  • 129
  • 2
  • 1
    I wasn't the downvoter, but am guessing it was for either: (1) Calling signing "encrypt [the message] with Alice's private key" and verifying by "decrypting [the message] with a public key" and acting like there is one encrypted message. For signing messages you first cryptographically hash the message then encrypt the hash of the message with your private key. For verifying message you decrypt the hash with the other's public key and compare against the hash of the decrypted message. You hash first as RSA can only act on messages smaller than N; RSA-2048 can only encrypt 256 bytes. – dr jimbob Aug 20 '15 at 23:14
  • (2) Textbook RSA ( c = m^e mod N and m = c^d mod N) has shortfalls and vulnerabilities when directly encrypting messages. Therefore you should use hybrid encryption -- encrypt the message with symmetric encryption (e.g., AES) with a new random key and then append the encrypted AES random key using the recipient's public RSA key to encrypt with some sort secure padding scheme like [OAEP](https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding). (I almost didn't like your AES trickier comment - but if Alice and Bob are only people with a shared sym. key they have same guarantees). – dr jimbob Aug 20 '15 at 23:17
  • @drjimbob re: (1) Actually, I was NOT talking about `signing`. The OP wanted the entire message encrypted. What I described does encrypt the entire message. The aspect of `signing` is a side effect, not the primary goal of doing it this way, since the OP didn't ask for authentication, only for privacy. re: (2) using a hybrid system is better for efficiency, agreed. Sticking with a PUBLIC/PRIVATE keys scheme means there is nothing that has to be shared via some other channel. re: _AES tricky_ only because you really do need to use a hybrid system to get a safe channel to share the key over. – Jesse Chisholm Aug 22 '15 at 01:54
  • @drjimbob Also, the system the OP describes (`think SMS style messages`) does not lend itself to the hybrid style. There is no opportunity (like there is in TCP/TLS) to keep the channel open and change encryption protocols. Also, the size of the messages makes the PUBLIC/PRIVATE algorithms less onerous. Hardly more than you'd need for the first stage in the hybrid scheme anyway. – Jesse Chisholm Aug 22 '15 at 02:04
  • 1
    The system OP describes asks to support "plaintext with potentially unlimited length". Textbook RSA doesn't do that or have a scheme for how to securely split up messages that are larger than the key's modulus; because in practice you always do hybrid RSA as its quicker and safer. Quick example why your method of double encryption won't work with very small RSA keys (6-bit primes for 12-bit RSA) to keep it simple using textbook RSA. A's public key is: (N=3127, e=3) and A's private key is (N=3127, d=2011). B's public key (N=1927, e=3) and B's private key (N=1927, d=1227). – dr jimbob Aug 24 '15 at 04:27
  • 1
    You can check for every message with a value of 0 to N-1, we have the identity `(m^e % N)^d % N == m` for both either key pair. Now let's try a short message `m = 11` with your scheme. We encrypt with A's private key and get 2707. The next step is problematic as 2707 is greater than B's N. A doesn't notice this and encrypts this value with B's public key to get 1272. A sends 1272 over to B, who decrypts it with his private key to gets 780 which is decrypted with A's public key to get m' = 1607 which is not 11 (however this scheme will work with say m=12, m=13). – dr jimbob Aug 24 '15 at 04:28
  • Excellent point - I had not considered making the keys so tiny as to not contain the intermediates for a message. (Perhaps I should have been more aggressive with my **sufficient bits** comment.) re: "A doesn't notice" - One hopes that the code would notice, even if Alice didn't. :) One would hope the code would fuss and complain. But to silently continue as if all is well is a bug in itself. And I do find it hard to think of SMS at the same time as infinitely long messages. @drjimbob, Thank you for the detail of your response. – Jesse Chisholm Aug 25 '15 at 06:08