Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
As a trivial starting point, we know that the order of $g$ divides the order of $\mathbb{Z}^*_p$. From that, perhaps a non-negligible set of potential $g$s have a small order that can be brute-forced to look for $C_1$? –  B-Con Jun 29 '12 at 17:02
add comment

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
Isn't finding such a $q$ with $g^q \equiv 1 \pmod{p}$ equivalent to solving the discrete logarithm problem? –  padde Jun 30 '12 at 15:33
    
@padde: no, it is not. It is quite easy if you know the factorization of $p-1$, as q will always be a divisor of that. Even if you don't know the complete factorization, well, you can easily find all the factors under, say, $2^{64}$; unless $g$ was specifically chosen so that $(p-1)/q$ had no small prime factors, it will almost certainly be the case that you can find an appropriate value of $q$. –  poncho Jul 1 '12 at 1:27
add comment

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).

share|improve this answer
    
interesting, i didn't know that. but what happens when $g$ isn't a valid generator at all? –  padde Jun 29 '12 at 20:16
    
If $g$ generates a prime-ordered group that is small (e.g., less than 160 bits), then discrete logs become feasible. If $g$ has composite order, the discrete log will not generally (always) not be hard (there are ways to setup composite groups that are). If $g$ has large prime order, then it is secure even if it is not the order that was intended (but you may have trouble encoding $M$ into $\mathbb{G}_q$). –  PulpSpy Jun 29 '12 at 20:28
    
Typo: should be "not generally (always) be hard". Also FWIW, if you try and encrypt an $M$ that is not in the group generated by $g$, then you can end up with a different set of problems. –  PulpSpy Jun 29 '12 at 20:47
    
If the generator has not order p, you don't have Elgamal, but a variant of it I would say. Apart from that, leakage of the Jacobi symbol applies to RSA as well. Using an appropriate plaintext encoding is the correct solution in both cases. –  SquareRootOfTwentyThree Jun 30 '12 at 8:32
    
Your first point is semantics, but all modern crypto textbooks do not consider the secure version (order q instead of p-1) a variant. Elgamal with order p-1 leaks Legrange, not Jacobi, but it is true both Elgamal and RSA leak a bit. Padding is necessary for RSA to have CPA (and likely CCA) security, but Elgamal is CPA secure in prime order subgroups without padding. Padding is essentially never used with Elgamal, either because you want the homomorphic properties or you use a hybrid variant (e.g., hash Elgamal). –  PulpSpy Jun 30 '12 at 19:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.