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

[Weikeng Chen]

Hi Ben,

Pardon me for the short reply. Recent I got crazy with some other stuff...

(1) For the PyCrypto, we actually attack PyCryptoDome
(https://www.pycryptodome.org/), which is currently maintained by
Helder Eijs. We extend our results to PyCrypto.

(2) It would be fine for signatures. But the problem is when we use
ElGamal for encryption, the confidentiality has problems! Exactly as
what you point out.


RSA is still not perfect -- it does not support multiplicative
homomorphism when we want security.



On Fri, Feb 16, 2018 at 4:36 PM, Ben McGinnes <ben at adversary.org> wrote:
> 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



-- 

Weikeng Chen @ 795 Soda Hall