Are there any known weaknesses with ElGamal algorithm?

Question

I am working on a messaging system and plan to use ElGamal asymmetric encryption to protect the message contents during storage and transmission. (This would be in addition to TLS used during transmission.) What I want to know is if there are any inherent weaknesses in the ElGamal algorithm that I should be aware of or guidelines to the key bit size.

Assumptions:

1. Messages will be short, so performance is less of a concern.
2. Keys (and the associated user accounts) are disposable (short lived).
3. Message retention will be minimized (days, not weeks or months).
4. Messaging will be asynchronous as users are not expected to be online at the same time. (This is the main reason that I have ruled out the typical D-H key exchange to generate a shared, symmetric key.)
5. Private keys will never leave the client device.
6. Public keys will be stored in a database with the anonymous user account consisting of a username and hashed password.
7. Using libgcrpt.

Answer 1

A Diffie-Hellman exchange needs not be synchronous. In DH, each party has a private key (x) and a public key (g^x mod p). If the sender knows the recipient's public key g^a, then he can build his own key pair (b and g^b), compute the shared secret (g^ab), and send both his public key (g^b) and the encrypted message (symmetric key derived from g^ab) to the recipient. This works for asynchronous messages: the recipient needs not do anything at message sending time. This kind of processing is used in, for instance, S/MIME for encrypted emails, and it works.

The difference between DH and asymmetric encryption (like ElGamal or RSA) is only that in the case of DH, the sender does not get to choose the exact value of the shared secret, but that's fine as long as that secret is only used for symmetric encryption.

In fact, even if you use asymmetric encryption (ElGamal, RSA...), you still want to use it to encrypt a randomly generated symmetric key, and use that key with a symmetric encryption algorithm to process the actual data. Indeed, asymmetric encryption algorithms are quite limited in the size and format of what they could send.

That being said, ElGamal, as an asymmetric encryption algorithm, is fine as long as it is used properly. Notably, ElGamal is homomorphic (given the encryption of x and the encryption of y, one can from the outside compute the encryption of the product xy), which is a nice property in some cases, but can be bothersome in other conditions. A safe method to do ElGamal encryption is to, indeed, use it only to encrypt a random symmetric key, at which point there really is no advantage over a simple Diffie-Hellman.

"Proper usage" really means that you should not just slap together a few cryptographic algorithms; such an assembly is a delicate matter, and should be done only as part of a fully specified and analysed protocol. For instance, OpenPGP, which is implemented by GnuPG (an opensource library from which libgcrypt was derived). Indeed, OpenPGP supports ElGamal encryption, and does it "properly" (it uses ElGamal because that protocol was defined at a time when RSA was still patented, but ElGamal was not -- this no longer applies nowadays).

So that would be the "guidelines": follow OpenPGP; even better, save time and use the GnuPG implementation directly. Code which is easiest to design and implement is code which has already been designed and implemented by somebody else.

Answer 2

Whenever possible, Security Stack Exchange is going to recommend "don't roll your own" crypto. Is there a library which implements ElGamal that you can use instead where it has been tested and vetted? Implementing Crypto is always difficult and unless you are experienced in the area, you should try to avoid doing as much as possible on your own.

There will always be weaknesses that can be found in the math, but most often the issues will be in the programming of the algorithm. You may be interested in Bruce Schneier's latest paper, "Surreptitiously Weakening Cryptographic Systems". In the paper (p. 3) , he notes there is a subliminal channel attack possible.

You may want to search or ask on Crypto.SE for relevant discussions.

Many of your assumptions are algorithm and protocol agnostic.