[Urgent] GnuPG ElGamal keys compromised
Werner Koch
Hash: SHA1
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 bug is a huge security failure
and leads to a compromise of almost all ElGamal keys ever used for
signing. This is a real world vulnerability which will reveal your
private key within a few seconds.
Please *take immediate action and revoke you ElGamal signing keys*.
Furthermore you should take all other measures to limit the damage
done for signed or encrypted documents using that key.
I write to you because your key was been found on some keyservers and
to give you a chance to take action before an advisory will be published.
This mail is not encrypted in case that your key is not anymore usable
due to a lost passphrase. Please keep this information confidential
until the public advisory has been released or 10 days have passed.
This message is signed using the usual GnuPG distribution key;
available through "finger w...@g10code.com" or "finger dd...@gnu.org".
Please do not respond to this message as I won't have the time to
catch up with message of all the ~800 key owners affected by this bug.
I apologize for this severe bug and all the problems resulting from
it.
Background:
===========
For historic reasons (unclear patent status of DSA when I started to
write GnuPG back in 1997) GnuPG allows to create ElGamal keys which are
usable for encryption and signing. It is even possible to have one
key (the primary one) used for both operations. This is not good
cryptographic practice, but the OpenPGP standard allows for that.
It was not anticipated that those keys are still 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 ever been problematic due
to a couple of cryptographic weaknesses when not used properly. Thus I
have always dissuade from using ElGamal keys for signing; however they
are still used and about 200 keys per year are generated and uploaded to
keyservers.
In January 2000, 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
doing this change the problem with signing keys was accidently
introduced: The same small k as 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 done using that
key is available. This is always the case for primary ElGamal keys
because signatures created with that key are used to bind the user ID
and other material to the primary key. Even is the key was never
used for signing documents it should be considered compromised.
Note, that GnuPG uses by default an ElGamal key for encryption
which is internally denoted as type 16. This encryption-only key is
not affected because GnuPG does not allow to use this key to create
signatures. Only the ElGamal sign+encrypt key (type 20) is affected
and then only when created 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 are to be considered compromised. Keys generated with prior
versions might still be safe but should better be revoked too.
ElGamal encrypt keys (type 16) 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 have the ability to create those keys
and to create ElGamal signatures removed.
How to revoke a key:
====================
To creates a revocation certificate, 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 sheet 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
then 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
Thanks
======
Phong Nguyen analyzed the implementation of GnuPG's cryptographic parts
and found this vulnerability. He also developed actual code to mount the
attack and was so kind to give me enough time to have a look at his
paper and to gather a list of known type 20 keys owners.
I am really sorry for this,
Werner
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)
iD8DBQE/xGjqaLeriVdUjc0RAk6YAJ9PmCGCfVCCovOEaQ2cDHpfibcPKQCdFr9g
PL1VAjx+Fr/w1h631mrXg9I=
=CJDW
-----END PGP SIGNATURE-----