[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Linkology proposal for SPKI/SDSI

This note gives some thoughts on links, with a specific proposal for a
better way of handling them in SPKI/SDSI.  I was motivated in part by
my reading of the XML document
on linking, although what is given here is much simpler and directed
specifically at SPKI/SDSI.  Comments and discussion invited.

At the moment we have s-expressions containing subexpressions like
	(hash md5 {...})
	(hash md5 {...} <url>)
	(ref <key> name)
this is ad-hoc, and also fails to make a clear distinction between hash-values
and links, between the pointers and the thing pointed to.

I propose a uniform syntax of the form
	(link ...)
where the parameters can be of several forms, including:
	(hash <alg> <value>)	
	(url "...")

Thus, the forms above become:
	(link (hash md5 {...}))
	(link (hash md5 {...}) (url "..."))
	(link (url "..."))
	(link (srl <key> name))

That is the short version of the story.  The long version of the story
goes as follows.

What is a link?  This is not a simple question, and linkology is still
evolving.  We don't need to answer this question fully, but should provide
a framework for future developments and/or application-specific requirements.
The "link" function is extendible so that other fields can be added.  As an
example, how do we have a link defined by SDSI name, rather than URL?  (The
above example gives a hint of that part of our proposal.)

Here are some considerations and discussions.

** The main thing that a link does is to refer to some other object.  It
   specifies or implies some procedure for obtaining that other object.

** There are several ways to refer to another object, e.g. hash values and 
   URL's. Even URL's
   are not always well-defined; you may have to specify a language or
   other parameters in the http request.  Thus, we might need something

	(link (url "http://w3.org/index.html" (language french)))

   The link-handler will have to know how to handle such a URL.
   For things referred to by SPKI/SDSI names I propose the syntax:

	(link (srl <key> n1 n2 ... nk))

   (Here "SRL" stands for "SPKI/SDSI Resource Locator".  It is analogous
   to the URL, but typically points to some s-expression (a public key)
   rather than a web page or file.

   If there is more than one object with a given SRL or URL, then one way
   to make the reference precise is to also include a hash value:

	(link (srl <key> bob) 
	      (hash md5 {...}))

   Other forms of resource locators can be added for specific applications, 

	(link (phone-download 617-555-1234)
              (hash md5 {...}))

   might be just what somebody needs.  SPKI/SDSI only presumes that an
   implementation understands urls, srls, and hashes as a means of identifying
   objects.  Future extensions might include ways of picking out parts of
   an object, as in
	(link (srl <key> auto-certificate) (part photo) (hash md5 {...}))
   or other exotic things. 

** The SDSI implementation should have some understanding of the type of
   the object being pointed to.  At a high level, there are only two types
   of objects, as far as SPKI/SDSI is concerned:

	s-expressions	(byte strings and s-expressions represented in 
		         canonical format)

	data		everything else (uninterpreted byte strings)

   A link can specify what sort of object it is looking for.  This is given
   in an (sexp) or (data) attribute.  Thus

	(link (sexp) 
              (url "http://mit.edu/~rivest/autocertificate")
	      (hash md5 {...}))

   is a link to some stuff that can be interpreted as an s-expression,
   even though the URL has no such type information.  To link to the same file
   as an uninterpreted byte string, one would have:
	(link (data) 
	      (url "http://mit.edu/~rivest/autocertificate")
	      (hash md5 {...}))

   As a further refinement, a display-type can be given for data:

	(link (data "image/gif") 	
	      (url "http://mit.edu/~rivest/goofy-photo.gif")
	      (hash md5 {...}))

   In some cases it might be useful to include a sexp type indicator, as in
	(link (sexp public-key)
              (url "http://mit/edu/~rivest/key45"))
   This is analogous to the argument for "data", but probably less useful.

   For s-expressions, a hash value is the hash value of its canonical
   representation.  For an uninterpreted data file, it is just the hash
   of that file (without the display type or any other information given
   in the link).  The hash value is the hash of the remote information.

   If the sexp/data type is not given, the default is (sexp).  

** Types of links

   We distinguish two types of links: 

	-- a mere reference

	-- an inclusion by reference, where the intent is that the meaning
           of the s-expression should be the same as if the entire link
           s-expression were replaced by the thing pointed to.

   We call these links "pointers" and "grabbers", respectively.  They are
   indicated by the link options (point) and (grab).  


	(link (point) (srl <key> bob))

   is a pointer to bob's key, while

	(link (grab) (srl <key> bob))

   is a grabber of bob's key, which can be used (more-or-less like the
   C "#include" macro) wherever bob's key might have be usable directly in
   an s-expression.

   To interpret an s-expression, you need in principle to replace all the 
   grabbers by their referents, and iterate until you have no more 
   grabbers.  Circularity and explosive growth are of course possible, 
   which your local implementation will of course strongly discourage 
   by putting tight implementation limits on how much work it will do 
   trying to expand grabbers.  Lazy evaluation and caching of previously
   expanded links will keep things from getting out of hand, in general.
   Most importantly, even though the _meaning_ of an s-expression may be
   formally defined in terms of the expansion of grabbers, the _processing_
   of the s-expression may not require the actual expansion.  For example,
   if you have a certificate with subject
	(subject (link (grab) (url "http:/foo"))) ,
   you can certainly process the certificate without expanding the link.
   (Here one could specify that the link should be just pointer in all
   cases, but the above way of doing things is slightly more flexible, as you
   can include the subject in-line if you want.  This choice is debatable,
   and we could do it either way, but that is not the point here.  The
   point is in part that we can now talk more clearly about such choices.)

   Indeed, the general philosophy of SPKI/SDSI is: if you give someone 
   an s-expression with grabbers, you should also be so kind as to give him
   all of the necessary grabber referents so that he does not need to 
   rummage around the Internet to find out what your s-expression might 
   mean.  Of course,  you don't need to give him things he already knows 
   about.  The SDSI 1.0 way of putting this philosophy is: the work should 
   be on the "client" and not on the "server".  

   A certificate is one basic form of grabber definition, when the link
   is defined by an SRL.  We need to think about how other grabber definitions
   might be conveyed from client to server.

   Note that when an s-expression is hashed, the grabbers are not expanded
   to their definitions.  Thus, while the _meaning_ of an s-expression is the
   same as if grabbers had been expanded, the _hash_value_ of the s-expression
   is different, and you can't just replace the grabber by its definition
   without changing the hash value.  The s-expression would need to be
   re-hashed if a grabber is replaced by its definition (it is a different 
   s-expression, after all).

   When an assertion is made about an s-expression using a tag in an
   SPKI/SDSI certificate, it is understood that it is about the target
   s-expression with all grabbers expanded.  

   A link is understood to be a grabber unless it is explicitly declared
   to be a pointer.  (This seems more useful, as we are typically using
   links wherever we could have had the object directly.)

   I propose that the subject field of a certificate is understood to be 
   about the argument given.  (subject x) is about the s-expression x, not 
   what x refers to, unless x is a grabber.  Thus

	  (issuer bob)
	  (subject (link (point) (srl <key> bob)))
	  (tag (funky)))

  says that the s-expression (link (point) (srl <key> bob))) is funky, whereas

	  (issuer bob)
	  (subject (link (grab) (srl <key> bob)))
	  (tag (funky)))

  says that Bob's public key (public-key ...), the definition of the grabber
  link, is funky. 
  (Would it be better to have (link ...) for pointers and (grab ...) for
   grabbers? I think not.  It is nice to have the general term "link" to 
   refer to both pointers and grabbers.)

  We note that links can be nested in a natural manner, as in

	(link (grab) 
	      (srl (link (grab) (hash {...})) 

  (Assuming here that srl is looking for a public-key, and not a pointer,
  as its first argument.)  I don't think this introduces any new issues.

  Quoting is a potential issue.  How do you issue a certificate whose subject
  is the s-expression (link (grab) (srl <key> bob)) ?  We could use
	(subject (quote (link (grab) (srl <key> bob))))
  in a certificate.  I'm not sure this is actually useful, so I propose that
  this feature be held in abeyance until somebody makes a strong case for it.

  For SPKI/SDSI purposes, links that are not cryptographically secure should
  be pointers rather than grabbers.  A link is cryptographically secure for
  SPKI/SDSI if it has a hash value or is defined with an SRL (which is
  evaluated using signed certificates).  The SPKI/SDSI syntax may also
  specify using pointers rather than objects (or their grabbers) in some

** Access control
   In order to expand a link (either a pointer or a grabber), you might
   need to provide suitable credentials.  The link help out in providing
   an indication of what credentials are needed, or what might be

	(link (url "http://mit.edu/~faculty-salary-list.html")
		(link (grab) (srl <key> my-mit-administrator-certificate))))

   Since there is no hash here, the srl can point to your most recent 

   This needs thought, but is given here as an illustration of what other
   information might be needed in a link.

** small syntax note

   The attributes (sexp) (data) (grab) (point) could presumably also be
   given without their parentheses; I have proposed doing it this way
   in case they (like (data) already) might want arguments someday.

** other minor thought

   A link might point to an encrypted object.  The link could specify how
   to decrypt it:
	(link (url "http://mit.edu/secret-stuff")
	      (hash md5 {...})
              (decrypt-key (link (srl ...))))
   The hash is the hash of the decrypted data.  The key is given here by name.
   although it could be given in other ways.

** Note on specifying issuers

   The issuer of a certificate will be an expression of one of the forms
        (issuer <key>)
	(issuer (name <key> bob))
   where the key is given directly, or replaced by a grabber.

Ron Rivest