Note about ElGamal Encryption

Since CS276 (Cryptography), I have been interested in reminding people about the insecurity of the textbook ElGamal encryption, unless it is only used for hybrid encryption. It has been known since at least as early as 1998 for Dan Boneh's paper on DDH assumption.

Erik-Oliver Blass and I found that the implementations of ElGamal encryption in libgcrypt, PyCrypto, PyCryptodome, and CryptoPP are not secure. Before we started to write down an attack (or, a proof-of-concept) for the first one, libgcrypt, we discussed with some developers of libgcrypt, we agreed that, fortunately, today, ElGamal encryption is only used for hybrid encryption, in which CDH assumption is sufficient. And as libgcrypt is specifically for GnuPG, since GnuPG only uses ElGamal for hybrid encryption, there is no security risk and no incentive to fix. When we discussed with PyCryptodome without a PoC, the author did not understand why and insisted the implementation is correct, and this issue was delayed because the author said ElGamal is deprecated in PyCryptodome.

Responsible disclosure without an attack failed.

Given that (1) libgcrypt is designed for GnuPG which only uses ElGamal for hybrid encryption; (2) PyCryptodome has the implementation for ElGamal, but is officially deprecated; (3) Only a few academic systems in voting use ElGamal, and some of them use correct implementation of ElGamal, not based on previously mentioned libraries, like Helios; (4) Hybrid encryption only requires CDH, and therefore a PoC does not attack the existing systems; (5) Without a PoC, no one believes that the implementation is wrong,

We started to write an attack (or a proof-of-concept), which, as we mentioned, will be harmless to existing systems.

With a joint work with Erik-Oliver Blass, we provided the PoC and requested for CVE entries to warn some users of these cryptographic libraries (with insecure implementations) and add pressure to the developers. The CVE entries are: CVE-2018-6829 and CVE-2018-6594.

Unfortunately, so far, none of the developers of these libraries fix the ElGamal in the desired way. The primary reason is this: ElGamal in the library is specifically for hybrid encryption, using it in other ways is beyond the scope; or ElGamal is kept only for compatiability, so it is deprecated, and no strong need to fix. A second reason is: changing the existing construction to one of the two secure alternatives breaks the compatibility totally. A third reason is: many developers do not understand the security assumptions backing ElGamal and it is hard to explain, even with a PoC.

We keep the PoC as we hope one day the developers change their minds.

ElGamal is rarely used not for hybrid encryption – so to some extent, this attack is useless. However, ElGamal has its advantages: multiplicative homomorphism with semantic security, the support of key splitting, and the ability of rerandomization. These properties, as Erik said, are useful for mixers, voting, and shuffling.

What if someone uses these libraries to build such systems? I believe that it is necessary to use a safe implementation.