Attack on libgcrypt's ElGamal Encryption with Proof of Concept (PoC)

[Weikeng Chen]

I am Weikeng Chen from UC Berkeley. This post is joint work with
Erik-Oliver Blass from Airbus.

Libgcrypt is one of the very few cryptographic libraries that
implements ElGamal. In the homepage, we see "Libgcrypt is a general
purpose cryptographic library." ElGamal is a cryptographic algorithm
with efficient multiplicative homomorphism, the ability of self
re-randomization, and the support of key splitting. Its applications
include voting, mix-nets, shuffling, etc. I am glad that libgcrypt
implements this algorithm.

However, handling the ElGamal is hard. The ElGamal implementation is
not secure for general purposes. If we use libgcrypt to encrypt
messages directly, rather than using for hybrid encryption, the
security can be broken.


We prepared the attack on the Github:
https://github.com/weikengchen/attack-on-libgcrypt-elgamal

The wiki page for explanation:
https://github.com/weikengchen/attack-on-libgcrypt-elgamal/wiki/Attack-on-libgcrypt's-ElGamal-Encryption-with-Proof-of-Concept-(PoC)

Note: This is a ciphertext-only attack.


Suggestions: I would suggest libgcrypt to consider either one of two
things as follows.

(1) Announce on the manual that ElGamal in libgcrypt should *only be
used for hybrid encryption*:
https://gnupg.org/documentation/manuals/gcrypt/Available-algorithms.html#Available-algorithms

This prevents new libgcrypt's users from possible misuse of the
ElGamal implementation for the purposes not considered by us.

(2) Consider the implementation of ElGamal with semantic security,
which would better be another algorithm in addition to current
ElGamal. One problem is about current ElGamal's prime generation. It
is hard to make the current prime generation, which is fast, secure.
There is a reason to find p=2q+1 where p and q are both primes.


Any further thought?

-- 

Weikeng Chen @ 795 Soda Hall