SPKI, SDSI and the other certificate mechanisms from 1996 onward started out to address apparent overcomplication in the X.509 world. However, by starting with a blank sheet of paper, they ended up addressing a more basic problem than complexity. Earlier certificate mechanisms suffered from the Walton's Mountain Assumption - that if you know a name for someone you know their identity (all their defining characteristics) - and that if you know someone's identity, then you know whether they're authorized to do or have something they request. This assumption is true in a world of small towns where, as the old joke goes, ``you don't have to use your turn signals because everyone knows where you're going''. That world no longer exists, so earlier certificate mechanisms based on it (X.509 in particular) fail miserably. Specifically, the Walton's Mountain Assumption is that those characteristics of a small town apply to the entire world.
This assumption is replaced by one of local knowledge: that knowledge required for security decisions and identity establishment remains local but the world extends beyond any one locality. In SDSI, an identifier is valid only locally to the person who creates it but the underlying raw public key is valid globally. In SPKI, an authorization grant is made only locally. If you need to grant authorization to someone beyond your locality, then you may (must) delegate that grant through a chain of local relationships. The same applies to PolicyMaker, KeyNote and XrML V2 (when properly used).
Along the way, we have learned that what is important in certificate (and related) security systems is not the computer-readable data structures and protocols alone. Rather, these certificates, licenses, grants, ACL entries, ..., are a cyberspace reflection of relationships in the physical world - and the security of these systems rests most heavily on the security of the process by which the physical world relationships are bound to their cyberspace reflections. That security far outweighs the more trivial security of private key protection, key length, choice of algorithm, etc., that people have obsessed about for decades. In pursuing this line of reasoning, we now have the Ceremony work but this work is in its infancy. There is much more to come.
[24 January 2004]
There are five certificate syntax forms referenced from this page: SPKI/SDSI, X.509, PGP, X9.59 (AADS), PolicyMaker and KeyNote. This page defines SPKI/SDSI and gives some links to the others but doesn't claim to provide a full set.
Check out John Pritchard's SPKI resource page.
There are frequent questions about the status of SPKI in IETF and in general. I wrote to the cryptography list about this in this message and, as I often do, in a reply to that message.
subscribe spki
As with other majordomo mailing lists, you can send the command:
help
to learn of other commands you can issue.
The mailing list archive can be accessed at http://www.sandelman.ottawa.on.ca/spki/. [There is another mailing list archive that appears to be more current. Thanks to the list member who pointed me there...]
The SDSI (Simple Distributed Security Infrastructure) part of SPKI/SDSI was developed separately by Ron Rivest and Butler Lampson. The early documents on SDSI are available at:
It is generally asserted that one can achieve the desired non-repudiation through the combination of strength of cryptography and security of Certificate Authorities. However, as Don Davis and others have pointed out, this puts a burden on the individual keyholder that that person may not be equipped to handle. The result, when this is applied to normal consumers with home computers, is a potential victimization of that consumer.
One of the problems here is the change in computer cost and therefore ubiquity. In 1976, when Diffie and Hellman were writing and proposed non-repudiation (under a different term), computers were in guarded glass rooms. Now they're in the family room where the neighbor's teenage son has easy, unguarded access. A guarded computer might well serve as a check writing machine, but an unguarded one is too dangerous to empower that way.
Carl M. Ellison; mailto:cme@acm.org?subject=spki.html
frm http://world.std.com/~cme/html/spki.html
This assumption is replaced by one of local knowledge: that knowledge required for security decisions and identity establishment remains local but the world extends beyond any one locality. In SDSI, an identifier is valid only locally to the person who creates it but the underlying raw public key is valid globally. In SPKI, an authorization grant is made only locally. If you need to grant authorization to someone beyond your locality, then you may (must) delegate that grant through a chain of local relationships. The same applies to PolicyMaker, KeyNote and XrML V2 (when properly used).
Along the way, we have learned that what is important in certificate (and related) security systems is not the computer-readable data structures and protocols alone. Rather, these certificates, licenses, grants, ACL entries, ..., are a cyberspace reflection of relationships in the physical world - and the security of these systems rests most heavily on the security of the process by which the physical world relationships are bound to their cyberspace reflections. That security far outweighs the more trivial security of private key protection, key length, choice of algorithm, etc., that people have obsessed about for decades. In pursuing this line of reasoning, we now have the Ceremony work but this work is in its infancy. There is much more to come.
[24 January 2004]
There are five certificate syntax forms referenced from this page: SPKI/SDSI, X.509, PGP, X9.59 (AADS), PolicyMaker and KeyNote. This page defines SPKI/SDSI and gives some links to the others but doesn't claim to provide a full set.
Check out John Pritchard's SPKI resource page.
There are frequent questions about the status of SPKI in IETF and in general. I wrote to the cryptography list about this in this message and, as I often do, in a reply to that message.
Table of contents
- SPKI/SDSI Documentation
- Code and product pages
- Papers
- Other certificate formats
- Glossary of terms used within this page
SPKI/SDSI Documentation
The SPKI/SDSI certificate format is the product of the SPKI Working Group of the IETF. The IETF SPKI documentation is in four parts:- RFC2692: Requirements giving the requirements gathered by the working group at the start of the process.
- RFC2693: Theory giving the theory of authorization certificates, as opposed to name or ID certificates that most people (e.g., X.509) discuss. This document points out some of the flawed assumptions in ID certificate theory and shows how SPKI's certificates (both authorization and ID) attempt to correct those flaws.
- structure #5 (old, #6 coming soon) -- giving the detailed structure of certificates that satisfy the theory RFC.
- examples #1 (even older) -- giving actual examples of certificates, both for instruction in how to use authorization certificates and for testing implementations for interoperability.
subscribe spki
As with other majordomo mailing lists, you can send the command:
help
to learn of other commands you can issue.
The mailing list archive can be accessed at http://www.sandelman.ottawa.on.ca/spki/. [There is another mailing list archive that appears to be more current. Thanks to the list member who pointed me there...]
The SDSI (Simple Distributed Security Infrastructure) part of SPKI/SDSI was developed separately by Ron Rivest and Butler Lampson. The early documents on SDSI are available at:
- The MIT official SDSI page.
Code and product pages
- JSDSI has a project page on Sourceforge.
- Niels Möller's SPKI library.
- My s2x code source (with Makefile) and an earlier executable for Windows (along with a copy of sexp). s2x translates from a canonical S-expression into XML. If you have an advanced form S-expression, you can convert it to canonical with Ron Rivest's sexp.
- My canonical S-expression parser is included in s2x.tgz, referenced in the previous bullet. When I have time, I will separate it out.
- Ron Rivest's S-expression page includes code for the utility, sexp, that translates from advanced to canonical S-expressions.
- The open-source CDSA release from Intel includes an SPKI service provider for building certificates and a module, AuthCompute, for doing tuple reduction. CDSA splits this SPKI operation into two parts so that one can also get tuples from other certificate forms and do a combined authorization computation, assuming the plug-in service provider written for one of those other formats implements the necessary additional call [TP_CertgroupToTuplegroup]. At present, only the SPKI service provider implements that call.
- Cristian Ferreira de Souza has provided an implementation of the SSL Protocol in Java which supports SPKI/SDSI Certificates. I have not tested this code yet, but am making it available for the community as Christian requested. I did not put it all in one .zip file, as he had requested, since I often don't want to wait for a single huge download and I assume others are in that position. Here is the mail he sent me with that code.
- Sameer Ajmani has his SPKI/SDSI code under development.
- The MIT official SDSI page includes code for SPKI/SDSI.
- The eSpeak product from HP uses SPKI certificates for specifying and delegating access control.
- Per Harald Myrvang, An Infrastructure for Authentication, Authorization and Delegation. This thesis includes a large body of code.
- The CDSA code at sourceforce.
- SILC, a secured chat project that uses SPKI certs alongside X.509 and PGP, but I haven't tried this yet to see how they use them.
SPKI/SDSI Papers
- Ellison, C. M., ``Home Network Security.'', Intel Technology Journal. http://developer.intel.com/technology/itj/2002/volume06issue04/ (November 2002).
- Dohrmann and Ellison, ``Public-key Support for Collaborative Groups'', 1st Annual PKI Research Workshop, April 2002.
- The theory behind SPKI certificates has been summarized in a journal paper: Ellison, ``The nature of a usable PKI'', Computer Networks 31 (1999) pp. 823-830, which includes figures that might help in reading RFC2693, although the RFC is far more detailed and complete than this paper.
- M. Burnside, D. Clarke, T. Mills, A. Maywah, S. Devadas, and R. Rivest, ``Proxy-Based Security Protocols in Networked Mobile Devices'', Proceedings SAC 2002. [PDF] [PS]
- J.Y. Halpern and R. van der Meyden, ``A logical reconstruction of SPKI''.
- Jon Howell's research papers include his thesis, other discussions of SPKI and examples of its use. These include an extension of SPKI to include the formalization of the principal type ``A quoting B''. This is used in implementation of authorized gateway functions (where a gateway has to translate data and therefore invalidate the digital signature of the data signer).
- A Trusted Execution Platform for Multiparty Computation
- Per Harald Myrvang, An Infrastructure for Authentication, Authorization and Delegation.
- Ninghui Li, Local Names in SPKI/SDSI.
- Juha Paajarvi, ``XML Encoding of SPKI Certificates'', March 2000 [cached copy]
- Dwaine Clarke, SPKI/SDSI HTTP Server / Certificate Chain Discovery in SPKI/SDSI, September 2001. (Master's thesis, reporting on his use of SPKI/SDSI for access control to web pages.)
- Tuomas Aura, Carl Ellison, Privacy and Accountability in Certificate Systems, Research Report A61, Laboratory for Theoretical Computer Science, Helsinki University of Technology, Espoo, Finland, April 2000. [PS][PDF][abstract][BibTeX].
- Tuomas Aura, Dieter Gollmann, Software license management with smart cards, in Proc. USENIX Workshop on Smartcard Technology, Chicago, May 1999, pp. 75-85, USENIX Association 1999. [PS][PDF][HTML][abstract/BibTeX].
- Tuomas Aura, Distributed access-rights management with delegation certificates, Secure Internet Programming: Security Issues for Distributed and Mobile Objects, J. Vitek and C. Jensen (Eds.), LNCS 1603, pp. 211-235, Springer 1999. [PS][PDF][abstract/BibTeX]. (Copyright 1999 Springer)
- Tuomas Aura, Fast access control decisions from delegation certificate databases, in proceedings of 3rd Australasian Conference on Information Security and Privacy ACISP '98, Brisbane, Australia, July 1998, pp. 284-295, Lecture Notes in Computer Science 1438, Springer 1998. [PS][PDF][abstract/BibTeX].
- Tuomas Aura, On the structure of delegation networks, in proceedings of 11th IEEE Computer Security Foundations Workshop, Rockport, Massachusetts, June 1998, pp. 14-26, IEEE Computer Society Press 1998. [PS][PDF][abstract/BibTeX].
Sameer Ajmani. Masters thesis, Massachusetts Institute of Technology, July 2000.
[ PostScript | PDF ]
[CME: This thesis addresses the distributed certificate chain validation problem when you don't want to release your pool of certificates to the world.]
UPnP Papers
- See the UPnP Security Standards web page.
- The Security Ceremonies paper on that page is especially noteworthy. It is the first paper to use the Ceremony construct outlined by me and Jesse Walker for security protocols.
PKI in general
- Diffie and Hellman, ``New Directions in Cryptography'', IEEE Transactions on Information Theory, 1976. [The paper that started it all.]
- Ellison, ``Improvements on Conventional PKI Wisdom'', 1st Annual PKI Research Workshop, April 2002.
- For a completely different approach to solving the John Wilson problem, see ``Wyman vs. Wyman'', from All Things Considered, Friday, November 15, 2002.
- The John Wilson problem isn't limited to computer companies. See Tony Blair's e-mail to the wrong person.
- Modeling a Public-Key Infrastructure (Ueli Maurer), available at http://www.inf.ethz.ch/department/TI/um/publications.html.
- Reasoning about Public-Key Certification (Reto Kohlas and Ueli Maurer), Confidence Valuation in a Public-Key Infrastructure Based on uncertain Evidence (Reto Kohlas and Ueli Maurer), available at http://www.inf.ethz.ch/personal/kohlas/publications.html.
- Don Davis, ``Compliance Defects in Public-Key Cryptography'', Proc. 6th USENIX Security Symp, (San Jose, CA, 1996), pp. 171-178. (130 Kbytes) (PDF, 134 Kbytes).
- Carl Ellison and Bruce Schneier, ``10 Risks of PKI'', Computer Security Journal, v 16, n 1, 2000, pp. 1-7.
- Carl Ellison and Bruce Schneier, ``Risks of PKI: Secure E-mail'', Inside Risks 115 CACM 43, 1, January 2000, Inside RISKS columns for the CACM or Bruce's copy.
- Carl Ellison and Bruce Schneier, ``Risks of PKI: Electronic Commerce'', Inside Risks 116 CACM 43, 2, February 2000, Inside RISKS columns for the CACM or Bruce's copy.
- Carl Ellison, ``What do you need to know about the person with whom you are doing business?'', written testimony for the House Science and Technology Subcommittee Hearing of 28 October 1997: Signatures in a Digital Age
- Carl Ellison, ``Certification Infrastructure Needs For Electronic Commerce And Personal Use'', submission to NIST, 16 July 1997 (with minor modifications 14 August 1997).
- Carl Ellison, ``Naming and Certificates'', CFP 2000.
- Wendy Grossman, ``Circles of Trust'', Scientific American, August 2000.
- Ben Rothke, PKI: An Insider's View, Oct 2001, Information Security
- Gatekeeper goes missing, from Australian IT. Discusses the non-adoption of PKI. April 22, 2003.
Digital Signature Risks
The idea that digital signatures could enable electronic commerce through what has come to be known as non-repudiation was first proposed by Diffie and Hellman in their seminal paper, ``New Directions in Cryptography''. The idea has since gained much popularity.It is generally asserted that one can achieve the desired non-repudiation through the combination of strength of cryptography and security of Certificate Authorities. However, as Don Davis and others have pointed out, this puts a burden on the individual keyholder that that person may not be equipped to handle. The result, when this is applied to normal consumers with home computers, is a potential victimization of that consumer.
One of the problems here is the change in computer cost and therefore ubiquity. In 1976, when Diffie and Hellman were writing and proposed non-repudiation (under a different term), computers were in guarded glass rooms. Now they're in the family room where the neighbor's teenage son has easy, unguarded access. A guarded computer might well serve as a check writing machine, but an unguarded one is too dangerous to empower that way.
- Adrian McCullagh and William Caelli, Non-repudiation in the Digital Environment, First Monday, volume 5, number 8, August 2000.
- Cem Kaner, ``The Insecurity of the Digital Signature'', September 1997.
- Jane Winn, ``The Hedgehog and the Fox'': Distinguishing Public and Private Sector Approaches to Managing Risk for Internet Transactions.
- The Federal Trade Commission had a workshop on Global Electronic Commerce in June 1999.
- Carl Ellison presentation to the workshop [zipped PowerPoint ]
- Winn and Ellison, Comment P994312 to the Federal Trade Commission, March 1999.
- Carl Ellison, comment about jurisdictional issues, June 1999.
- Gladman, Ellison and Bohm, Digital Signatures, Certificates and Electronic Commerce, April 1999.
- PFIR Statement on Electronic Signatures and Documents in reaction to the signing of S.761 on June 30, 2000.
- Bohm, Brown and Gladman, ``Electronic Commerce: Who Carries the Risk of Fraud?'', (with a special focus on the situation in the UK), July 2000.
- Carl Ellison and Bruce Schneier, ``Risks of PKI: Electronic Commerce'', Inside Risks 116 CACM 43, 2, February 2000, Inside RISKS columns for the CACM or Bruce's copy.
- ``E-Sign and UETA: What Should States Do Now?'' National Consumer Law Center
- William Allen Simpson, Electronic Signatures Yield Unpleasant Surprises, June 2000.
- Michael Froomkin, The Essential Role of Trusted Third Parties in Electronic Commerce, 1996.
- CALPIRG's report Identity Theft 2000, not about digital signatures, but about sloppy authentication in current practice and the legal problems that result.
- Andy Oram, ``Forget the Global Marketplace-Trade with Someone You Know'', Dec 2000. Andy emphasizes that you don't get trust from technology. It takes work. This suggests to me that we may need layers of middlemen not for shipping or inventory reasons, but for trust reasons. The Internet allows me go directly to the middleman's own suppliers, but I don't have the energy or time (or money to lose in inevitable risk) to make so many individual relationships.
- Don Davis, ``Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML'', to appear in Proc. Usenix Tech. Conf. 2001 (Boston, Mass., June 25-30, 2001).
[IMHO, we could use a law declaring that there is non-authenticating information (namely anything anyone other than the person being identified might be able to learn) and that any creditor using non-authenticating information to establish a credit account is and remains liable for all charges incurred under that account. BTW, such a law might cause all mailed credit card offers to dry up -- a good side-effect. Also, it should be noted that all information in a credit report is automatically non-authenticating under this definition, so that controls on the dissemination of credit reports would not be necessary to prevent identity theft (only to preserve privacy).]
[Don points out that if you naively sign something that isn't specifically anchored to the transaction you intended, then that signed message can be replayed in a transaction where you don't intend the result. He notes that e-mail cryptography standards encourage this mistake. If you assume non-repudiation of signed e-mail, this can have unfortunate results.]
Miscellaneous Papers
- Carl Ellison, Ceremony Design and Analysis, Cryptology ePrint Archive, Report 2007/399, 2007.
- The CAP Theorem states that you can design a distributed system to achieve any two of the following three characteristics: (1) data Consistency; (2) application Availability; (3) tolerance of network Partitions; but you can never achieve all three at the same time. This has application to revocation in certificate systems. The various revocation mechanisms are attempts to achieve data consistency in an application that must be available and must tolerate network partitions.
- Statement: Armando Fox and Eric Brewer, Harvest, Yield, and Scalable Tolerant Systems, in Proceedings HotOS-VII, 1999.
- Proof: Seth Gilbert and Nancy Lynch, Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, Sigact News, 33(2), June 2002.
- M. Abadi, M. Burrows, B. Lampson, and G. Plotkin. A calculus for access control in distributed systems. ACM Trans. Programming Languages and Systems, 15, 4 (Oct. 1993), pp 706-734. This paper first appeared in Crypto 91, August 1991.
- B. Lampson, M. Abadi, M. Burrows, and E. Wobber. Authentication in distributed systems: Theory and practice. ACM Trans. Computer Systems 10, 4 (Nov. 1992), pp 265-310. This paper first appeared in the 13th SOSP, October 1991.
- Carl Ellison, ``Establishing Identity Without Certification Authorities'', 6th USENIX Security Symposium , 1996.
- Ron Rivest's Publications page.
- John Bull, Li Gong, Karen R. Sollins, ``Toward Security in an Open Systems Federation'', Proc. ESORICS, Toulouse, France, 1992.
- Ellison, Hall, Milbert, Schneier, ``Protecting Secret Keys with Personal Entropy''
- based on Carl Ellison, Emergency Key Recovery without Third Parties ,CRYPTO '96 Rump session presentation.
- The IETF XML Digital Signature Working Group, core draft (8) includes the data structure (in KeyInfo) for holding SPKI-encoded public keys and/or certificates backing up an XML signature. This draft does not intend to address what is done with certificates. It is at a much lower level, just specifying the syntax of a raw signature.
Other certificate formats
- X.509, PGP and SPKI: Summary comparison table
- X9.59 (also known as AADS) is a mechanism that uses ACLs only, instead of certificates. Specifically, the ACL is a bank's account database that has had a public-key field added, so that the bank can look up the account-holder's public key. This makes the X9.59 ACL an authorization instrument, in SPKI terms, similar to the ACL implemented by SSH's file: .ssh/authorized_keys. For more information on X9.59, see: http://www.garlic.com/~lynn
- PGP - an identity certificate format, the first to gain widespread usage and the form supporting the well known Web of Trust
- IETF OPENPGP working group
- PGP Inc.
- Zendit from Authora, a UI for OpenPGP.
- X.509 - the identity certificate from the X.500 effort, with an attribute certificate added recently (perhaps borrowed from X9)
- IETF PKIX working group
- ISO documents are available by purchase, not by the web
- Blaze, Feigenbaum and Lacy trust management forms (computing authorization with certified code)
Misc. articles and how-to
This is not intended to be a complete list at all. These are just some links as people refer me to articles on PKI.- start of the eWeek series on PKI
Glossary
- asymmetric cryptography: defined originally by Diffie and Hellman, a cryptographic system using different keys for encipherment and decipherment such that one of the keys (private key) can not be derived efficiently from the other (public key).
- certificate: a digitally signed data record communicating some information from the signer (issuer) of the certificate to the verifier of the certificate. A certificate differs from a general signed message usually in that:
- the data structure is well defined so that a computer can interpret the structure, and
- the certificate's ``message'' is of the form ``to whom it may concern'', rather than addressed to a specific party
- Certificate Authority: in the X.509 world, a special certificate issuing entity, usually part of a hierarchy, responsible for issuing all certificates to end entity keyholders.
- digital signature: a computation with a private key and typically the hash of a document or data record such that any entity in possession of the matching public key can verify computationally that the computation was performed by the associated private key and that the signed document has not changed since the signature was computed.
- hash: a cryptographic computation over a message yielding a fixed length quantity (the hash value) such that it is computationally difficult to find any two different input messages yielding the same hash value. The ``strength of a hash'' is a reference to the difficulty of finding such message pairs.
- keyholder: the holder of the private key.
- non-repudiation: the notion that the keyholder is legally liable for any statement digitally signed by that keyholder's signature key.
- PGP: Pretty Good Privacy -- an early public key application, defining the first public key infrastructure to be widely deployed.
- PKI: Public Key Infrastructure -- a mechanism to permit the distributed use of public keys, involving certificates that bind information of interest to public keys
- private key: a key in an asymmetric cryptosystem that is kept secret and held by one entity, called the keyholder.
- public key: a key in an asymmetric cryptosystem that need not be kept secret and is often
- SDSI: Simple Distributed Security Infrastructure
- secret key: a key in a symmetric cryptosystem.
- speaks for: the notion that a private digital signature key speaks digitally signed statements in cyberspace on behalf of the keyholder
- SPKI: Simple Public Key Infrastructure
- symmetric cryptography: the original kind of cryptography, in which the same key is used for both encipherment and decipherment.
- trust: a term so frequently misused that it has become almost devoid of meaning. It means whatever you want it to mean, but vendors keep using it because it evokes warm and fuzzy feelings and that helps sales.
- Web of Trust: a mechanism for fault tolerance of certificate signature, associated with PGP.
- X.509: a data structure defined as part of the X.500 global directory effort, designed to bind an X.500 distinguished name to a public key. The presumption in X.509 is that the named entity is the keyholder of the associated public key. In some cases, it is assumed that the public key speaks for the named entity.
Carl M. Ellison; mailto:cme@acm.org?subject=spki.html
frm http://world.std.com/~cme/html/spki.html