Just to clarify things for William Geiger, I was not speaking of a PGP
PKI in a formal sense, but rather in a de facto sense. There is a PGP
PKI, and there has been for some years. It was the first widely deployed
PKI. I was merely acknowledging this fact, and making some educated
guesses as to how this de facto PKI would behave if we deploy software
that supports this OpenPGP spec. There is no need for us to get involved
in any formal discussions of how to standardize on a PGP PKI.
On other matters...
At 13:12 +0200 6/3/98, Ulf Möller wrote:
PRZ wrote:
If discrete logs prove to be a solvable problem, both DSA and
ElGamal will fall, as well as DH encryption.
As you probably know, discrete logs are a solvable problem, the
difficulty of which is a function of the key size. You fail to
consider the effect of progress in algorithms to efficiently compute
discrete logarithms.
I did not fail to consider that. In fact, that is precisely what I
meant by "solvable" -- that it becomes *feasibly* solvable. I was
using a shorthand expression that I thought would be acceptable to
crypto colleagues.
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.
Then we need a specification, and a notice from the DSA patent holder
(NSA) that they have no objections against this use.
There is no time to expand DSA in time for this OpenPGP spec. I thought
we could do it later. I don't think NSA would object. I talked with
some NSA crypto people at Crypto97 about this.
We already know how to expand DSA. We know how big to grow p and q,
how to keep them well balanced. It's only the lack of a larger hash
that kept us from doing that in PGP software. The lack of a larger
hash affects DSA and ElGmal signatures equally. If this lack is cured,
it would be applicable to both signature schemes.
Since the DH patent is now expired, that opens the door for free
unencumbered public key cryptography, creating a level playing
field.
You seem to imply that the DSA is not covered by patents. That again
is wrong. Please refer to the past discussion on the Kravitz patent
on DSA, and Schnorr's US patent, which the owner claims covers DSA and
which has not been challenged in court.
The legal burden of challanging RSA's claim (that Schnorr covers DSA)
in court rests on RSA, not on the rest of us. It is up RSA to challange
anyone else in court over DSA usage, and that has not happened. No one
but RSA believes that the Schnorr patent covers DSA. Many software
products that implement DSA, including PGP, will be commercially deployed
by many vendors, without any patent licensing from anyone. NIST indemnifies
anyone who implements it for the government, and Cylink indemnifies their
customers as well. I didn't think we needed to debate the patent status
of DSA here. Obviously we are going ahead with DSA deployment along with
everyone else. Surely you are not suggesting that we not deploy DSA
(oops-- too late for that!).
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.
Netscape, SecuDE and several others fell into one of the pitfalls that
are so easy to fall into by fielding crypto implementations with
fatally flawed PRNGs. RSA has been done wrong. Your poing being
what?
"RSA has been done wrong"? I see no mention of RSA in the above paragraph
that you quoted.
When I was at Eurocrypt97, 3 or 4 well-respected cryptographers approached
me and asked me (with concern in their voices) if PGP's use of ElGamal included
signatures. In other words, when they heard that PGP 5.0 was using ElGamal for
encryption, they immediately raised doubts about PGP's quality if PGP were to
use ElGamal for signatures as well. This is because they were concerned that
there were ways to get it wrong. If we had been using ElGamal for signatures,
I would have made sure we were doing it the right way, and I would have told
them that. But that would require me to talk with each and every cryptographer
who harbors such doubts and assure him that we did it right. They did not
express such doubts about DSA. They just assumed that we would do it right
if it were DSA. It's not enough that PGP implement ElGamal correctly. It is
also necessary that all the cryptographers believe that we all (all of the
various OpenPGP implementors) did it correctly.
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.
It is not a bad algorithm. If you feel that your company is not
capable of implementing it properly, well, don't do it. Others can
avoid all known weaknesses and provide their users with a useful
algorithm.
Of course we can implement it correctly. It was only in experimental
code that should not have been released that there was a flaw in our
implementation. We ifdef'ed it out, and so should not be judged on it.
Providing users with a useful algorithm should not be the point. We can
add hundreds of variants of discrete log signature algorithms to PGP.
Why not support them all? They are all useful. Why not add Rabin's
algorithm on the factoring side as well? Because there is no need to.
We don't need more algorithms unless they bring something unique to the
table. Having one PK algorithm based on factoring and one based on discrete
logs is enough. Even though EC is also based on discrete logs, we can
add it when we need to because it's much easier to compute on cheap
processors.
There will be harm done to the deployed PGP PKI if large numbers of ElGamal
signature keys get deployed, even if there are no weaknesses in the
implementations. The signatures are much bigger than DSA, without any
additional benefits that would not apply equally to DSA. If you want
bigger signatures, we can expand DSA, and get more bang for the buck.
More strength for fewer bits in the signature. But I would prefer not to
hold up the spec, so can we wait until after the RFC is issued before we
do that?
How about this. Let's deploy the standard with just the 1024-bit DSA,
and say "SHOULD NOT" on the ElGamal algorithm, but leave it in. That
will inhibit its deployment. After the standard is out, we can then
immediately start work on expanding DSA the right way. If we succeed
in that, we can meet everyone's needs with a bigger DSA, and issue a
revision that includes that and deprecate ElGamal.