# Malleability of ElGamal and Hashed ElGamal

Question: Suppose A encrypts a number $x$ which indicates her bid on a contract, using ElGamal encryption. Say that the encryption of $x$ produces a ciphertext $c$. Explain how E can modify $c$ to make it an encryption of $100 \cdot x$.

Answer: E is exploiting the malleability of ElGamal. She can take the ciphertext pair $(c_1,c_2)$ Where $c_1$ is $g^y$ and $c_2$ is $m * h^y$ and multiply $c_2$ by $100$ to get the desired results. A can protect herself from this by used a hashed version of ElGamal

Is this correct?

-
The answer to your question is that E has to multiply c by 100 to make it an encryption of 100⋅x. See my explanation below. Not sure what you mean by cyphertext pair. In Elgamal you would mostly pass an ephemeral key along with an encrypted message as a pair. –  mwhs Jun 25 at 0:05

There are different crypto-systems that have been called Hash-Elgamal. The one your exam refers to is likely whatever was included in your course. Without knowing that, we can't necessarily answer your question.

The most common is the Elgamal variant defined with encryption function: $c=\mathsf{Enc}(m,r)=\langle g^r, \mathcal{H}(y^r)\oplus m \rangle$

This is still a malleable encryption function, except that the adversary must xor in the amount they want to change the encrypted message by. So strictly speaking, it may protect against the exact attack of multiplying in constants, but it does not prevent the broader attack of being able to manipulate a message under encryption (without knowing the message).

Hash Elgamal could also refer to the Fujisaki-Okamoto heuristic applied to Elgamal. This prevents malleability but can also lose the CPA-security of Elgamal. Other Elgamal variants that use a hash function are Cramer-Shoup (mentioned by @jalaj) and DHIES. These are both secure against any malleability (they are CCA-secure) however they aren't typically referred to as hash Elgamal.

-
If there is a formal proof of the encryption scheme $c=\mathsf{Enc}(m,r)=\langle g^r, \mathcal{H}(y^r)\oplus m \rangle$? –  frank li Nov 5 at 14:41

What you are saying for hashing is actually more commonly known as Cramer-Shoup's crypto-system and yes it is non-malleable. You can read Lecture notes 22 given by Boaz Barak in Fall 2007 for more details.

-

What you are referring to is the same weakness in regard to malleability that is also applicable to (non-hashed schoolbook) RSA. In Elgamal an attacker can (in practice) not decrypt the transferred and encrypted message, but he can modify (factor) it and is able to determine the effect of his modification.

Let $y$ be the original encrypted message of the plain text $x$.

In the course of action the encrypting party would transfer a data tuple to the destination party, namely the encrypted data $y$ and the ephemeral key $K_E$, which is public, but only valid for this one message (since Elgamal is probabilistic).

An attacker could simply replace $y$ by the product $n \cdot y = y_{NEW}$, where $n$ is any factor at the discretion of the attacker.

Let's call the altered encrypted message $y_{NEW}$ to make clear it is different from the original encrypted data $y$.

The receiving party would then decrypt the result as $n \cdot x$, with $x$ being the original unencrypted data from the sender. Of course the receiving party does not see the the two factors but only the product and is left believing (or not) that the data is integer.

Why does this work?

When receiving the tuple the decrypting party would first compute the needed multiplication key $K_{M_{DECRYPT}}$ from the public ephemeral key $K_E$, the secret exponent $d$ and the prime $p$, and of that find the inverse $K_{M_{DECRYPT}}^{-1} \mod p$, or at least have a notion of the inverse for calculation purposes.

Decryption then works by multiplying the received encrypted data $y_{NEW}$ by $K_{M_{DECRYPT}}^{-1}$ modulo $p$.

Let's call the decrypted message $x_{RECEIVER}$ to make clear that it is the result of the decryption on the receiver side, and that it may not necessarily match the original message $x$.

$x_{RECEIVER} \equiv y_{NEW} \cdot K_{M_{DECRYPT}}^{-1} \equiv n \cdot y \cdot K_{M_{DECRYPT}}^{-1} \mod p$

and since $y \equiv x \cdot K_{M_{ENCRYPT}} \mod p$ (see encryption)

$x_{RECEIVER} \equiv n \cdot y \cdot K_{M_{DECRYPT}}^{-1} \equiv n \cdot (x \cdot K_{M_{ENCRYPT}}) \cdot K_{M_{DECRYPT}}^{-1} \equiv n \cdot x \mod p$

The substitution of $K_{M_{ENCRYPT}} \cdot K_{M_{DECRYPT}}^{-1} \equiv 1 \mod p$ works since both keys are equivalent, even though they are calculated separately. This can be demonstrated as follows:

$K_{M_{ENCRYPT}} \equiv K_{PUB}^i \equiv K_E^d \equiv K_{M_{DECRYPT}} \mod p$

since

$K_{PUB}^i \equiv (\alpha^d)^i \equiv \alpha^{di} \mod p$

and

$K_E^d \equiv (\alpha^i)^d \equiv \alpha^{di} \mod p$

for the secret exponent (private key) $d$ and the probabilistic exponent $i$ and a primitive element $\alpha \in \mathbb{Z}_p^*$.

The result of the decryption ($x_{RECEIVER}$) is thus the original data $x$ multiplied by the factor $n$ chosen by the attacker.

This is why (schoolbook) Elgamal is called malleable.

As previous authors have mentioned, other more advanced variants of Elgamal are used in practice, in particular variants resistant to this demonstrated weakness.

-