Best way to encrypt messages in Java where ciphertext is public

I'm writing an app in Java where users must be able to share encrypted messages, and communication happens exclusively via a database where all data is publicly visible.

Requirements are roughly:

• Each user may publish some information (e.g. a public key) to the public database but should only do this once
• Other users must be able to encrypt a message for a target user and publish it publicly on the same database
• The intended recipient must be able to decrypt the message, but no other user should be able to do so
• The encryption must be strong enough that no plausible brute force computation should be able to decrypt the message (now or in the future)
• Messages are arbitrary length, but usually quite small (think short emails, tweets etc.)
• Must be easy to implement in regular Java (libraries like Bouncy Castle are fine if needed)
• Users already have Ed25519 key pairs for digital signatures if necessary

What crypto algorithm or combination of algorithms would be best to meet these requirements? I'm assuming some form of asymmetric encryption algorithm with a public/private key pair for each user but alternative ideas welcome. I definitely want to avoid the "roll your own crypto" trap though....

You (almost) always roll your own protocols. Which is usually where the hacks are.

Now, if you were to roll your own algorithm (as in, you avoid, say, AES-256, and write something on your own. We'll just XOR every byte with a repeated application of 'OhWowThisIsTheBestSecurityEvar', it's like a one-time pad right, can't be cracked! - that kinda thinking is what the whole 'dont roll your own crypto' meme is all about. Don't do that.

Even if you use off the shelf 'protocols', it's real easy to mess it up and create holes. The protocol side (HOW you use the crypto algorithms) is by its nature not easily abstracted into a single, hard-to-impossible to abuse prebuilt library.

So, roll your own. Protocol that is.

It seems nearly trivial here - but it's not. The basic job is to use Public/Private key crypto, in the usual fashion, encrypting the message with symmetric crypto (say, AES-256), generating a random IV and random key, and storing both in the DB, but the key is stored encrypted - encrypted using Public/Private key crypto.

That is, at its core, enough to do what your requirements say you want. But, what about replay attacks? Possibly overzealous or implausible, but what if I can write stuff into your DB? I could replay the message: Store the exact same ball of encrypted bytes but with different timestamps, and you'd think it was real.

That's exactly one of those protocol thingies: It helps if you include the timestamp, sender, etc all inside the blob to be encrypted - you want a replay attack to be innocuous, and generally, if the message (including the metadata) is the exact, precise same, it should be. Maybe. Usually. It depends on what your users expect and what they'll be using it for. There is no such thing as perfect crypto, after all. But if even that is not acceptable, there are solutions to that too, though the easy route is simply to ensure nobody has raw SQL-level write access to the DB.

If your system gets 'hacked' it'll almost always be in the second-level 'protocol' bits. Can I just call your help desk and inpersonate a user? Can I just say I lost my password and get a new one mailed to me, and 'just' hack the user's email instead? Can I stick a keylogger in their computer? Maybe litter some USB sticks with RAT worms around the parking lot; a RAT worm specifically written to find their key files, catch them in entering the password for this key file, and send it all to me? No 'off the shelf java library' is ever going to protect you against any of this. You can't do security in a 'I dont really know what I am doing, but I at least I know I don't know so I'll make sure to get a community and expert recommended library and try to follow its manual as well as I can and surely I'll be fine!' - kind of fashion. Not if you take it seriously.

Some of the algorithms you should probably use:

• BouncyCastle supports ElGamal, a Public/Private key encryption scheme. The idea is that all users have a public and private key; the public key is known to your server (and all users on demand; your server is a clearinghouse for them and will have to vouch for the truth, that is, if you go: "here is the public key for user Foo", you're vouching that this is true, and presumably vouching that the personal info of user Foo on your site is correct. How - that's on you, and has nothing to do with crypto, but with politics and local processes. Do you call them? Do they identify themselves with a passport? What? The private key is known only to them. You'll need to handroll some sort of invalidation scheme. Perhaps users can anoint a few other users - they then get the right to invalidate their key. The idea being, if a user feels their private key is compromised, they ask one of their buddies to log in and authenticate themselves to the system, and tell the system to mark your public key as no longer valid for any further communications.

• Note that you'll have to find a way to use that Ed25519 key pair you have if you want to use that for the vouching system as above.

• Use AES-256 along with your plane jane basic new SecureRandom() to generate a key for each and every message you want to store in the system. To store a message, you take the data, generate a random key, encrypt the data using that key and the AES-256 algorithm, store the encrypted data, then you encrypt the key using ElGamal and the user's public key, and store that too. To decrypt this data, the user fetches the (with their public key encrypted) key data (which can be public), and the encrypted data (also public), and can undo the job on their end by first using their private key + ElGamal to derive the randomly generated AES-256 key used, and then use that. You don't encrypt the entire message with ElGamal; that's quite slow and not the common way to do it. AES-256 is blazingly fast. But symmetric. You'll need a 'block mode' and a 'padding mode' for your encryption in addition to an algorithm (Which will be AES-256). block mode should probably be GCM; you may read about CBC; that's outdated (worse, and slower). Definitely don't pick ECB, that's straight up insecure. Padding probably doesn't matter, depends, as usual, on so many factors.

• You mentioned nothing about signatures. If user "Foo" wants to send a message to user "Bar" in a way that nobody but Bar can read it, all they have to do is the above. But if they do, "Bar" has absolutely no idea who sent it. GCM has some built in support for MACs, which is what you need to tag a message in a way that senders can prove they were, in fact, the sender, and also to tag date and time, though this is not easy; basically you as a server would tag any message with 'I, server, decree, and you are going to have to trust me, that this was present in the DB at this point in time and appeared recently; to me anyway. Signed, server'.

That'll give you a few terms (MAC, GCM, AES-256, ElGamal, Bouncy Castle, signatures, and a few more) to search the internet for and read up on.

It sounds to me that you are developing a chat system.

The way to fulfil your requirements you need to combine two crypto systems.

The first one is a Diffie-Hellman key exchange - in short: each party generates a private/public key pair. The public key is stored on the server. If I try to send a message to Bob I'm using your database for "Bob" and get his public key. Next I'm generating a "shared secret" with my private key and Bob's public key - this shared secret is usually 32 bytes long.

Now the second phase begins - I'm encrypting my message with an AES algorithm (best one could be "GCM"-mode) and save the encrypted message (encoded as Base64-string) in your public database (of course with any hint that the counterpart is me).

Third phase: Bob is getting the encrypted message with the note it's from Michael. Now Bob is searching in the database for Michael's public key, builds the shared secret with his (Bob's) private key and Michael's public. Some kind of magic will happen - the shared secret is the same key I used for encryption. Now Bob is been able to decrypt my message.

Just a note: beware the risks because if Bob will lose his private key (maybe stored on his stolen smartphone) he will no longer read any messages for him, so a backup of his private key is needed.