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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/attachments/20170920/a2542cc4/attachment.html>