What do you need to know about the person with whom you are doing business?

House Science and Technology Subcommittee
Hearing of 28 October 1997: Signatures in a Digital Age
Written testimony of Carl M. Ellison

Thank you for the opportunity to submit for the record these remarks on Digital Signatures, Public Key Infrastructures (PKIs) and the nature of certificates.

These remarks are derived from my work as a cryptographer for CyberCash, Inc., an Internet payments firm, and as standards draft author for the Simple Public Key Infrastructure (SPKI) working group of the Internet Engineering Task Force (IETF). This paper presents my personal conclusions rather than an official position of either CyberCash or the IETF.

The announcement of the 28 October hearing asked, "Do you know who you are doing business with?" Before answering that question, one should really answer the two questions: "Do you need to know who you are doing business with?" and "Can you know who you are doing business with?" The answers to all three of those questions are more complex than one might initially assume.

I am part of a community of researchers currently studying digital certificates and signatures for the purpose of electronic commerce, access control and general Internet security. This community consists primarily of application developers who need the security public key authentication promises to provide. We have found earlier thinking about certification and authentication inadequate for our needs and have therefore been forced to study the nature, content, use and meaning of certificates. We are developing new forms of certificate to meet our needs.

Our work has shown that the most important question to answer is: "What do you need to know about the person with whom you are doing business?"

In this course of this work, we have uncovered a number of commonly held but mistaken beliefs. It is important to those of us who are working to establish truly useable public key authentication and authorization that these mistaken beliefs not find their way into legislation. Therefore, I list some of these mistaken beliefs below and applaud H.R. 1903’s call for a study of this topic by the NRC.

Some Commonly Held Mistaken Beliefs

"Without a KMI of trusted certificate authorities, users cannot know with whom they are dealing on the network...."

[McConnell and Appel, "Enabling Privacy, Commerce, Security and Public Safety in the Global Information Infrastructure", report of the Interagency Working Group on Cryptography Policy, May 12, 1996; [quote from paragraph 5 of the Introduction]]

Perhaps the most persistent mistaken belief is that the Internet needs a Key Management Infrastructure (KMI) [more often called a Public Key Infrastructure (PKI)] in order for a user to know with whom he is dealing. This PKI is assumed to consist of a hierarchy of trusted Certification Authorities and on-line directory services from which one might obtain certificates. The Certificates are assumed to be so-called "identity certificates" – digitally signed instruments tying together a name string and a public key.

The quoted statement is false. One can know with whom he is dealing on the network without a PKI. Perhaps more surprising is the recent result of our research that a formal PKI as described in that document is less secure than a distributed network of certificates, with each keyholder [the person (or other entity) holding and controlling a private key corresponding to a given public key] issuing his own certificates, as one finds in the SDSI proposal by Rivest and Lampson.

A Certificate binds a public key to a person.

An "identity certificate" does not bind an identity or a person to a public key. It binds a name string to a public key. The underlying mistaken belief is that each name string is somehow naturally bound to a person. That is an assumption we use in our daily lives and have used for as long as humans have given names to other humans. However, it is no longer true the way it would have to be, in order for a person-to-key certificate to be built. I discuss this in greater detail later.

The world needs a PKI in order to enable electronic commerce.

Electronic commerce has been happening for many years, in the form of telephone ordering with credit cards. On the Internet, the same model applies and is in operation today. Neither of these instances of electronic commerce uses a PKI.

More recent developments in electronic payment, such as CyberCoin, NetBill, Millicent, Mondex, VisaCash and DigiCash all operate without a PKI.

The only payment mechanism so far designed to employ a PKI is the Secure Electronic Transactions (SET) protocol, by VISA and MasterCard, for credit card payments. However, the PKI for this protocol does not use "identity certificates" and therefore does not fit the definition usually assumed when one claims that a PKI is needed to enable electronic commerce. The vast majority of certificates in SET are what we call "authorization certificates" – binding a permission to a key. In the SET cardholder case, the permission is the permission to use a given credit card. There is no name in that certificate.

Non-repudiation is derived from a trusted Certificate Authority.

It is true that if one has a seriously flawed Certificate Authority issuing certificates, then those flaws form a convenient excuse for repudiating a digital signature. However, non-repudiation depends on proving that the indicated keyholder was in fact in sole possession and control of the indicated private key at the time the signature was made. No Certification Authority can make that guarantee. The mere existence of a certificate has no impact on whether a private key was under the control of some indicated person at a given time.

Non-repudiation is possible.

Given the current state of protection of operating systems, it is not possible to protect all channels for employing a private key so that only the proper owner of the private key can use it. This situation is expected to continue into the indefinite future. "SmartCard" technology to protect private keys can not solve this problem. Therefore, it is unlikely that digital signatures will ever be non-repudiable.

It is a common assumption in cryptographic research that one operates with a Trusted Computing Base (TCB) and under that assumption, one can talk about non-repudiation. However, the academic assumption of a TCB does not match the real world and it would be a mistake for our laws to assume that it does. That is, one might write laws to make a given person responsible for all actions of a given private key, once a particular kind of certificate has been issued, but this puts a burden on the user heavy enough to discourage him from allowing that kind of certificate to be issued.

There will be (or should be) a global directory of public key certificates.

When the oldest standard certificate form, X.509, was created in the 1980’s it was part of a larger project, X.500, which was to be a distributed, global directory of named persons (and other things). The notion that such a directory will come about has persisted and is even present in some plans today. However, there is a reason this directory effort failed back in the late 1980’s and has never been implemented since. It was assumed at the time that companies and agencies would build their parts of such a directory, issuing certificates to their employees. Company directories would then be placed on-line and linked together to form a global directory. What was forgotten in those plans was that most companies and agencies consider their employee lists to be proprietary. For example, will I ever be able to go to a global directory to look up one of my friends at NSA, find his public key and send him confidential mail? Of course I won’t. If I find his key in any directory, it will be in a local directory of keys I build and keep for my own use.

History of Identity Certificates

Diffie and Hellman, in their paper introducing the concept of public key cryptography [Whitfield Diffie and Martin Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, November 1976, pp. 644-654], noted that public key cryptography had the chance to do away with couriers of secret keys between correspondents. "Given a system of this kind, the problem of key distribution is vastly simplified. Each user generates a pair of inverse transformations, E and D, at his terminal. The deciphering transformation, D, must be kept secret but need never be communicated on any channel. The enciphering key, E, can be made public by placing it in a public directory along with the user’s name and address. Anyone can then encrypt messages and send them to the user, but no one else can decipher messages intended for him." They called this public directory the "Public File".

Loren Kohnfelder, in his bachelor’s thesis in electrical engineering from MIT [Loren M. Kohnfelder, "Towards a Practical Public-key Cryptosystem", May 1978], noted: "Public-key communication works best when the encryption functions can reliably be shared among the communicants (by direct contact if possible). Yet when such a reliable exchange of functions is impossible the next best thing is to trust a third party. Diffie and Hellman introduce a central authority known as the Public File."

Kohnfelder then noted, "Each individual has a name in the system by which he is referenced in the Public File. Once two communicants have gotten each other’s keys from the Public File then can securely communicate. The Public File digitally signs all of its transmission so that enemy impersonation of the Public File is precluded." He then noted problems in this operation, including the need to make and break connections to this Public File, the potential performance bottleneck, the complexity of maintaining such a large system, the control of access into the huge database, etc. He then introduced the concept of a certificate – a signed (name, key) entry, like the response from the Public File, but able to be communicated without direct connection to a centralized database.

About 10 years after the work of Kohnfelder, the X.500 proposal was published. It was to be a global directory of named entities. To tie a public key to some node or sub-directory of that structure, the X.509 certificate was defined. The Subject of such a certificate was a path name indicating a node in the X.500 database – a so-called "Distinguished Name". The X.500 dream has effectively died but the X.509 certificate has lived on. The distinguished name took the place of a person’s name and the certificate was called an "identity certificate", assumed to bind an identity to a public key in the manner described by Diffie, Hellman and Kohnfelder.

Flaw in the concept of Identity

Throughout human history, until the last century or so, people lived and operated in small communities. In such a small community, if Alice talks to Bob about Carol, Alice and Bob can use Carol’s name with assurance that the name identifies the same person to both of them. Also in a small community, there are effectively no secrets. Therefore, the name "Carol" carries with it a great deal of information about her.

Over this history, the habit developed that a name stands for a person and all of that person’s important characteristics (marital status, dependability, credit worthiness, etc.). The sum total of those characteristics amount to a person’s Identity.

Therefore, when we lived in small communities, we learned

name = person = characteristics = identity

but now that we no longer live in such small communities, our habits, language, laws and customs retain that learned lesson. More specifically, Diffie and Hellman, in 1976, wrote "…E can be made public by placing it in a public directory along with the user’s name and address. Anyone can then encrypt messages and send them to the user…" as if the user’s name and address were enough to identify that user to everyone else in the world.

If I want to send a message to my old friend Bob Smith, I can not look him up in a global public-key directory unless I know his current name and address. If I am in contact with him, then I can get his public key from him directly (as Kohnfelder recommended as the most secure method of getting a person’s key). If I am not in contact with him, there is no certainty that I know his current address. If I look up all Bob Smith entries in that directory, I am likely to find thousands. Do I encrypt this sensitive message to all of those thousands of Bob Smiths?

The flaw here is that the telephone book model, which Diffie and Hellman used, is not appropriate for a PKI. The telephone book does not claim to be able to let me find all my old friends, with certainty. For that I need a personal address book and communication with mutual friends.

The more general flaw here is that the lesson that name = identity was learned in small communities where names were both unique and meaningful. In any society as large as even New York City, much less the global Internet, we can always make names unique but not meaningful. For a name to be meaningful to me, I must have it in my head. I can not hold in my head as many names as would be in a global directory. That is why I keep a personal address book.

Similarly, that is why any certificate mapping a name to key must come from my own personal directory if I am to find the key with certainty. The reliability of a Certificate Authority is of minor importance to me when I, as a human user, can not disambiguate the names I find in the certificates it issues.

Nature of certificates for electronic commerce and Internet use

If we give up on so-called identity certificates to provide the security we need, what can we use?

The SPKI group of the IETF answered that question the same way VISA and MasterCard did: authorization certificates. A SET cardholder certificate has no name inside. Instead, it binds a permission to use a particular credit card to a particular public key. This certificate gives the keyholder that permission, the way a physical credit card gives the cardholder permission. Merchants in this country often ignore the name and signature on a credit card. The name, if any, on an ATM card is definitely ignored by an ATM or point-of-sale terminal.

An authorization certificate empowers a public key by delegating some permission to it. It must be issued by some entity that has the power to delegate that permission. So, for example, SET cardholder certificates are to be issued by the entity issuing the physical credit card.

We can imagine many kinds of empowerment. A bank might issue certificates giving the power to an account holder’s key to make withdrawals from a given checking account. A corporation’s system administrators might issue certificates to give specific users the power to log in on the corporation’s machines from over the Internet, through the corporate firewall. An online magazine might issue certificates giving subscriber’s keys the power to gain access to a month’s publication. A lone citizen at home with a PC connected to the Internet might issue a certificate empowering the public key of his child to write into a certain directory on that PC.

In general, we predict that each computer owner (and therefore eventually each human on Earth) will issue authorization certificates. The details of how such certificates are linked, whether name spaces are used and how they are linked, etc., are given in on-line documentation of this research. However, the future we envision has no use for global names and no clear use for large directories of certificates. It is always possible that some use for such PKIs might appear, but none is apparent at this time. Therefore, legislation mandating such PKIs appears to be out of step with recent developments. Such legislation even runs the risk of retarding the future development of public key authentication and authorization if developers are forced by law to use obsolete technology.

Hearing Issues

What, if anything, is needed legislatively to help electronic commerce flourish through the use of digital signatures?

At this time, no legislation is needed, unless it is possible to prevent State legislation. We need to allow users of certificates to define and implement what they need without legal interference.

Would a limited form of preemption by the federal government pave the way for new technical standards to help spread the inexpensive uses of this technology?

The most beneficial action by the federal government would be to encourage the research into the nature, content, meaning and use of certificates. We are not yet in a position to state that we know what should be in technical standards. The standards we are writing today must be considered temporary, to be used while we learn from experience.

What lessons can be drawn from the work of differing nations and states?

As various nations and states encourage digital signatures, we are likely to learn from their experience. However, we have not seen enough years of application use to form any conclusions at this time.

What are the needs of the varying concerns in this debate: CA’s, their users, and trusting third parties?

Our research focusses on the needs of users (both holders and verifiers of certificates). I can not speak to the needs of CA’s or trusted third parties.

What would be the ideal forum for discussion and resolution of these issues?

The NRC study proposed by H.R. 1903 should be an excellent forum.

What are the varying methods currently available to digitally sign a document?

There are many different public key algorithms available for forming digital signatures. Independent of algorithm, those signatures are meaningless unless the signing key has been empowered by the appropriate certificate. Our research has come up with a non-exhaustive list of over 10 types of certificate, of which the large-PKI "identity certificate" is only one. The most common are likely to be authorization certificate, SDSI name certificate, SSL certificate, e-mail certificate and auto-certificate.

Note: an SSL certificate appears to be an "identity certificate" but SSL provides no machinery to use the certified name in any security-relevant way. Therefore, it functions as an authorization certificate giving permission to establish an SSL connection while the name it contains is ignored in the trust management computation.

E-mail certificates are currently of PGP or S/MIME format - binding a key to an e-mail address. These should eventually be supplanted by some combination of SDSI and DNSSEC certificates.

An auto-certificate is one issued by the same key as the subject - giving information about that keyholder for which the keyholder is the most trusted source. For example, the keyholder himself is the most trusted issuer of a certificate giving his name and address for the purpose of sending him money.