question on ElGamal implementation

[Weikeng Chen]

Dear All,

I am not sure about whether libGCrypt uses the correct multiplicative
group for ElGamal to ensure the underlying cryptographic guarantee --
DDH assumption -- holds.

I cannot find details in the source code that libGCrypt uses such a
subgroup -- this seems not the best practice. I would like to raise
this as an issue to discuss -- whether it is really using a secure
subgroup for ElGamal.

The group for ElGamal. In non-curve case, we use a multiplicative
group with modulus $p$, where $p$ is a safe prime.

In cipher/primegen.c, the function _gcry_generate_elg_prime calls
prime_generate_internal to generate a safe prime group, and also the
generator.

It seems to return the generator for the multiplicative group with
modulus $p$, not a special subgroup -- while the DDH assumption only
holds in this subgroup.

In the Wikipedia
(https://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption),
it said that DDH assumption does not hold for this group.

But DDH assumption is crucial for the semantic security of the ElGamal
algorithm. If we are using a generator for group modulus $p$, it is
not strongly secure.

Professor Dan Boneh from Stanford University said this in his paper
"The decision Diffie-Hellman problem" in Section 4.1
(http://crypto.stanford.edu/~dabo/abstracts/DDH.html):

       When $g$ is a generator of $Z_p^*$ the system is not semantically secure.

while semantical security is the foundation of security encryption schemes.


The general treatment. Instead of letting $g$ be the generator of
$Z_p^*$, we let $g$ becomes the generator of a subgroup of $Z_p^*$.
This subgroup has the prime order.

In prime_generate_internal, the prime $p$ is given as $p=2(q f_1 f_2
... f_n) + 1$, where $q$ as the prime with a sufficient size.

If we have a generator $g_0$ in $Z_p^*$, we can have
$g=(g_0)^{(p-1)/q_f}$ which is the generator of a prime group. In this
group, DDH assumption is believed to hold.


Cannot find relevant code in libGCrypt. In cipher/elgamal.c, we have
the key generation function generate, which uses the generator $g$
directly from _gcry_generate_elg_prime. This function is defined in
cipher/primegen.c. This function directly calls
prime_generate_internal, which is in the same file.

Before Ln 624, the code of prime_generate_internal, it is about
finding a safe prime and returns its factors (this is helpful because
finding the generator/primitive root becomes probabilistic
polynomial-time). Starting Ln 629, we start to test the candidate
generator. It seems that we are finding the primitive root of the
group modulus $p$, not the subgroup.


My question. Many open-source implementations of ElGamal do not jump
to this subgroup. But DDH assumption holds only in these subgroups.

1. [Correctness of my code reading] Is it due to my misunderstanding
of the code and I made it wrong -- that libGCrypt is surely finding
the good generator for that subgroup?

2. [Should we improve?] Why not prefer a better generator?


Thanks a lot for reading!

Sincerely,
Weikeng

-- 

Weikeng Chen @ 795 Soda Hall