On Tue, 2 Jun 1998, Philip Zimmermann wrote:
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.
I can also go back and plead for the OpenPGP WG to change lots of things
which I have been silent on and sent messages at earlier points. If you
want to open settled issues, I would like an equal chance to do so.
Generally I have remained silent about things settled in a manner which I
disagree with, and have actively participated and reviewed the
specification and several changes I suggested had been adopted. You
haven't even said you have read the spec, and the only other message I see
is from a week ago.
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.
There was a fair amount of traffic about this. Maybe you should read it
before you create a list of straw men from your imagination and mow them
down. Final call is supposed to be final call, and this is too large of an
issue to be this radically changed at this point.
In any case walking into a meeting at the last minute is rude. Walking in
like you own the place is ruder still. And then trying to overturn an
issue that was discussed and decided much earlier without even reviewing
the minutes is downright barbaric. But I will go over the old ground and
respond anyway.
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.
It is not a different genus but is a different species - ElGamal
signatures have weaknesses that DSA doesn't and possibly vice versa.
Schneier notes that there are thousands of variants possible given the
generalized equation used to create the signature. And the weaknesses in
ElGamal don't require the discrete log problem to fall, but only weak
parameters. Some of these may exist yet undiscovered in DSA.
2) DSS is only 1024 bits max, while ElGamal can be bigger and thus stronger.
Again, wrong. ...
Technically not. DSS can have P become larger than 1024 bits, but as you
point out that is not the weakest link and thus is irrelevant...
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
Tiger-192, which isn't yet completely analyzed is larger. There is a 256
bit variant of HAVAL. These don't work with DSS. Or even duplicate
hashes (place a RIPEMD160 and a SHA1 hash, or maybe two SHA1 hashes
drawn on different parts of the signed material).
I could also point out CAST. In fact the 5.0 versions I know about
default to using it and there is no way of overriding it. It is far newer
than 3DES or IDEA. DES/SK isn't even out yet as a reference
implementation, but is in the spec as a MAY.
If you would propose a strong-DSA with a larger q, I could accept it, or
even a double DSA signature. But no one has proposed any upward path from
DSA except ElGamal and they have had a long time to do so.
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.
So start reviewing. Has anyone at pgp.com done anything about Tiger,
Haval or even Snefru?
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.
ElGamal Signatures allow a single primary key to be used for both signing
and encryption. They also aren't limited to 160 bits on the size of the
material signed. These are the issues upon which the inclusion of ElGamal
turned. You might not weigh them as important, but then you weren't part
of the discussion when all the things you brought up were weighed.
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.
I have to bypass more junk in signature packets that any difference in
signature sizes is likely to be irrelevant. Now that the MPI is smaller,
we now have to change the signature structure because 64K is insufficient
for the hashed and unhashed material in a standalone packet. And more
bloat is coming to signatures with the next release.
If size was a concern, you would have split out a separate parameter
packet since it is likely that all PGP 5.0 1024 bit DSS and DSA keys have
the parameters in common, and then used a parameter ID and just the public
key.
And isn't someone over at PGP proposing including a picture within the
keyring material? Or other ID material?
Further, if you only have one primary DH key, you lose all the extra
overhead of the DSA key and the packet/subpacket binding.
If you are really serious about key infrastructure bloat, then you should
immediately look at and condemn the subpacket bloat already occuring.
And it sound more sincere if you didn't have things like cute but large
animations in your programs. How many printed volumes did the all the eye
candy take?
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.
And DSS requires a *lot* more than RSA which RSA.com often points out.
And it also explains why it is limited in the size of material to be
signed. And MD5 takes less than SHA1, but TIGER takes less than either.
I don't think anyone would use ElGamal except in two situations: 1. where
extra security is needed for signed material (thus signing multiple hashes
or a larger hash), or where space is at a greater premium (using a
param/pubkey infrastructure).
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.
A known weakness is not a weakness if it can be avoided. I haven't seen
anything on DSS, but does that mean that nothing exists? Or that it
hasn't been found or published?
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.
I know only of three implementations of ElGamal within PGP. One was
within PGP 5.0 and was "wrong", but it is what I used as a template and
have since fixed the flaws I was contacted about which were in the
original. No one has since contacted me about my implementation getting
it wrong (other than a note that I was too strict in one place and another
suggesting I look at some references about problems, and I replied that I
fixed those liste). The other one I know about is gnupg.
Maybe my implementation is the one you are talking about. If it is, then
it has been around for 6 months, and initally was #ifdef-ed so I could
easily have disabled or removed the code before the threads on ElGamal
signatures and incorporation into the spec. Remember that it was not a
light issue, and even has a different algorithm number for the key. I
pointed out some subtle errors in pgp 5.0 (not having to do with security)
and suggested corrections because I am interested in having better
products on all sides. I have had no contact from anyone pointing out any
specific problems in my implementation of ElGamal, so even I am left to
wonder. Anyone who has looked at the many releases I uploaded knows that
I don't get everything right.
If I got it wrong, I would like to know where so I can fix it. If I
didn't I would like to know that too. Or is PGP now going to play a game
of "guess which competitor has the problem - we know but aren't telling"?
If it is by request of the implementor that would be a different thing,
but you now have called into question every one of your competitors. Is
this how PGP is going to act now? Even if you haven't checked the other
impelmentations, you need to say that too.
Technically, my implementation won't interoperate with OpenPGP ElGamal
signatures - it generates ElGamal keys, but only with the DH-encryption
algorithm tag.
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.
Inferior in every way except two - it can use a single key for both
encryption and signing, and it can handle more than 160 bits.
... 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.
The switch from 2.6.x to 5.0 already bloated things far more than ElGamal
ever will. The key material is larger, and now I have to maintain two
keys, a 2.6.x for those who still only have the old version, and now a
DSS/DH to be trendy. And there is still the unresolved issue of a V3 v.s.
V4 RSA key since the IDs can differ in two ways, so I will need two
versions of my RSA keys to interoperate in addition to the DH/DSA stuff.
And I don't think your worries are warranted. I am still trying to find
SSL sites that use any form of DH instead of RSA for their public key
exchanges. More than enough older implementations don't interoperate with
ElGamal signatures that it won't be a factor.
Worse, there are lots more algorithms besides ElGamal. For example, the
elliptic curve encryption and signatures that aren't specified, so every
implementor is free to do the parameters and algorithms the way they
please. Why even put these in to this revision when there is NO
implementation that uses them? Technically it is the same with Blowfish
and Safer though they have multiple variants. Why leave these in since
they are the same "MAY" as ElGamal? And the extra hashes without OIDs.
If anyone breaks an ElGamal signature because it was improperly implemented,
the reputation of the whole OpenPGP standard will suffer. ...
...
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.
The original PGP published source contained disabled support for ElGamal
signatures and was broken. This code should have been removed, though I
may have been the only one to enable it.
As far as the panic by the public, every time any paper is published
anywhere on any algorithm, someone will say the entire crypto
infrastructure is broken. As you note, a single form of a single
algorithm was flawed, and you had to explain it didn't apply.
And I thought PGP would be the leader in OpenPGP. Regardless of what the
specification says, if you don't implement ElGamal, most people won't use
it specifically because the PGP Inc. version doesn't use it.
If PGP stands for quality, you should have the best implementation
(including *NOT* doing things you think are flawed), the best programs,
the best SDKs, and the best support. Quality is more than the algorithm
list.
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.
Except you have not discovered any new weaknesses - but only an
implementation error (which you aren't identifying). If there is a new
attack that would threaten the security of previously correctly
implemented ElGamal keys I would like to know and would agree.
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.
They will be subjected to Haval, Tiger, DES/SK (when it is available),
Blowfish, Safer/SK-128, MD2, EC (in whatever form), on the same basis as
ElGamal. Why include all these, but not ElGamal?
This late in the game, I would agree to changing the MAY to a SHOULD NOT
for ElGamal. I would even be willing to disable it by default in my code
in the same way that PGP 5.0 disabled support (after fixing it if mine is
the errant implementation). And I think the other implementors may agree
to do the same thing and do a moratorium on "enabled ElGamal" until the
next spec is released and we can then either delete it or place caveats
or come up with a way of extending DSA.
But I would want to leave the code and infrastructure in place until then,
and leave it in the spec.
Alternately we could leave the OpenPGP spec open for another few months to
let everyone get up to speed and we can reopen everything to make the spec
perfect.
--- reply to tzeruch - at - ceddec - dot - com ---