Discussion on ElGamal generator safe check

[weikengchen]

This is a problem starting from PyCrypto.

The implementation of ElGamal is not secure -- the problem is that DDH assumption does not hold for the group modulus $p$.

It is only believed to hold for a safe prime $p=2q+1$, where $q$ and $p$ are primes. And the generator $g$ is not the generator of order $p-1$. It should be the order $q$.

Only, in this case, the ElGamal is safe because the underlying DDH assumption holds.

You can check the page 3 of this scribe note for a small explanation. Note that in many IEEE standards for ElGamal, their generator is also not the one here.

https://people.eecs.berkeley.edu/~alexch/docs/CS276-F2015/lecture-14.pdf

My problem:

1. Disable ElGamal?

2. Let me submit a PR to correct this one? Note that the secure ElGamal takes a super long time to find a good prime.

And also, I notice that in the documentation, ElGamal is not preferred. However, actually, it is better than RSA, if we want to use the homomorphism.

1. If we want to use RSA with homomorphism, this can only be the textbook RSA, which is insecure. If we use the one with padding, we lose the homomorphism of RSA.

2. But ElGamal can remain secure if we want homomorphism.

[Legrandin]

ElGamal key pairs are already generated with modulus p being a safe prime, and generator g having prime order q=(p-1)/2. See here the relevant code in Crypto.PublicKey.ElGamal.generate():

https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/PublicKey/ElGamal.py#L34

[Legrandin]

ElGamal key pairs are already generated with modulus p being a safe prime, and generator g having prime order q=(p-1)/2. See here the relevant code in Crypto.PublicKey.ElGamal.generate():

https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/PublicKey/ElGamal.py#L34

[weikengchen]

@Legrandin

Sorry. I am still not on the same page.

The code in the repo is:
if safe and pow(obj.g, q, obj.p)==1: safe=0

It seems that the accepted obj.g will have order 2q instead of q?

[weikengchen]

@Legrandin

Sorry. I am still not on the same page.

The code in the repo is:
if safe and pow(obj.g, q, obj.p)==1: safe=0

It seems that the accepted obj.g will have order 2q instead of q?

[weikengchen]

I edited the content again because I believe we are not all set.

[weikengchen]

I edited the content again because I believe we are not all set.

[wheeler18]

@weikengchen Looking forward your work , the maintainer seems not understanding your question.

[wheeler18]

@weikengchen Looking forward your work , the maintainer seems not understanding your question.

[weikengchen]

@wheeler18 I came to the upstream which is GNU Crypt Library. I have successfully persuaded them to accept this change. However, I have not yet have time to write a PR for them. I think that would be the first step.

[weikengchen]

@wheeler18 I came to the upstream which is GNU Crypt Library. I have successfully persuaded them to accept this change. However, I have not yet have time to write a PR for them. I think that would be the first step.

[TElgamal]

Please allow me to clarify: DDH is believed to hold in, e.g., the subgroup QR_p of quadratic residues mod p. (Specifically, the Legendre symbol over the ciphertext cannot leak whether a plaintext is a quadratic residue or not.)

With p a safe prime, QR_p has prime order, so any element of QR_p is a generator. Choosing a generator of QR_p is easy, simply take any element of Z_p and square it. This is, however, not sufficient. Plaintexts must be encoded as elements of QR_p, too. The standard textbook trick is to allow only integers 1,...,(p-1)/2 as plaintexts m, and square them before encryption. After decryption, computing a square root is easy in Z_p.

The current implementation lacks that, so it is insecure. Maybe, instead of repeatedly checking whether the order of g is (p-1)/2, the implementation should 1) simply take a random element x of Z_p and set g=x^2, and 2) encode plaintexts as QR by restricting m to 1...(p-1)/2 and square, decode by computing the square root?

[TElgamal]

Please allow me to clarify: DDH is believed to hold in, e.g., the subgroup QR_p of quadratic residues mod p. (Specifically, the Legendre symbol over the ciphertext cannot leak whether a plaintext is a quadratic residue or not.)

With p a safe prime, QR_p has prime order, so any element of QR_p is a generator. Choosing a generator of QR_p is easy, simply take any element of Z_p and square it. This is, however, not sufficient. Plaintexts must be encoded as elements of QR_p, too. The standard textbook trick is to allow only integers 1,...,(p-1)/2 as plaintexts m, and square them before encryption. After decryption, computing a square root is easy in Z_p.

The current implementation lacks that, so it is insecure. Maybe, instead of repeatedly checking whether the order of g is (p-1)/2, the implementation should 1) simply take a random element x of Z_p and set g=x^2, and 2) encode plaintexts as QR by restricting m to 1...(p-1)/2 and square, decode by computing the square root?

[weikengchen]

Are you Taher? Another two people I guess are Dan Boneh and Victor Shoup.

I think we should do the following four things:

(1) use $p=2q+1$ where $p$ and $q$ are both primes.

(2) set the generator $g$ to be in $G=QR(Z_p^*)$

(3) to encrypt a binary string $m\in{0,1}^\lambda$, express it into a number in ${1,2,...,2^\lambda}$, and encode it into $\widetilde{m}$ by $\widetilde{m}=m^2 \in Z_p^*$.

(4) to decode it back, first compute $m'=\widetilde{m}^{(q+1)/2}$. if $m'>2^\lambda$, then $m=p-m'$. Otherwise, $m=m'$.

[weikengchen]

Are you Taher? Another two people I guess are Dan Boneh and Victor Shoup.

I think we should do the following four things:

(1) use $p=2q+1$ where $p$ and $q$ are both primes.

(2) set the generator $g$ to be in $G=QR(Z_p^*)$

(3) to encrypt a binary string $m\in{0,1}^\lambda$, express it into a number in ${1,2,...,2^\lambda}$, and encode it into $\widetilde{m}$ by $\widetilde{m}=m^2 \in Z_p^*$.

(4) to decode it back, first compute $m'=\widetilde{m}^{(q+1)/2}$. if $m'>2^\lambda$, then $m=p-m'$. Otherwise, $m=m'$.

[weikengchen]

@wheeler18 I think I should really work on fixing this :)

@TElgamal If you are one of the people that can automatically persuade the maintainer of this repo to change, e.g. Taher, Dan, Victor, or other cryptographers I know working seriously on using DDH-version ElGamal, you are welcome to ping me an email to weikeng@eecs.berkeley.edu and I think we can drop an email to the maintainer when I have a pull request to fix this issue.

side note: the source of the problem is in GNU Crypt Library.

[weikengchen]

@wheeler18 I think I should really work on fixing this :)

@TElgamal If you are one of the people that can automatically persuade the maintainer of this repo to change, e.g. Taher, Dan, Victor, or other cryptographers I know working seriously on using DDH-version ElGamal, you are welcome to ping me an email to weikeng@eecs.berkeley.edu and I think we can drop an email to the maintainer when I have a pull request to fix this issue.

side note: the source of the problem is in GNU Crypt Library.

[TElgamal]

Regarding step 3), just make sure that 2^\lambda does not go beyond (p-1)/2. That is, allow only inputs up to (p-1)/2.

[TElgamal]

Regarding step 3), just make sure that 2^\lambda does not go beyond (p-1)/2. That is, allow only inputs up to (p-1)/2.

[weikengchen]

Agree. That can ensure the correctness of encoding and decoding is possible to achieve.

note: I should have used $n\left(\lambda\right)$ instead of $\lambda$.

[weikengchen]

Agree. That can ensure the correctness of encoding and decoding is possible to achieve.

note: I should have used $n\left(\lambda\right)$ instead of $\lambda$.

[Legrandin]

I agree with most parts - though I invite to consider that this encryption method is private and undocumented, and only there for backward compatibility with PGP software that would break if we added the appropriate message encoding to make it secure. In other words, this is raw encryption code is not meant to be used by itself, in the same way you should not use textbook RSA by itself without proper padding.

The one part I am not clear about is this comment from @weikengchen.
You say that this piece of existing code:

if safe and pow(obj.g, q, obj.p)==1: safe=0

selects a generator g of order 2q instead of order q. Are you sure about that?

[Legrandin]

I agree with most parts - though I invite to consider that this encryption method is private and undocumented, and only there for backward compatibility with PGP software that would break if we added the appropriate message encoding to make it secure. In other words, this is raw encryption code is not meant to be used by itself, in the same way you should not use textbook RSA by itself without proper padding.

The one part I am not clear about is this comment from @weikengchen.
You say that this piece of existing code:

if safe and pow(obj.g, q, obj.p)==1: safe=0

selects a generator g of order 2q instead of order q. Are you sure about that?

[weikengchen]

@Legrandin Let me try to explain:

1. if an element g, g^q=1 (mod p), then g is a Quadratic Residue, not a generator of order 2q.

2. for a generator in Z_p^*, g^q should be -1 (mod p), so that g^{2q}=1, its order is 2q.

3. This line of the code REJECTS all generators with order q. It sets the flag safe=0 and forces the program to reselect a generator.

4. Therefore, your program will finalize with a generator such that safe=1, this generator must have the order of 2q.

[weikengchen]

@Legrandin Let me try to explain:

1. if an element g, g^q=1 (mod p), then g is a Quadratic Residue, not a generator of order 2q.

2. for a generator in Z_p^*, g^q should be -1 (mod p), so that g^{2q}=1, its order is 2q.

3. This line of the code REJECTS all generators with order q. It sets the flag safe=0 and forces the program to reselect a generator.

4. Therefore, your program will finalize with a generator such that safe=1, this generator must have the order of 2q.

[TElgamal]

@Legrandin You now write in Elgamal.py:
When creating ElGamal keys, the generator wasn't a square residue: ElGamal encryption was not secure under the DDH assumption.

This indicates that, with your latest modification, ElGamal encryption is now secure under the DDH assumption. However, this is not true. As I mentioned in my previous comment, you must encode plaintexts as quadratic residues, too (which is, I guess, what breaks compatibility).

[TElgamal]

@Legrandin You now write in Elgamal.py:
When creating ElGamal keys, the generator wasn't a square residue: ElGamal encryption was not secure under the DDH assumption.

This indicates that, with your latest modification, ElGamal encryption is now secure under the DDH assumption. However, this is not true. As I mentioned in my previous comment, you must encode plaintexts as quadratic residues, too (which is, I guess, what breaks compatibility).

[weikengchen]

The encoding of the plaintexts is something not compatible and non-trivial.

Need a discussion

[weikengchen]

The encoding of the plaintexts is something not compatible and non-trivial.

Need a discussion

[Legrandin]

@TElgamal I clarify the message to say now When creating ElGamal keys, the generator wasn't a square residue: ElGamal encryption done with those keys cannot be secure under the DDH assumption., which communicates a bit better that the generator being a residue is a necessary but not sufficient condition. Since the library itself does not support encryption officially, we cannot make claim an implementation using the keys generated by the library is secure or not.

@weikengchen thanks for pointing out that line in generate(). I looked at it several times without noticing it was indeed doing the opposite I intended it to do. :-(

I will close this issue, since this fix is in v3.4.10.

[Legrandin]

@TElgamal I clarify the message to say now When creating ElGamal keys, the generator wasn't a square residue: ElGamal encryption done with those keys cannot be secure under the DDH assumption., which communicates a bit better that the generator being a residue is a necessary but not sufficient condition. Since the library itself does not support encryption officially, we cannot make claim an implementation using the keys generated by the library is secure or not.

@weikengchen thanks for pointing out that line in generate(). I looked at it several times without noticing it was indeed doing the opposite I intended it to do. :-(

I will close this issue, since this fix is in v3.4.10.