Attack on PyCrypto's ElGamal Encryption with Proof-of-Concept (PoC) #253
Description
Joint work with @TElgamal.
We attack PyCrypto.
The textbook ElGamal implementation is not secure. PyCrypto, and its relevant implementations, PyCryptodome, and libgcrypt, use the wrong algorithm.
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).
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.
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.
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.
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/TElgamal/attack-on-pycrypto-elgamal
A running trace is collected by Travis CI: https://travis-ci.org/TElgamal/attack-on-pycrypto-elgamal/builds/336735857
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 Legrandin/pycryptodome#90 .
This bug is prevalent. It exists in PyCryptodome and libgcrypt (if used directly to encrypt messages).



