Wed Dec 20 07:38:44 1989
In this discussion of Kerberos and standards and public-key
encryption, etc, there seem to be a whole host of inter-related
but fairly separable issues. I am trying to come to an
understanding of this area. (I've got the task of coming up
with a strategy for secure protocols for the UK academic
community. These absolutely must be in line with the emerging
standards work, but must also allow us to interwork with our
colleagues in the USA.) The main things to understand at the
minute are the similarities and differences between the kerberos
approach and that embodied not only in X.509, but the other
efforts in at least four of the ISO layers (link, network,
transport, and application). However, lets not get diverted
into the sterile wastes of ISO vs the ARPANET stack - there are
other orthogonal issues that are of more fundamental interest.
Note that this message is aimed primarily of increasing my
own understanding of the issues, and hopefully, perhaps that of
other list members. I'm sure I've got hold of the wrong end of
the stick in more than one place.
1) Public Key vs private key "in principle".
Much is made of the fact that one of a pair of symmetric
keys can be "published", and thus much of the key
management problem apparently disappears. Unfortunately,
when you examine what "publication" involves, the issues
become much less clear. For most purposes, most people
feel comfortable about the authenticity of the published
telephone directory in its familiar paper form. However,
as a way of managing encryption keys this has several
1.1) Keys for new people must wait for the next printing.
1.2) Read any book about cryptanalysis and you soon learn
that the cardinal rule about keys is to change them
completely and often. How often is the "paper key
directory" to be printed?
1.3) To accommodate the need for change in telephone
numbers beyond that provided by the printed
directories some form of online system is oftem
provided. In France the PTT has gone a long way
towards completely replacing printed directories with
an online system (there are other complex reasons in
this case that are tangential to this discussion).
1.4) As noted recently on the list, revocation of
priviliges (keys) is difficult without electronic
management - do you dispatch hoardes of messangers
with erasers to delete a key from all the distributed
directories that should no longer be used?
In thinking about this I have always been lead to the
inescapable conclusion that "proper" key management must
lead inevitably, at least for a large and growing and
dynamic community, to some form of electronic publication.
If Electronic publication is necessary, and there is a need
for mutual authentication of both the publisher and the
client, then both public-key and private-key protocols
have, surprisingly, the same complexity (Kline and Popeck,
1979, Needham and Schroeder, 1978). Thus, argue Kline and
Popek, public key cryptology offers no advantage in
practice because to manage change you still need a server,
and once you have a server, private key cryptology is just
(If it is not necessary for the client to be authenticated
to the server (key-provider) then public-key methods
probably still have an edge. I'm not absolutely clear when
only one-way authentication is actually useful. Perhaps
for truly public data, but I suspect that the vast majority
of data is not truly public in this sense but is available
only on the payment of some money - like buying a newspaper
or some kind of subscription to the information source.
For example, my public library will lend me books without
charge, but only if they know I am a local resident, and
thus fund the library through my local taxes - i.e. I have
to authenticate myself to them.)
2) Public keys and "signatures".
The use of signatures depends even more than communication
and printed directories on the long term integrity of the
keys. Any "signature" is valid, only as long as the key
has not been compromised. Setting aside any technical
doubts, what about attacks along more conventional lines,
like hacking into one of the computer systems where keys
are stored, "borrowing" smart cards overnight, or the 1001
things nobody has yet thought about? In addition,
Tanenbaum has pointed out that the signor of a message
could compromise his own key (e.g. get his neighbor's
teenage son to post it on a bulletin board), and then
"repudiate" all the supposedly "non-repudiatable" (yuck,
what a word!) messages that he had issued.
I've not seen any suggestion of this in the literature, but
again one could imagine that just as one can have trusted
"authentication servers", one could also imagine trusted
"notary servers". Just as present public key protocols
sign messages by encrypting a message digest, the NS could
store these message digests (which would presumably also
cover useful headers like the time and date, name of
issuer, etc) and be prepared to verify them at any later
time. Such servers could use either public or private key
protocols when verifying or denying authenticity, though
the same properties are presumably still required of the
This is not an argument for or against one kind of
"signature" over another - it is meant only to point out
that here too there seems to be a duality between
public-key protocols and trusted servers in which the trust
placed in the public key algotithms and keys can be
compared with the operationally different but functionally
similar trust placed in a specialized server.
3) Number of Algorithms
I think that only the RSA algorithm (or mathematically
equivalent ones) survives as a public key algorithm.
Recently, work by Lenstra cast a shadow on RSA - it has
emerged only moderately weakened (I think???), but putting
all our cryptographic eggs on one single algorithm sounds
less than prudent to me.
On the other hand there are many private key algorithms.
Despite many years of examination and rumours to the
contrary, DES has not been cracked. Recently a "harder"
version of DES that is simultaneously more efficient in
software has slipped out through a wormhole in space.
4) RSA algorithms are very expensive in computer time.
However, much of this can be alleviated by combining slower
public key algorithms with faster private key methods. For
example, use RSA to send a DES key on the front of a
message, and then use the DES key to encrypt the the
5) RSA is patented in the USA (except for the Government and
Though individual fees are low, some organizations may have
problems either with the large total payment, or any
payment at all. In any case, the adoption of anything as
an international standard normally requires that it not be
proprietary. Recently I have witnessed a heated argument
between a representative of RSA Inc and the co-chairman of
an IEEE committee on this very point (i.e. if THEY can't
agree, I think this list would only be wasting its time
discussing this point - just lets note it).
Interestingly, this patent apparently only applies WITHIN
the USA, and use is free in the rest of the world. RSA Inc
still hopes to sell related computer programs outside the
USA, but it is not clear to me how this would avoid export
embargoes mentioned in the next point.
6) There are problems with exporting certain encryption
"devices" from the USA. The situation is complex, but
apparently applies to kerberos either with or without DES
modules. Does this apply to software produced by RSA Inc,
and if not, why not? (Yes, maybe I should read Alice in
Wonderland with my daughter over Christmas!)
Re-implementing the kerberos protocol may not be too
difficult for us foreigners - we are already knee-deep in
DES implementations :-)
7) The standards scene seems, quite sensibly, to be allowing
any encryption method to be a "parameter" (my word) - that
is to be chosen separately. I also believe that the choice
of public vs private key methods is also being left as open
as possible. The exception seems to be X.509 which is
likely to be revised when the rest of the security
framework gets filled in.
So far so good, but sometime a "functional standard" will
have to be chosen, and for open working everyone will have
to conform. It is not yet clear to me which way this will
go. However, at the Computer Security Applications
Conference in Tucson in December, there was a lot of talk
about public key cryptology and not much about private
keys. (Well, RSA Inc had a very persuasive speaker there,
but no-one who was there put the case for servers).
In addition, the Final Report of the Protection of
Logistics Unclassified/Sensitive Systems (PLUS) has
recommended the combination of public-key and DES. Another
development that is being widely discussed is the
specification of protocols for secure mail enshrined in
RFCs 1113 to 1115. RFC 1113 (in line with other standsrds
work) is specific neither about encryption algorithm nor
about the public vs private question, but RFC 1114 on key
management specifies public key methods of key distribution
Kline, C.S. and Popek, G.J. "Public vs. Private Key
Encryption" AFIPS Conference Proceedings 48 pp831-837 1979.
Needham, R.M. and Schroeder, M.D. "Using Encryption for
Authentication in Large Networks of Computers" CACM 21 p993 Dec
Tanembaum, A.S. "Computer Networks" Prentice-Hall International
ISBN 0 13 164699 0, 1981 (First ed.)
It would seem to me that present "interim" solutions that aim to
"intercept" ISO standards appear to be trying to keep their
options open, but are tending towards the adoption of
public-key, i.e. RSA methods. My reading of the background to
this that I have tried to set out in the early part of this
message makes me very uneasy. Is my unease justified - i.e.
should the "server approach" as best exemplified by Kerberos be
trying to influence the standards process more, or is the
Kerberos approach just an interesting diversion on the true path
to open working which will be supported by RSA-based protocols?
Sorry for the long message - A merry Christmas to all, and I
look forward to a lively and instructive (and constructive)
conversation in the new year!!!
Denis Russell JANET: Denis.Russell@uk.ac.newcastle
Computing Laboratory ARPA: Denis.Russell@newcastle.ac.uk
Claremont Road Tel: (+44) 91 222 8243
Newcastle upon Tyne Fax: (+44) 91 222 8232
NE1 7RU Telex: 53 65 4
daemon@ATHENA.MIT.EDU (RSA Data Security)
Thu Dec 21 17:38:59 1989
(RSA Data Security)
The debate over the use of Kerberos vs. RSA has been interesting to
observe. I feel that since so many posters have discussed what they
see as the cost of RSA, this post is appropriate.
Let's at least set the record straight. What has been proposed to
both CCITT and to NIST/OSI is a licensing proposal where the cost of
using RSA is $2.50 per user *one time*. People are confusing the use
of RSA in directory authentication with the cost of a certificate ala
RFCs 1113-5, which describe the cost of obtaining a *service*
(getting a public key certified, at $25 for a two year certificate)
Having a certificate for Internet Privacy Enhanced Mail has nothing
(at this time) to do with X.509. All cost assumptions thus far
posted are based on information that is 100% wrong.
It is not possible to address the differences between digital
signatures and Kerberos for authentication here. I would simply
suggest that any comparison should be made by someone who understands
certificate based key management. If someone really wants to
understand what public-key is and how it can be uses *and* how it
compares to symmetric systems, I suggest "The First Ten Years
ofPublic-key Cryptography," by Whitfield Diffie. It appeared in
Preceeding of the IEEE Vol. 76, No. 5, May 1988. It also may be
appropriate to ask members of the IAB Privacy Task Force why they
chose RSA over Kereberos (even though it costs money).
Back to X.509: Note that the $2.50 is typically paid by a vendor
building a directory product. Also consider the 1988 recommendations
in X.411 (many of which require digital signatures to accomplish) and
the $2.50 one time seems quite reasonable. This price has not changed
since our original proposal to CCITT in 1984. In the meantime, a
large number of companies have licensed RSA and are introducing
products that use it (Digital Equipment, Motorola, Lotus,
Racal-Milgo, Fischer International, Tektronix, Simpact Associates,
etc). Apparently these companies saw a reasonable way to purchase
licenses to use RSA; don't knock the process if you haven't tried it.
The people who complain the loudest about patents and licenses are
the ones who seem to know the least about them. There's an awful lot
of "hip shooting" on this subject. Anyone who wants to discuss this
further can send me E-Mail.
On the "alternative" signature scheme proposed by NIST/OSI: ElGamal
is a scheme that requires a license to use (it employs methods
covered in the patent on exponential key exchange). Unlike RSA,
there is no written guarantee of the cost of using the scheme, yet it
is named in the NIST/OSI documents. There is *no* public-key
cryptosystem we know of that is *not* patented. RSA is the only one
we know of to actually submit licenses with defined costs so that
standardization can be considered.
Standards allow for the adoption of *patented* technology
(proprietary is the wrong term for RSA in *this* case as used by
James Galvin; no proprietary issues exist, only patent issues - also
the "heated exchange" referred to was over the implications of naming
the RSA algorithm in the IEEE 802.10 SILS documents and had nothing
to do with proprietary/patent issues). ANSI even states that between
2% and 5% is a "reasonable" royalty for such things. Anyone
genuinely interested in understanding these issues should obtain and
read the related documents and publications.
Finally, the $2.50 amount *came from* CCITT and NIST/OSI. It is not
even our number; it is the number the representatives on the
standards committees insisted on in 1984 and again in 1989 and which
we agreed to!
No, I don't think the dollar cost of RSA is the problem. The
problems are (1) political and (2) mis and disinformation (our main
competitors are apathy and ignorance). While organizations in Europe
openly adopt and endorse public-key such as RSA (EFTPOS UK, with an
endorsement of RSA by the NPL, or National Physical Laboratory), our
own government has been strangely silent in the area of public-key
while they seem at the same time to be the largest user. Also, the
computer security budget of NIST has been cut by over 3 million
dollars. Is electronic privacy and authentication for the most
automated society on earth so unimportant that congress (or those
advising them) feels compelled to cut the equivalent of 6 minutes of
of the annual Defense budget from it?
Jim Bidzos, President
RSA Data Security, Inc.
PS: It may be appropriate to have a newsgroup on X.509 and or the
daemon@ATHENA.MIT.EDU (RSA Data Security)
Thu Dec 21 20:33:43 1989
From: sun-barr!apple!well!rsa@DECWRL.DEC.COM (RSA Data Security)
Another often-overlooked possibility is to use Kerberos and RSA
together. Kerberos can be used, as it is, for authentication in a
given domain, and RSA can be used "on top" of Kerberos for
inter-domain authentication by system adminsitrators. This way, users
don't even need to be aware of anything but Kerberos. That also
reduces the cost to $2.50 per domain.