Using bad generator in ElGamal Encryption

Question

Suppose Alice chooses a random Prime $p$ and a random private Key $a \in \mathbb{Z}^*_p$. By accident, she also chooses a random number $g \in \mathbb{Z}^*_p$, which is not a generator of $\mathbb{Z}^*_p$ and therefore

$$\langle g\rangle \subset \mathbb{Z}^*_p$$

as opposed to $\langle g\rangle = \mathbb{Z}^*_p$, which would yield a valid key. Alice then computes $A \equiv g^a \pmod{p} $ and publishes the Tuple $(p,g,A)$ as her public key.

Bob now encrypts a message $M$ using Alices public key by computing

$$C_1 = g^b \pmod{p}$$ $$C_2 = M \cdot A^b \pmod{p}$$

Is it possible for an attacker (Eve) to distinguish a “real” ciphertext $(C_1,C_2)$ from a random ciphertext $(Z_1,Z_2) \stackrel{$}{\longleftarrow} \mathbb{Z}^*_p$ with significant advantage (say $Adv \geq \frac12$)?

---

Edit: I guess it should be enough to show, that the ciphertext cannot be random, if

$$\langle g \rangle \neq \langle C_1 \rangle \quad(\text{or $Z_1$, respectively})$$

But how can Eve check for this property efficiently? Can someone point me in the right direction here?

---

Edit: A real-world situation where this flaw occurred was recently found in the PyCrypto Library

Answer 1

The attacker can distinguish $\langle C_1, C_2 \rangle$ from a random pair if the attacker knows a value $q < p-1$ such that $g^q = 1 \mod p$.

Here's how the distinguisher would work: he simply computes $C_1 ^ q$ and checks to see if that value is 1. If this $C_1$ corresponds to a valid ciphertext, then that value will always be 1. If this $C_1$ is part of a random pair, then the value will be 1 with probability $q/(p-1) \le 1/2$ (remember, $q$ will always be a divisor of $p-1$).

On the other hand, just because we show distinguishability against a particular random source doesn't mean that we have shown that it is insecure. In this case, that would depend on what is the order of $g$ (and whether it is "smooth", that is, has no large prime factors). If the order of $g$ is smooth, then solving the discrete log problem is easy, and hence the system is insecure. On the other hand, if the order of $g$ has a large prime factor $q$, I believe that it is still safe.

Answer 2

Actually, you don't want $g$ to generate $\mathbb{Z}^*_p$ for Elgamal. The order of $\mathbb{Z}^*_p$ is $p-1$ (an even non-prime number). Instead, $g$ should generate a multiplicative subgroup of prime order. With Elgamal specifically , message encoding generally requires choosing a value $p$ such that $p=2q+1$ for a smaller prime $q$. Then $g$ should be chosen to have order $q$.

If you use all of $Z^*_p$, one can efficiently test if the plaintext of an encrypted message is a quadratic residue or not, which leaks one bit of information about the plaintext. For CPA-security, you ask the oracle to encrypt a plaintext that is a QR. If the challenge ciphertext encrypts a NQR, you know it is a randomly generated tuple and not an actual encryption of your message.

If I am reading the bug report you posted correctly, it seems the "bug fix" is not correct (possibly the code was correct to begin with, but I can't determine that from the bug report as it has mistakes -- order of 107 in $\mathbb{Z}_{211}$ is not 42; and since 107 is not a safe prime, maybe the code is doing something weird).