question on ElGamal implementation

Weikeng Chen w.k at berkeley.edu
Thu Sep 21 08:04:01 CEST 2017

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

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?

Sincerely,
Weikeng

--

Weikeng Chen @ 795 Soda Hall
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/attachments/20170920/a2542cc4/attachment.html>
```