Subject: Re: Removing Elgamal signatures

From: Lutz Donnerhacke <[email-masked]>
Date: Mon, 1 Dec 2003 14:45:08 +0000 (UTC)

* Werner Koch wrote:
> In the light of the recent GnuPG bug, where I accidently used the same
> small sized k for signature creation as it is used for encrypting, I'd
> very much like to drop the ElGamal signing ability all together from
> OpenPGP.  AFAIK, GnuPG is the only implementation with support for
> these keys and by now the about 1100 known primary and subkeys should
> have been revoked.  Thus there won't be any interoperability problem
> anymore.

I'd like to oppose. ElGamal signatures are still useful, despite there is a
charge of signatures with some algorithmic errors. I'd prefer a paragraph
describing the problem and advicing to not use keys of this charge.

> If we can't agree on that, I'd suggest to declare type 20 keys to be
> Elgamal sign only - this way a new problem with this algorithm will
> at least not affect the encryption use.

It's only the parameter k, right? Type 20 keys are not limited to the small
parameter.

---

From: David Shaw <[email-masked]>
Date: Mon, 1 Dec 2003 11:58:12 -0500

> have been revoked.  Thus there won't be any interoperability problem

I agree with this.  Not too long ago, we removed a handful of unused
hash algorithms from the standard using the "less is more" rationale.
I see this as a similar case.

David

---

From: Ian Grigg <[email-masked]>
Date: Mon, 01 Dec 2003 14:48:17 -0500

> describing the problem and advicing to not use keys of this charge.

Thinking about the case for removing ElGamal from the
standard, here are the pluses that I see:

  a. The purpose of the standard is to document the greater
  good set of common and useful algorithms to which most
  implementation should try and implement.

  If there are O(1000) users of the ElGamal signature
  algorithm, I'd say at first glance this does not qualify
  as a major usage.

  Also, if GnuPG is the *only* implementation of this,
  then that would seem to go against the spirit of the
  "two implementations" rule.  (Although, not breached
  in practice, as it is only a small part, I would guess.)

  b. Removing it from the standard would only mean that other
  implementations could then totally ignore it, instead of
  choosing to ignore it.  Also, removing it from the standard
  does not mean it can't be used - it just means that it is
  then a private algorithm.  If it later on proves to be
  of great use and other implementations adopt it, it can
  always be added back into a future version, or written
  into a informational draft.

  c. Some change has to be made, because there is a bug.  So
  it might simply be a balance between removing it - easy? -
  and writing in the bug-fixed-text - not so easy?

  d. Less is much better.  OpenPGP is already way too big and
  complex, which slows its implementation and thus slows
  its use, and its long term success.

Against the removal:

  A. This is supposed to be very late in the game for the
  production of the standard.  There should be very minor
  changes, if any.

On balance, there seems to be a good case for removing it
entirely!

( I speak here without any knowledge of the technical aspects
of the algorithm, of course!  Standard Dilbert comments
apply... )

One thing I am not sure of - what is it useful for?  In the
sense, does it do something that is highly prized and wanted?

That would perhaps be key in determining if removal is to
be warranted at this late stage...

iang

---

From: David Shaw <[email-masked]>
Date: Mon, 1 Dec 2003 16:38:48 -0500

>   in practice, as it is only a small part, I would guess.)

With regards to this point - very shortly, GnuPG will not be an
implementation of this.  The upcoming GnuPG (1.2.4) does not allow
users to do anything with Elgamal sign+encrypt keys except revoke
them.  It will not encrypt to them, it will not sign with them.  The
next large release (1.4) will not implement Elgamal sign+encrypt at
all.

> sense, does it do something that is highly prized and wanted?

In the past it was a patent-free signing algorithm that wasn't limited
to a 1024 bit key and a 160 bit hash.  Given that the RSA patent has
expired, I see little benefit to Elgamal signatures that RSA
signatures do not provide, and at the same time there are some
significant advantages to RSA (like speed.)

David

---

From: Ian Grigg <[email-masked]>
Date: Mon, 01 Dec 2003 16:54:04 -0500

Ian Grigg wrote:
> >   c. Some change has to be made, because there is a bug.

Correction supplied by Micheal Young:
> The bug is in the GnuPG implementation, not the specification.

Thanks!  Delete c. then.

> [I'm neutral on whether to keep ElGamal signatures in the
> specification, but I wouldn't consider this a compelling factor.]

iang

---

From: Jon Callas <[email-masked]>
Date: Mon, 1 Dec 2003 21:05:28 -0800

I'm happy to remove it, if there's rough consensus that it be removed, 
myself. I just want to make sure that there is that consensus.

Elgamal sigs have been controversial from the start.

The main reason for them is to have a discrete-log public key system 
that parallels RSA in being able to both encrypt and sign. We've always 
known that Elgamal signatures were tetchy, and 2440 has finger-wagging 
in that direction, anyway.

In 1998, there was more reason to have a discrete-log encrypt+sign key 
than there is in 2004. There's very little reason to have them today.

Lutz has stated a preference for them remaining, but with exactly zero 
implementers of it, that sounds like something resembling rough 
consensus to remove them.

If we *don't* remove them, then they are part of the standard, but an 
interesting part of the folklore. If a brand new implemented came to me 
and asked about them, I'd reply something like the following:

"I don't see why you should implement them. They're a MAY, which means 
you don't have do. All signature algorithms are tetchy in that if you 
don't do them right, bad things can happen, but Elgamal sigs are even 
tetchier. The only people who did implement them removed them after 
some exasperating bugs showed up. If you implement them, then you have 
to make sure you don't put in some weird bug. If you do, people will 
say, 'I told you so.' If you do, anyone with a different implementation 
can't verify a signature -- you're the only one who does. I see a lot 
of bother for you and not much benefit. There are much better things 
for you to spend your time on."

I then hear in my head, "So why didn't you remove them from 2440+ when 
you had the chance? If they're such a pain that no one does them, why 
are they there at all?"

I don't have a good answer to that question. I say remove them, myself.

	Jon

---

From: Florian Weimer <[email-masked]>
Date: Thu, 4 Dec 2003 23:51:35 +0100

Lutz Donnerhacke wrote:

> I'd like to oppose. ElGamal signatures are still useful,

Useful for what?

In the past, your primary argument seems to have been the avoidance of
DSA (not because of patent problems, but because of rather theoretical
objections to its design process), but this is no longer a convincing
justification since we now have RSA at our disposal.

> despite there is a charge of signatures with some algorithmic errors.
> I'd prefer a paragraph describing the problem and advicing to not use
> keys of this charge.

Are you confident that no additional implementation traps will
discovered?  With RSA, I have some confidence that the most important
things are properly documented, but ElGamal signatures appear to be much
more problematic.  Please keep in mind that this is the second case of
such an implementation trap for the ElGamal signature scheme.

---

From: Lutz Donnerhacke <[email-masked]>
Date: Fri, 5 Dec 2003 11:49:34 +0000 (UTC)

>> I'd like to oppose. ElGamal signatures are still useful,

I prefer more than one algorithm for a given task. That's all.
My personal opinion is not relevant to the removal of this packet type.

> justification since we now have RSA at our disposal.

Do we use RSA right? Requiring SSP?

> such an implementation trap for the ElGamal signature scheme.

There are a lot of listed RSA attacks, too.