Skip to content

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

Jump to bottom
Weikeng Chen edited this page Feb 7, 2018 · 3 revisions

Joint work with Erik-Oliver Blass from Airbus.

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

I would give the basic idea as follows. Readers with modern algebra background can jump to @TElgamal 's explanation here.

The wrong implementation has two messages classes.

Due to technical reasons, all messages are classified into two classes. A random message belongs to one of them (with 50% 50% possibility).

two_message_classes

In some applications, there are only several possible messages. Consider we are sending a military message. There are only two outcomes: the army moved forward or retracted. With a high possibility, they belong to different classes.

Encrypt the two messages.

We now encrypt two messages with ElGamal.

encrypt_message

The encrypted result is called a ciphertext. It should reveal NO information about the original message.

Expectation: encrypted message has indistinguishability.

We expect a secure encryption scheme to provide message indistinguishability. No adversary can learn what is encrypted inside the ciphertext better than a random guess.

message_ind

Let us assume the headquarter sent the second message -- no adversary should to able to learn.

Truth: the adversary can distinguish messages in two different classes.

Due to the wrong implementation, the adversary can distinguish messages in different classes.

truth

If the outcomes differ in which classes they belong to, then an adversary can infer more information.

Proof-of-Concept (PoC).

We release our attack code in this GitHub repo: https://github.com/weikengchen/attack-on-libgcrypt-elgamal

A running trace is collected by Travis CI: https://travis-ci.org/weikengchen/attack-on-libgcrypt-elgamal/builds/336433895

Showing that our adversary makes 0% mistakes in guessing the messages if the two outcomes differ in the classes they belong to.

Discussion

The problem can be fixed by using ElGamal carefully on the correct algebra group. Some results are given by @TElgamal and me on issue https://github.com/Legrandin/pycryptodome/issues/90 .

If libgcrypt plans to limit the uses only to hybrid encryption, I think libgcrypt should announce it on the manual here: https://gnupg.org/documentation/manuals/gcrypt/Available-algorithms.html#Available-algorithms

Clone this wiki locally