To continue our journey in cryptography, I suggest you discuss today the ElGamal encryption.

Presented in August 1984 by Taher Elgamal, from which the algorithm takes its name, it proposes an asymmetric encryption protocol built from the Diffie-Hellman Key Exchange (Published 8 years earlier).

A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, ElGamal T. Lecture Notes in Computer Science, vol 196. (PDF).

Reminder about Diffie Hellman

The easiest way to understand ElGamal is to start from the Diffie-Hellman key exchange. As a reminder, here are the steps of the protocol:

1. Alice and Bob publicly agree on a group $(G, \times)$ and a generator $g$;
2. They each choose a random number (their secret key), $a$ for Alice and $b$ for Bob;
3. They compute their public part and send it to each other; Alice therefore sends $g^a$ to Bob and receives $g^b$ in return;
4. They finally compute the shared secret; Alice computes $g^{b^a}$ and Bob computes $g^{a^b}$ which, by magic of mathematics, have the same value.
5. They can now use this shared secret to encrypt and decrypt their subsequent communications 🎉.

ElGamal

For Elgamal, the protocol is exactly the same but since only Alice needs to write to Bob, they can distribute the protocol and take initiatives.

Foreplay

To allow everyone to send him kind words, Bob takes care of the first half of the protocol:

• choice of group $(G, \times)$,
• choice of generator $g$,
• choice of a secret random number $b$,
• computation of the public part $g^b$.

The public information (group, generator and $g^b$) make the public key and can be sent in advance to Alice or simply published in a directory for everyone to enjoy.

Generating the secret message

To send a message to Bob, Alice retrieves this public information and takes care of the second part of the protocol:

• choice of his secret random number $a$,
• computation of its public part $g^a$,
• computation of the shared secret $g^{b^a}$,
• message encryption $m' = m . g^{b^a}$

In the original Elgamal’s paper, the encryption is done in a finite additive or multiplicative group, the important thing being that it is easily invertible. It is usually a multiplication that is chosen.

She just has to send her public part and the encrypted message to Bob.

Receiving message

With all this information, Bob can compute the secret key and decrypt the message.

• computation of shared secret $g^{b^a}$
• message decryption $m = m' / g^{b^a}$

If you don’t see the relationship with Diffie Hellman, go back to the first diagram 😉.

In real life…

All this is in theory because in practice, there are a few small adaptations.

Add a PKI

As long as Eve can only listen to the network, everything is fine, but if she is able to alterate the communications, she can very well replace the keys of Alice and Bob with her own in the exchanges.

When Alice thinks she is sending a message to Bob, she actually sends it to Eve who can decrypt it. After reading it, she encrypts it with her own key for Bob. Note that she can also change the contents before encrypting and sending to Bob.

Since the message that Bob receives is accompanied by the public key allowing it to be decrypted, he cannot be sure who is the author (only that he is indeed the recipient).

To solve this problem (already present for Diffie hellman), we then use signatures and a trusted third party who is responsible for authenticating the public keys of the actors. Often by signing certificates but not only.

Hybrid system

The encryption and decryption operation is possible on arbitrarily long messages, but this operation is often slower than symmetric encryption algorithms with equivalent security.

We could have replaced the multiplication by a symmetric algorithm, the shared secret then being the key of this algorithm, but the tradition chose otherwise (and did well).

Indeed, we prefer to use the algorithm of Elgamal, unchanged, conjointly with a symmetric algorithm. We then speak of a hybrid algorithm. We then choose a key to encrypt the message and it is this key that will be encrypted with Elgamal.

The advantage of this method is to decouple the asymmetric algorithm that establishes the communication (Elgamal, RSA, …), and the symmetric algorithm that secures the content (AES, 3DES, …). It is then possible to choose the most suitable combination or to improve some part according to the latest advances.

This is done through the cypher suites of TLS and which has been further reinforced in version 1.3 of the protocol (RFC8446).

Nonce Re-use

When Alice wants to send a message to Bob, she must generate a specific secret random number $a$ for the message to send.

She could of course reuse the previous key but in doing so, she would jeopardize the security of all her exchanges.

Indeed, suppose that Alice sends two messages $m_1$ and $m_2$ to Bob using the same random number $a$. Since Bob has not changed his public key, the shared secret ($K = g^{b^a}$) will be the same for the encryption of the two messages:

$$\begin{align} m_1' & = m_1 . K \\ m_2' & = m_2 . K \end{align}$$

Now suppose that an attacker (Eve) got her hands on a plaintext message… ($m_1$). The problem is that she can use it to decipher all the other messages between Alice and Bob. $$\begin{align} m_1' / m_2' & = (m_1 . K) / (m_2 . K) \\ m_2 & = m_1 . m_2' / m_1' \end{align}$$

That can happen more often than you think… The Krack attack on WPA2 follows the same logic (even if the encryption used is different). Force WIFI clients to use one nonce several times then, thanks to the (partial) knowledge of a clear message, decrypt the others.

Note that in this case, Eve can also retrieve the $K$ shared secret: $$\begin{align} K & = m' / m \end{align}$$

Fortunately, even in possession of the public parts and the shared secret, obtaining the private keys remains difficult since it is a question of solving the problem of the discrete logarithm.

In fact, it is a question of solving the Diffie-Hellman problem which in the current state of our knowledge is as difficult as that of the discrete logarithm.

Attack on encryption

As defined and used, this cipher has the property of malleability: it is possible, to a certain extent, to modify the plain message by operating only on the cipher.

Precisely, the encryption operation being a multiplication, multiplying the cipher by a constant has the same effect as if the multiplication had taken place on the plain:

$$\begin{align} not . m' & = n . m. K = (n.m)' \end{align}$$

If Elgamal is used to encrypt a message, and Eve has the ability to intercept communications, she can then modify the very content of the messages and, depending on the context, change the meaning to her advantage.

To avoid this type of attack, you can either add a signature system to the messages or manage it directly in the protocol as is the case with Cramer-Shoup.

If El Gamal is used to encrypt a symmetric key, this weakness is no longer relevant since changing the symmetric key will make the message unreadable, which Eve might as well have achieved by replacing the message with random data.

Finally, it should be noted that this property is not specific to El Gamal but also affects other protocols such as RSA or, to a lesser extent, the CBC mode.

And after ?

At the time of its publication, RSA was covered by a patent (patent US4405829A, valid only in the US because filed after publication) and the community was very happy to welcome a new royalty-free algorithm. GnuPG, the free clone of PGP therefore implements this cryptosystem for the exchange of messages.

On the other hand, El Gamal does not natively offer a signature method. It is therefore not usable for certain applications such as SSL/TLS for which RSA retains the advantage, especially since the expiry of the patent in September 2000.

On the other hand, as one can implement Elgamal on any finite group, a version on elliptic curves was born (i.e. implemented in GnuPG) and offers, for an equivalent key size, much greater security.

Finally, here are the recommendations of the ANSSI (via its General Security Reference) regarding key length for asymmetric ciphers:

• For the classic version, 2048 bits before 2030 and 3072 bits beyond.
• For the elliptic curve version, 200 bits before 2020 and 256 bits beyond.

In real life, we rarely use ElGamal, but its affiliation with Diffie-Hellman makes it easily understandable and allows it to be implemented via elliptic curves, which is rather fashionable and very useful.