1st Annual PKI Research Workshop: Summary www.cs.dartmouth.edu/~pki02/summary.shtml
Last modified: 08/03/02 05:16:00 PM

Summary by Ben Chinowsky, Internet2

This report summarizes current issues in PKI as discussed at the 1st Annual PKI Research Workshop, held April 24-25, 2002 and sponsored by NIST, NIH and Internet2.

Sense of the Meeting

While reaching consensus was not among the goals of the workshop, there appeared to be something close to general agreement on the following points.

PKI trust relationships must be built on real-world trust relationships. In the workshop's XKMS panel discussion, Phillip Hallam-Baker described PKI as "the interface between the Internet and the Real World," and it was evident throughout the workshop that PKI practitioners are increasingly taking this as a starting point. At the coarsest level of generalization, hierarchical (aka traditional) PKIs are usually more appropriate for hierarchical organizations — such as the military, as discussed by Green, Winnenberg, Henry, and Fink. Non-hierarchical PKIs (aka trust networks, webs of trust, or anarchy) are usually more appropriate for non-hierarchical organizations — such as the collaborative groups discussed by Dohrmann and Ellison. Hallam-Baker illustrated the idea of building PKIs on existing trust relationships in his overview of the Trust Assertion XML Infrastructure (TAXI), the direct ancestor of SAML and XKMS. Even in the "Dueling Theologies" session that opened the workshop, there was little of the my-model-is-better-than-your-model style of argument common to many discussions of PKI. Instead, there is a growing awareness that we have a wide variety of tools and a wide variety of circumstances in which they can be applied, and growing agreement that starting from existing real-world trust relationships, whether those relationships be hierarchies or networks, is the central principle that should guide how we apply these tools.

At the same time, there is also broad agreement that the closer you look at these top-level categorizations — hierarchical vs. non-hierarchical, real-world vs. not — the more questions arise. Does "traditional PKI" refer only to X.509 with a strict X.500-style naming hierarchy, or is it broader than that? When members of a purchasing department operating under instructions to honor any purchase order coming from some specified class of individuals nonetheless insist on making some kind of personal contact before placing an order for someone they're not familiar with, what are the real-world trust relationships that PKI should follow? Clearly the top-level categories, while necessary, are not sufficient for describing either real-world or PKI trust relationships. It was also noted that in some cases — such as the use of PKI to ensure privacy or anonymity — it can be important to make sure that PKI trust relationships don't follow real-world trust relationships.

Because the real-world trust relationships of many large organizations are "heterarchical" — consisting of a diverse set of hierarchies, anarchies, and combinations of the two — heterarchical PKIs appear to have a bright future. Such hybrid PKIs are created by means of bridge CAs. Federal PKI Steering Committee Chair Spencer briefly discussed progress on the Federal Bridge Certification Authority (FBCA). Alterman presented a progress report on the NIH-EDUCAUSE PKI Interoperability Project, which centers on communication between the FBCA and the Higher Education Bridge Certification Authority (HEBCA); Alterman summed up by saying that "there are NO show-stoppers." The workshop's work-in-progress session included a discussion by Alterman of possible topologies for a multiple-bridge infrastructure.

Directory functionality is a central concern for both traditionally- and non-traditionally-minded PKI practitioners. For example, Marc Branchaud of RSA noted that "the directory is the main thing that makes X.509 work," and Peter Alterman observed that "solving directory issues is the key to interoperability." On the other hand, in his critique of "conventional PKI wisdom," Carl Ellison puts the problem of naming entities front and center. Ellison sees the gap between the ways computers use names (precisely) and the way humans use names (imprecisely) as a big obstacle to humans being able to trust that they have chosen the right cert from a directory and are dealing with the person they think they are dealing with. At Intel this has become known as "the John Wilson problem." Ellison advocates using personal directories or naming services that can use "local names" (e.g., "my mom") to retrieve keys.

Users want security, but they're not willing to tolerate much additional system complexity in order to get it. If security adds significant complexity, users will either use it incorrectly — which can provide a false sense of security, leaving the user worse off than before — or not use it at all. Carl Ellison argued that the main successful deployment of certificates so far, SSL, is in effect mostly used to grant this false sense of security. Ellison suggested an experiment comparing the frequency of stolen credit card numbers in encrypted and unencrypted transactions; he was was sufficiently confident in his pessimism about SSL to offer to include his own credit card in the non-encrypted sample.

Legal issues, in particular certificate policy issues, are very hard. Fink, discussing his work with the Naval Surface Warfare Center, observed that PKI can also stand for "Policy Keeps Interfering." Green laid heavy stress on the DoD's work in this area: "we have a major activity in the certificate policy world...if you're not paying attention to this you're not taking PKI seriously." Klingenstein described a trust continuum running from collaborative trust (handshakes) to legal trust (contracts). While collaborative trust tends to go with the federated models of security (like Shibboleth, which resembles a bridge CA in some respects), and legal trust tends to go with traditional PKI, there are a wide range of intermediate cases, and each user community needs to decide what mix works best for it.

Issues and Approaches

Key management and mobility. Much discussion was devoted to various schemes for ensuring that people can access their keys as needed, both at the time of issuance and thereafter. In the session on key management, Gupta provided a survey of current approaches. She emphasized the wide variety of solutions available and noted three contraindications for attempting to implement mobility: a need for strong non-repudiation, a need to be able to recover encryption keys, and zero tolerance for DoS attacks. Perrin presented a system for sharing a single private key among many users; he noted that his system is intended to interoperate with conventional PKI rather than replace it. Perrin's system uses an online trusted third party; Peter Honeyman pointed out that if you remove the asymmetric cryptography from this system, it looks a lot like Kerberos, and asked why he didn't just use that. Perrin replied that his system makes path validation possible and can be implemented without a central server for the shared private key (though the prototype does indeed use such a server). Also on the theme of incorporating secret-key cryptography, Sandhu pointed out that "it is completely possible to design a sufficiently secure password system...security is always about adequacy." Absolute security doesn't exist anyway, and users don't inherently hate passwords, they just don't want so many of them. With respect to the question of what's holding back physical smartcards; Sandhu observed that "it's the readers, stupid;" he described the principal motivation of his work on virtual smartcards as to provide a "phased migration path" from weak passwords to strong PKI.

Smartcards are a major focus of effort for the military, and the DoD and International Coalitions presentations included two striking cautionary tales drawn from their experience. One speaker noted that smartcard readers present more of a challenge than smartcards themselves, and recounted an episode in which users were issued smartcards and PINs, but then six months elapsed before the card readers were installed and working, so that the PINs were mostly forgotten. Henry noted that the DoD currently combines smartcards with Geneva Convention cards; as the Geneva Convention card is to be surrendered upon capture by the enemy, this clearly needs to be fixed.

Also closely related to key management were the presentations of Boneh and Levy on their respective developments of identity-based encryption (IBE). IBE uses information about the user, such as an email address, to create a public key, making it possible to send someone encrypted mail without them having to first set up a keypair and publish their public key. The recipient then visits a server to obtain the corresponding private key. Boneh emphasized the "viral" deployment properties of this system, seeing its potential to encourage broader use of PKI as its principal advantage. Levy emphasized the control that IBE gives the sender over what information the receiver needs to provide the server in order to get their private key; the sender thus gains precise control over how secure the encryption will be.

Authorization. Underscoring the importance of authorization for PKI as a whole, in addition to the main session on authorization, three of the four presentations in the workshop's "Scale" session were also devoted to authorization. DeTreville set out his thinking on how to do scalable distributed authorization by building relational algebra into certificates. Cánovas discussed his work on delegation of authorization in SPKI, which has been deployed in a production smartcard system at his university. Knight discussed the role-based X.509 privilege management infrastructure he is developing for the Canadian Department of National Defence.

In the authorization session proper, Dam discussed a streamlined version of the SPKI authorization syntax which is adequate for almost all real-world uses but which executes in linear rather than exponential time. Dohrmann outlined a PKI that he and Carl Ellison developed with the overarching goal of improving ease of use, thereby improving the likelihood that the system will be used correctly. One of the ways they do this is by having lines of authority to grant authorizations follow existing lines of authority within an organization; for example, long authorization chains that go up one side of the org chart and down the other are preferred to short ones that cut across from one leaf node to another. Thompson provided an overview of approaches to authorization and an in-depth look at Akenti. Akenti is a Grid-oriented authorization system which has been implemented as an Apache module and which has been used by the Diesel Combustion Collaboratory and the National Fusion Collaboratory.

The workshop's emphasis on ensuring ease of use was especially strong in the discussions of authorization, reflecting a general awareness of the conceptual complexity of relationships in this area.

Validation and revocation. In the validation session, Micali introduced NOVOMODO, a scheme for ultra-lightweight certificate validation via 20-byte tokens. Micali developed an extended analogy between these tokens and the validity stickers affixed to student ID cards at the start of each term. Tero Hasu, presenting work by his colleague Kortesniemi, discussed a range of options for validity management of SPKI authorization certificates, and set out a very simple (only two messages) validity management protocol. Branchaud noted that while X.509 was built on the assumption that CAs aren't online, that assumption no longer necessarily holds. He provided an overview of resulting options for distributed and delegated validation, looking beyond OCSP to, "in the limit," possibly getting rid of certificates altogether.


In order to work out both the social and the mechanical issues, we need more deployment experience. While the deployments discussed at the workshop have provided many useful lessons, the user base of these deployments is tiny in relation to the user base PKI will need to support. In addition to the hundreds of technical details that can only be fully resolved in the course of a full-scale deployment, there are a lot of "Why Johnny Can't Encrypt"-type questions that can't be answered until there is more experience with PKIs supporting thousands rather than dozens of users. In addition to removing obstacles to deployment, we must also ensure that there is sufficient positive motivation for PKI; as Phillip Hallam-Baker noted, "you don't want to deploy PKI starting with problems that have already been solved better."

We need to do a better job of working with social scientists, lawyers, and other non-"technical" experts. It seems clear that these experts are available and willing to help, but the initiative and direction in applying their skills have to come from the technical community.

We need to keep cross-pollinating. There was near-unanimous opinion in favor of immediately beginning planning for a 2nd Annual PKI Research Workshop, and that planning is now underway.

Back to Home Page Maintained by Sean Smith, sws@cs.dartmouth.edu