[ale] GnuPG and ElGamal...

[Michael H. Warfield]

Hello all...

	Last year I gave a talk on PGP/GnuPG with a follow-up keysigning
party a few months later.

	In that talked, I mentioned ElGamal and the DSA/ElGamal
keys used by PGP and GnuPG.  I mentioned that there were several
disadvantages to using ElGamal for signing or for signature keys
(primarily, the performance of such keys majorly sucks and the signatures
are huge).  This is why GnuPG and PGP use ElGamal for encryption and DSA
for signatures.  You could create ElGamal sign and encrypt keys with the
"expert" option and override a warning, but it's not normally a visible
option.

	We've just been handed another REALLY MAJOR reason to not use
ElGamal for signatures.  Warner Koch has announced that, due to a change
in the way GnuPG implimented ElGamal in GnuPG 1.0.2, a flaw was introduced
to ElGamal signatures which could readily lead to the compromise of the
secret key.  If it was a combination Encrypt/Signing key, then your
encryption key is compromised as well.

	http://lists.gnupg.org/pipermail/gnupg-announce/2003q4/000276.html

	The details are that certain internal numbers were choosen for
ElGamal which optimized the algorithms for encryption but don't impact
the security of the encryption.  Unfortunately, these same values were
choosen when the algorithms were used for signing and these values result
in very WEAK signatures.  Weak, not in the sense that they can be forged,
but weak in the sense that the secret used to derive the key can be
determined.  The ElGamal algorithms are highly asymetrical (which is why
signature verification is an order of magnitude worse in performance and
the signatures are so grossly large) leading to this skewed compromise.

	What's really nasty is that the bad values are not part of the
key itself but are ephemeral values used in the algorithm.  That means
that, even if you had good secure ElGamal keys from earlier version,
if you USE and ElGamal key to sign with recent versions of GnuPG, no
matter when the key was created, the key is now compromised by the existance
of that weak signature.

	This doesn't affect RSA keys nor does it affect standard
DSA/ElGamal keys.  It ONLY affects the ElGamal signature keys, which
can only be generated in expert mode.

	Recommendation is that ALL keys of type 20, ElGamal Sign and Encrypt,
be revoked.  If an ElGamal key is the primary signature key, then the
public key is already selfsigned with a signature that is capable of
compromising the private key!

	All that being said...  There was not a single key at the keysigning
party that would have been affected by this announcement.  They were all
either RSA or DSA/ElGamal.  Guess nobody thought themselves wise enough
or expert enough to generate ElGamal sign and encrypt keys.  :-)

	This is really the main reason I wanted to post this to this list.
To give everyone a heads up and make sure everyone understands that the
STANDARD keys are NOT impacted by this announcement.  It's a very limited
class of keys (estimated at less than .04% of the keys on the public
keyrings).  You do NOT have to revoke your DSA/ElGamal keys.  These keys
are NOT affected.  Only ElGamal sign and encrypt keys are affected.  Those
MUST be considered compromised at this time.

	I'm going to print a copy of Warner's post and stuff it in my
copy of Applied Cryptography as a reminder of why cryptography is always
tougher than it seems.  :-/

	Mike
-- 
 Michael H. Warfield    |  (770) 985-6132   |  mhw at WittsEnd.com
  /\/\|=mhw=|\/\/       |  (678) 463-0932   |  http://www.wittsend.com/mhw/
  NIC whois:  MHW9      |  An optimist believes we live in the best of all
 PGP Key: 0xDF1DD471    |  possible worlds.  A pessimist is sure of it!
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 307 bytes
Desc: not available