[NEWS] GnuPG's ElGamal Signing Keys Compromised

From: SecuriTeam (support_at_securiteam.com)
Date: 11/30/03

  • Next message: SecuriTeam: "[UNIX] GNU Screen Buffer Overflow (Negative Size)" 
    To: list@securiteam.com
Date: 30 Nov 2003 13:51:42 +0200

    The following security advisory is sent to the securiteam mailing list, and can be found at the SecuriTeam web site: http://www.securiteam.com
    - - promotion

    The SecuriTeam alerts list - Free, Accurate, Independent.

    Get your security news from a reliable source.
    http://www.securiteam.com/mailinglist.html

    - - - - - - - - -

      GnuPG's ElGamal Signing Keys Compromised
    ------------------------------------------------------------------------

    SUMMARY

    Phong Nguyen identified a severe bug in the way GnuPG creates and uses
    ElGamal keys for signing. This is a significant security failure which
    can lead to a compromise of almost all ElGamal keys used for signing.
    Note that this is a real world vulnerability which will reveal your
    private key within a few seconds.

    Please take immediate action and revoke your ElGamal signing keys.
    Furthermore you should take whatever measures necessary to limit the
    damage done for signed or encrypted documents using that key.

    Note that the standard keys as generated by GnuPG (DSA and ElGamal
    encryption) as well as RSA keys are NOT vulnerable. Note also that
    ElGamal signing keys cannot be generated without the use of a special flag
    to enable hidden options and even then overriding a warning message about
    this key type. See below for details on how to identify vulnerable keys.

    DETAILS

    Background:
    For historic reasons (The patent status of DSA was not clear when Werner
    started to write GnuPG back in 1997), GnuPG permits creating ElGamal keys
    which are usable for both encryption and signing. It is even possible to
    have one key (the primary one) used for both operations. This is not
    considered good cryptographic practice, but is permitted by the OpenPGP
    standard.

    It was not anticipated that these keys would still be used for signing
    because they have several disadvantages: The signature is much larger than
    a RSA or DSA signature, verification and creation takes far longer and the
    use of ElGamal for signing has always been problematic due to a couple of
    cryptographic weaknesses when not done properly. Thus Werner has always
    dissuaded people from using ElGamal keys for signing; however they are
    still used and about 200 keys per year are generated and uploaded to the
    keyservers.

    In January 2000, as part of version 1.0.2, the GnuPG code was changed to
    create ElGamal keys which work more efficiently for encryption (selecting
    a smaller x secret exponent and using a smaller k for encryption). While
    making this change the problem with signing keys was accidentally
    introduced: the same small k for encryption was also used for signing.
    This can be used for a cryptographic attack to reveal the private key
    (i.e. the secret exponent x) if a signature made using that key is
    available. Such a signature is always available for primary ElGamal keys
    because signatures created with that key are used to bind the user ID and
    other material to the primary key (self-signatures). Even if the key was
    never used for signing documents it should be considered compromised.

    Note that this weakness does not apply to the far more common encrypt-only
    (type 16) ElGamal key as GnuPG does not permit signatures to be issued by
    this key type. Only the ElGamal sign+encrypt key (type 20) is affected
    and then only when used to make a signature with a GnuPG version 1.0.2 or
    later.

    Impact:
    All ElGamal sign+encrypt keys (type 20) generated with GnuPG 1.0.2 or
    later must be considered compromised. Keys generated and used only with
    prior versions might still be safe but should ideally be revoked too.
    Note that even if an ElGamal sign+encrypt key was generated before GnuPG
    1.0.2, using that key in GnuPG 1.0.2 or later to issue signatures will
    still compromise the key.

    Again, ElGamal encrypt-only keys (type 16) from any version of GnuPG are
    *not* affected.

    Solution:
    Do not use *ElGamal sign+encrypt keys (type 20)*. Revoke all those keys
    immediately. Consider all material signed or encrypted with such a key as
    compromised.

    Forthcoming GnuPG versions will remove the ability to create such keys and
    the ability creates ElGamal signatures.

    How to detect ElGamal type 20 keys: ===================================
    We have to distinguish between two cases: The primary key is ElGamal
    sign+encrypt versus just a subkey is ElGamal sign+encrypt.

    The first case requires immediate attention, like this one:
      $ gpg --list-keys xxxxxxxx
      pub 2048G/xxxxxxxx 2001-xx-xx Mallory <mallory@example.net>

    such a key might be followed with additional "uid", "sig" or "sub" lines.
    Here an ElGamal sign+encrypt key is used and very likely created with
    GnuPG >= 1.0.2. The capital letter "G" indicates a ElGamal sign+encrypt
    key. REVOKE such a key immediately.

    The second case is about subkeys. Here is an example:
      $ gpg --list-keys 621CC013
      pub 1024D/621CC013 1998-07-07 Werner Koch <wk@gnupg.org>
      uid Werner Koch <werner.koch@guug.de>
      uid Werner Koch <wk@g10code.com>
      sub 1536g/ADF6A6E1 1999-02-20 [expires: 2002-11-01]
      sub 1536G/B5A18FF4 1998-07-07 [expires: 2002-07-06]
      sub 1536R/23D2A63D 2002-07-30 [expires: 2003-12-31]
        

    This Werner's usual working key, which is a standard GnuPG key with some
    additional subkeys added over time. It is a good example because one
    subkey was created as type 20 signing and encrypt ElGamal key. It is the
    second subkey:
      sub 1536G/B5A18FF4 1998-07-07 [expires: 2002-07-06]

    The capital letter "G" denotes such an possible compromised subkey whereas
    the first subkey:
      sub 1536g/ADF6A6E1 1999-02-20 [expires: 2002-11-01]

    Is a standard encryption-only subkey as indicated by the small letter "g".
     That key is not affected.

    The keys denoted with this capital letter "G" should be REVOKED unless you
    are definitely sure those subkeys were never used to create a signatures
    with GnuPG >= 1.0.2.

    How to revoke a key:
    To create a revocation certificate for the entire key (primary and all
    subkeys), you do:
     gpg --gen-revoke your_keyid >foo.rev

    If you have lost access to your passphrase, hopefully you have a
    pre-manufactured revocation certificate (either on a floppy or printed on
    a *** of paper) which you may the use instead of the above command.

    This revocation certificate should then be imported into GnuPG using:
      gpg --import <foo.rev

    Now export your key to a file and distribute it to the keyservers.
      gpg --export -a your_keyid >mykey.asc
      gpg --keyserver subkeys.pgp.net --send-keys your_keyid

    If your primary key is not an ElGamal key, you might need to revoke a
    subkey. Note again that only type 20 ElGamal keys (denoted by a capital
    letter "G") require revocation - the standard ElGamal encrypt-only key
    (small g) is perfectly fine. Use gpg's edit command like this:
      $ gpg --edit-key xyzxyzxy
      
    The key listing will be shown. Select the subkey you want to revoke, using
    the command "key 2" (or whatever subkey it is) and then enter the command
    "revkey" and follow the prompts. Continue then with an export as
    described above.

    How many keys are affected?
    Werner can't tell for sure. According to the keyserver statistics, there
    are 848 primary ElGamal signing keys which are affected. These are a mere
    0.04 percent of all primary keys on the keyservers. There are 324
    vulnerable subkeys on the keyservers, too.

    Some of the subkeys might have never been used for signing because for
    some time in the past GnuPG created the encryption subkey as type 20 but
    didn't used it for signing because the DSA primary key was used instead.
    It is better to revoke such keys nevertheless.

    Note again that the standard configuration of GnuPG does not allow
    creating the vulnerable sign+encrypt ElGamal keys and that neither DSA
    (type 17), RSA (type 1) nor ElGamal encrypt-only keys (type 16) are
    affected.

    ADDITIONAL INFORMATION

    The information has been provided by <mailto:wk@gnupg.org> Werner Koch.

    ========================================

    This bulletin is sent to members of the SecuriTeam mailing list.
    To unsubscribe from the list, send mail with an empty subject line and body to: list-unsubscribe@securiteam.com
    In order to subscribe to the mailing list, simply forward this email to: list-subscribe@securiteam.com

    ====================
    ====================

    DISCLAIMER:
    The information in this bulletin is provided "AS IS" without warranty of any kind.
    In no event shall we be liable for any damages whatsoever including direct, indirect, incidental, consequential, loss of business profits or special damages.

  • Next message: SecuriTeam: "[UNIX] GNU Screen Buffer Overflow (Negative Size)"

    Relevant Pages