Attack on libgcrypt's ElGamal Encryption with Proof of Concept (PoC)

[Ben McGinnes]

On Wed, Feb 07, 2018 at 12:14:46AM -0800, Weikeng Chen wrote:
> I am Weikeng Chen from UC Berkeley. This post is joint work with
> Erik-Oliver Blass from Airbus.

Hmmm, let me see if I'm following this correctly ...

> Libgcrypt is one of the very few cryptographic libraries that
> implements ElGamal. In the homepage, we see "Libgcrypt is a general
> purpose cryptographic library."

Correct.  Libgcrypt is a general purpose library, but that does not
mean that every algorithm, cipher and/or hash in it is general purpose
or ever intended to be implemented that way.  For instance it also
contains Serpent, a popular and strong cipher used with disk and
volume encryption, but you won't find it in the OpenPGP implementation
of GPG.

The correct application of any of the algorithms to be found in
libgcrypt is still determined by the projects which include libgcrypt
as a dependeny, not libgcrypt itself.

> ElGamal is a cryptographic algorithm with efficient multiplicative
> homomorphism, the ability of self re-randomization, and the support
> of key splitting. Its applications include voting, mix-nets,
> shuffling, etc. I am glad that libgcrypt implements this algorithm.

You're not the only one glad of it.

> However, handling the ElGamal is hard. The ElGamal implementation is
> not secure for general purposes. If we use libgcrypt to encrypt
> messages directly, rather than using for hybrid encryption, the
> security can be broken.

This is not new, it is well known and is, in fact the reason why
El-Gamal has only ever been implemented as an assymmetric cipher
within the OpenPGP specification.  Even when first implemented in
OpenPGP in the late 1990s it was always paired with DSA, first DSA-1
and subsequently DSA-2 when vulnerabilities were found in the former.

For instance, you will never see a signing or certification El-Gamal
key in any of the OpenPGP formats.  You will only ever see it as an
encryption only subkey; mostly with DSA certification keys, but
occasionally with RSA certification keys.  Indeed, if you verify the
OpenPGP signatures on this list and thus import the relevant keys you
can see one as you read this message.

> We prepared the attack on the Github:
> https://github.com/weikengchen/attack-on-libgcrypt-elgamal

Yeah, speaking of which, I noticed you also cited a similar attack
targeting the El-Gamal implementation in the PyCrypto library.

You are aware that PyCrypto is a dead project and no longer
maintained, right?

In fact it hasn't been maintained for several years.  Most mainstream
Python development requiring a cryptographic module now uses the
cryptography.py package instead and the original PyCrypto developer
has moved on to contributing to that project.  Though some also use
the NaCl package, which leverages libsodium to implement Daniel
Bernstein's elliptic curve implementations.

> The wiki page for explanation:
> https://github.com/weikengchen/attack-on-libgcrypt-elgamal/wiki/Attack-on-libgcrypt's-ElGamal-Encryption-with-Proof-of-Concept-(PoC)

We'll certainly take a long hard look at it, though I think I'll defer
to Niibe on this one, his maths and cryptographic skills are sharper
than mine.

> Suggestions: I would suggest libgcrypt to consider either one of two
> things as follows.
> 
> (1) Announce on the manual that ElGamal in libgcrypt should *only be
> used for hybrid encryption*:
> https://gnupg.org/documentation/manuals/gcrypt/Available-algorithms.html#Available-algorithms

The document you cite is essentially an index of what's in the
library, it is quite accurate.

> This prevents new libgcrypt's users from possible misuse of the
> ElGamal implementation for the purposes not considered by us.

This would be better served by a separate guide for developers
explaining these things as relevant for all the ciphers and hashes in
the library than singling out any one at the expense of others.  More
and more accurate documentation is always better than less.

> (2) Consider the implementation of ElGamal with semantic security,
> which would better be another algorithm in addition to current
> ElGamal.

Again, this draws back to the use of any given component of libgcrypt
in other projects, including GnuPG.  In that particular case, of
course, there is an additional algorithm used at the same level of
operation: RSA.

> One problem is about current ElGamal's prime generation. It is hard
> to make the current prime generation, which is fast, secure.  There
> is a reason to find p=2q+1 where p and q are both primes.

This is definitely where I'd ping Niibe for his opinion.  If and/or
when he has the time for it.


Regards,
Ben
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: not available
URL: <https://lists.gnupg.org/pipermail/gcrypt-devel/attachments/20180217/6de73bfc/attachment.sig>