[SUGGESTION NEEDED] A request for suggestion on furthering the discussion over ElGamal

[NIIBE Yutaka]

Hello,

Weikeng Chen <w.k at berkeley.edu> wrote:
> I am going to continue my post last month on the ElGamal in gcrypt. I
> am sorry to say gcrypt is the beginning of many wrong implementations
> of ElGamal. Some Github repo owners use this to show their
> implementation is correct. It uses a safe prime but the generator is
> still wrong. This makes the ElGamal not semantic secure.

Historically speaking, libgcrypt was factored out from GnuPG.  So, its
ElGamal API and the implementation are primarily intended to be used by
GnuPG.  In this context, it is perfectly OK.  I mean, "semantic
security" of the crypto system doesn't matter to the security of the
application.

> Niibe has mentioned that ElGamal used for hybrid encryption in general
> (which would be secure), but we two agree that we should improve.

I agreed that it make sense to improve the generator.  I don't think it
is mandatory.  I didn't mean introducing new or drastic change which may
impact existing usages.

> Some programmers may use ElGamal for homomorphic encryption and
> computation over encrypted data.

Interesting.  In that case, I wonder if current API of libgcrypt is
enough or good.  (I guess that... I don't think it's enough.)

> (1) Showing the current ElGamal implementation is not secure would be
> easy, as Wikipedia and some 17 years ago papers have some information.
> If we consult expert cryptographers in the field. They can clearly say
> the current implementation is insecure. --------- Do you think an
> experiment or proof-of-concept will be necessary?

If possible, please use careful wording.

The API of crypto library which implements crypto system lacking
"semantic security" property does not automatically mean "insecure".
For a library, its usage by an application matters.

> (2) Providing a corrected version is not trivial -- it is not just
> making the generator correct. We also need to embed the message (a
> binary string) into an element in a specific subgroup (and recovered
> later). There are many papers, and many years ago, to say some ideas
> about this encoding. One of that is my proposed solution.

You are talking about new crypto protocol, using ElGamal crypto system,
don't you?

> However, there is no official example. Even the original paper by El
> Gamal is not secure under this concern. Besides gcrypt, ---------- how
> to find a gold standard for ElGamal implementations? OpenSSL
> implements DH (also wrong but not a big deal in the real world,
> because it is for DH key exchange not ElGamal) ------ and one thing
> for sure, how to make it easy to follow in order to persuade a
> sufficiently large community to accept this change?

It seems for me that you have some confusions among:

	(1) ElGamal crypto system
	(2) crypto protocol which uses ElGamal crypto system
            --- e.g. OpenPGP
        (3) an implementation, in this case, partial implementation of (1)
            --- e.g. libcrypt
        (4) an application of (3) which implements (2)
            --- e.g. GnuPG

I would admit that libgcrypt API is not enough to provide full features
of ElGamal crypto system, for example, as you pointed out, it doesn't
provide "semantically secure" use case.  In other words, I could say,
libgcrypt's API for ElGamal just offers things needed for OpenPGP
protocol.

Actually, I think that "ElGamal crypto system" can refer different
crypto systems.  I think that your interpretation would be too modern,
and I'm afraid we can't find any existing (free software) implementation
which offers full features you'd like.

> (3) The solution will be incompatible with existing applications
> running ElGamal in gcrypt -- their ciphertexts will be undecryptable.
> ----- What is your opinion to deal with this?

If you are introducing new crypto protocol, old and new protocol can
co-exist, if designed carefully.


> My doubt on ElGamal encryption is a result of my cryptographic class
> CS276 at Berkeley. This page contains some reading
> (http://people.eecs.berkeley.edu/~alexch/classes/CS276-F2015.html).
> LEC NOTE 14 and PROB SET 4 have further information.

I think that you can ask your teacher.  That would be better.
--