Note about ElGamal Encryption

Since CS276 (Cryptography), I am interested in reminding people that the textbook ElGamal encryption is not secure, unless it is only used for hybrid encryption. It has been known since as early as 1998 for Dan Boneh's paper on DDH assumption.

We found that the implementation of ElGamal encryption in libgcrypt, PyCrypto, PyCryptodome, and CryptoPP is 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 is delayed because the author said ElGamal is deprecated in PyCryptodome.

Responsible disclosure without an attack fails.

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 encourage the developers of some cryptographic libraries (with insecure implementations) to warn the users. 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: ElGamal in the library is specifically for hybrid encryption, using it in other ways are 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 break 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 do the correct things.