I know I should have brought this up earlier, but better late than never.
I would like to suggest to the OpenPGP Working Group that we remove ElGamal
signatures from this draft RFC. Here's why.
First, I see no reason to add ElGamal signatures to the standard. I have
to admit I didn't follow the traffic on this list when this type of
signature was introduced, but I can imagine some of the reasons that one
might have for introducing them into OpenPGP. Let's review them.
1) Adding a new public key algorithm is good, in case the others are later
discovered to have weaknesses.
I disagree. ElGamal signatures are no better than DSA signatures. They
are similar in that they both rely on the difficulty of computing discrete
logs. If discrete logs prove to be a solvable problem, both DSA and
ElGamal will fall, as well as DH encryption. Indeed, DSA is a variation
on ElGamal. Thus, ElGamal signatures offer no real algorithmic diversity.
2) DSS is only 1024 bits max, while ElGamal can be bigger and thus stronger.
Again, wrong. The strength of the Digital Signature Standard is a function
of the size of prime p (1024 bits), the smaller prime q (160 bits), and the
underlying hash function SHA (160 bits). Making p bigger than 1024 bits
does no good to add to the strength of the DSS unless q is also made larger
than 160 bits. But making q bigger doesn't really pay off unless the hash
grows by the same amount. In fact, the DSS is balanced so that the work
factor for attacking p is about the same as the work factor for attacking q.
There is a square root attack on q (about 2^80 operations). There is also a
birthday attack on the 160-bit hash, regardless of what the hash algorithm
is. That would also entail a work factor of about 2^80. This means that
unless we find a bigger hash, we gain little by making p or q bigger in
the DSS.
It would be reasonable to point out here that it is likely to be operationally
harder for an attacker to exploit a birthday attack on the hash in a real
world situation. He has to trick the target of the attack into signing
a message that has the same hash as the desired forgery. Still, we must
try to design our systems to resist that attack, even if it is less likely.
Even if you think that a birthday attack is infeasible in your situation,
and would rather put your defenses into beefing up the size of the public
keys, it would be just as easy to expand the p and q parameters of DSS as
it would to expand the parameters of pure ElGamal.
I would like to find a suitable hash of perhaps 192 bits or better yet,
256 bits, thus opening the door for expanding q and p beyond 160 bits
and 1024 bits. But I think that any such candidate hash would have to
be extensively peer reviewed before acceptance into OpenPGP, lest it
suffer the same fate as MD4 and MD5.
3) Adding more public key algorithms is good, because more features is
always better.
Well, that one is so silly that I should not have included it. Each
public key algorithm should be justified on its merits. It should bring
something to the table that the other algorithms do not bring.
We added DH/DSS because of the RSA patent regime, which has for many
years stunted the growth of public key cryptography. Indeed, the RSA
patent and the patent cartel that once controlled all the public key
algorithms has done more to stifle this technology than all that the
NSA has done. Since the DH patent is now expired, that opens the door
for free unencumbered public key cryptography, creating a level playing
field. No longer can any companies be shut out of the game.
We probably will be able to justify adding elliptic curves at some point,
because they allow cheap 8-bit microcontrollers to compute and check
signatures because the computing requirements are so much less. This
is good for really cheap smartcards or tokens, a substantial economic
advantage.
But straight ElGamal signatures offers no new real capability. It brings
nothing new to the table. In fact, it actually has real disadvantages.
The first disadvantage of ElGamal compared with DSS is that ElGamal makes
much bigger signatures. Have you noticed that DSS signatures are so much
more compact than RSA signatures? They are only about one and a half lines
of radix64 characters. I think that is really cool. We lose that if we
go to pure ElGamal signatures. That will bloat the public key infrastructure,
as each key collects many signatures on it from other keys. It will
bloat everything that gets signed.
Another disadvantage is that ElGamal requires more computation than DSS,
in part because all the calculations are done in a larger field. DSS does
a substantial amount of its calculations in the field of q, which is 160
bits. That's why it's faster.
Another important disadvantage of pure ElGamal is that a number of attacks
and weaknesses have been published that apply only to pure ElGamal
signatures. These attacks and weaknesses do not apply at all to DSS, nor
do they apply to DH encryption.
In principal, an especially careful implementation could avoid these
weaknesses. But at least one implementation of OpenPGP's ElGamal signatures
has done it wrong. Others might also do it wrong. PGP users should not
have to lie awake at night wondering if the implementor did a perfect job,
or did he fall into one of the pitfalls that are so easy to fall into.
In short, ElGamal signatures are bigger, slower, and in many cases less
secure, than DSS. It is inferior in every way to DSS. It does not belong
in the OpenPGP standard. PGP stands for quality, and so should OpenPGP.
Of course, one might point out that ElGamal is not a required algorithm in
the OpenPGP standard. Thus, implementors do not have to support it, so there
is no problem. I must disagree here too. Some implementors will implement
it, in fact, some already have. In the arms race of feature competition,
algorithm implementation shows up as more checkboxes for sales brochures and
product reviews. It does not matter that it is a bad algorithm, reviewers
will compare products in such a way as to make it look better if you implement
ElGamal signatures. Market pressure will thus ensure that it gets implemented
in most OpenPGP-compliant products. That will include user interfaces that
allow the user to generate keys in that form. Are you going to make your
keygen wizard warn the user that he is a moron if he chooses to generate
his keys for ElGamal signatures? I doubt it. The users will begin generating
millions of keys in that form, and we will have a substantial part of the user
population doing The Wrong Thing. ElGamal signatures will begin to accumulate
on other people's keys, including DSS keys. We will all be penalized for this,
costing us all more compute time to check the signatures, more bulk
accumulating in our signature collections on our DSS keys.
If anyone breaks an ElGamal signature because it was improperly implemented,
the reputation of the whole OpenPGP standard will suffer. It will not matter
that it was only one implementor that did it wrong, the whole community will
take the hit. I hold in my hand a NY Times piece by John Markoff from 31
March,that is headlined "Powerful New Encryption Standard Delayed by a
Weakness", which reports on the weakness found by Biham and Knudsen in an
obscure variant of 3DES that was being used by X9F1. One of my clients who
was considering 3DES for an application sent me the article with a panicky
note asking me if this was a threat to PGP's use of 3DES, or to his own
application. I had to assure him there was no danger, because we were not
using this variant. In his mind, the entire 3DES standard was called into
question because of the cloud raised by this article. We could all be
similarly haunted by any weaknesses found in any implementation of ElGamal
signatures in any OpenPGP product. In fact, even if no one improperly
implements ElGamal signatures in any OpenPGP product (despite the fact that
this has already happened), there will always be doubts raised when mainstream
lay journalists (or lay users) rediscover any of the old academic papers that
have reported on weaknesses or attacks on ElGamal signatures. We will find
ourselves having to explain this away, over and over again.
It's noteworthy that the X9F1 committee was in the final call for its draft
standard when Biham and Knudsen discovered this flaw. The draft was changed
accordingly. It's not too late for us to change our draft as well.
I'm sorry to not have brought this up earlier, but I hope that the arguments
stand despite my tardiness. I also hope that those of you who have already
implemented ElGamal signatures (because it's been in the draft for so long)
will not allow the investment that you have made in software implementation
to prejudice you too much in deciding what is best for the PGP user
population to be subjected to.