daemon@ATHENA.MIT.EDU (Denis.Russell%newcastle.ac.uk@NSFNET-RELAY.AC.UK)
Wed Dec 20 07:38:44 1989

From: Denis.Russell%newcastle.ac.uk@NSFNET-RELAY.AC.UK
To: kerberos@ATHENA.MIT.EDU

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.
 
  --------=============oooooooooo=============-------------
 
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
     shortcomings:
 
     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
     as good.
 
     (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
     digest function.
 
     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
     message proper.
 
5)   RSA  is  patented in the USA (except for the Government and
     MIT?).
 
     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
     using RSA.
 
 
References:
 
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
1978
 
Tanembaum, A.S.  "Computer Networks" Prentice-Hall International
ISBN 0 13 164699 0, 1981 (First ed.)
 
  --------=============oooooooooo=============-------------
 
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
The University
Claremont Road            Tel:   (+44) 91 222 8243
Newcastle upon Tyne       Fax:   (+44) 91 222 8232
       NE1 7RU            Telex: 53 65 4
ENGLAND

daemon@ATHENA.MIT.EDU (RSA Data Security)
Thu Dec 21 17:38:59 1989

From: zaphod.mps.ohio-state.edu!brutus.cs.uiuc.edu!apple!well!rsa@THINK.COM  
(RSA Data Security)
To: kerberos@ATHENA.MIT.EDU


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
Internet RFC's.

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)
To: kerberos@ATHENA.MIT.EDU


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.