Slagell.name

A Survey of PKI Components and Scalability Issues University of Illinois at Urbana-Champaign The ability to communicate securely is desired for many of our PKIX is a PKI that uses X.509. The X.509 standard specifies a daily tasks. In the digital world, encryption is employed to achieve certificate format and procedures for distributing public keys via goals of confidentiality. Private key or symmetric encryption PKCs signed by Certificate Authorities (CAs). PKIX defines the algorithms are very fast and are still used as a part of most PKI system architecture along with an X.509 PKC profile and encryptions systems. However, decades ago it was recognized standard procedures for registration, initialization, certification, that key management using only symmetric key cryptography key generation, recovery, update, expiration and compromise, quickly becomes unmanageable for one-to-one communication cross-certification and revocation of certificates.
within large groups. The reason is that a separate key is needed The architectural model consists of five components as speci- for each pair of users communicating instead of just one key per user. Public key or asymmetric cryptography was developed to address this issue, allowing each user to have one public key.
• Registration Authorities (RAs) that vouch for the binding Now if Alice wants to send a message to Bob, she encrypts it between public keys and certificate holder identities or other with Bob’s public key. Similarly, if Carol wants to send a message to Bob, she uses that same public key. Only Bob, who has the • PKC owners that can sign digital documents and decrypt corresponding secret key, can decrypt Alice or Carol’s messages.
Though one serious problem remains; how can Alice be sure that • Clients that validate digital signatures and their certification the key is actually Bob’s public key and not Eve’s public key? paths from a known public key of a trusted CA and encrypt Public Key Infrastructures (PKIs) help solve this problem. The documents using public keys from certificates of PKC hold- purpose of a PKI is two-fold: (1) to help Alice retrieve Bob’s public key and (2) to give Alice confidence that the key really • Repositories that store and make available PKCs and Cer- belongs to Bob. This paper is a result of an investigation into the scalability of PKIs. In it, we present the most common PKIimplementations and discuss important scalability issues related In order for an individual to start using the PKI, she first needs to register by sending a request for a PKC to a CA. Along with In section II, we present an overview of 3 major PKIs.
the request, users must provide some other information like their Section III describes different problems with traditional PKIs name (e.g., common name, domain name, IP address) and other during enrollment and certificate issuance along with three dif- attributes they wish to be put in their PKC. Prior to the creation ferent solutions to those problems. Section IV discusses several of a certificate, the CA must verify that the information provided certificate revocation systems and scalability issues with each.
by the user is correct and that the name belongs to that user. This Most recently, people have enhanced PKIs by providing real-time process of verification can be done directly by the CA, but it is services; section V reviews some of those services. Section VI more commonly done by RAs. An RA can verify the identity of the user at the moment it receives a request for a PKC, and thenit will forward the request and the verified information to the CA which will create the certificate, sign it with the CA’s private key, First, we review Public Key Infrastructure using X.509 (PKIX), and distribute it to the user. The main idea of a certificate is to one of the two most popular PKIs. PKIX is based on the ITU- bind an identity with a public key. The public-private key pair T Recommendation X.509 Public Key Certificates (PKC), and can be generated by the CA, or the public key can be presented its study will help us better understand directory-based PKI by the user as part of the attributes. If the key pair is generated by solutions. Then we provide an overview of Simple Public Key the CA, then it must be sent back to the user by trusted means.
Infrastructure (SPKI) which is an effort to produce a certificate If the user provides the public key, she should prove that she has structure and operating procedure that is easy to use, simple and extensible. We conclude this section with a brief discussion of The initialization process consists of an End Entity (EE) (e.g., Pretty Good Privacy (PGP), the other of the two most popular a client using a web browser) retrieving all the values needed to PKIs. PGP bases its structure on a so called web-of-trust where start communicating with the PKI, like the CA’s public key that users decide which keys must be trusted and at what levels.
will enable the subject to verify PKCs signed by the CA. If Alicewants to communicate with Bob, she must first go to a repository 1This work was funded by the Office of Naval Research under contract number and retrieve Bob’s certificate. These repositories are like phone N00014-03-1-0765. The views and conclusions contained in this document are directories with certificates indexed by users names. One difficulty those of the authors and should not be interpreted as representing the officialpolicies, either expressed or implied, of the Office of Naval Research or the at this point, called the John Wilson Problem, is how Alice can be sure that she has the correct John’s certificate and not some other John’s certificate. A partial solution is achieved by having The John Wilson problem in section II-A proves that names the CAs verify the names during enrollment to assure they are cannot always work as identifiers, and this is a serious drawback locally unique. Additional information could be added to the of PKIX. CAs already have to locally distinguish between John certificate’s name so it will be different from all other names Wilsons. To globally extend names, users need to know the issued by that one CA. Still, we could find two or more John extra information added to locally distinguish names and the Wilson with certificates issued by two separate CAs.
issuing CA. In contrast, SPKI uses Simple Distributed Security Once Alice has Bob’s certificate signed by some CA, she can Infrastructure (SDSI) names to create globally unique identifiers.
verify it if she trusts the CA and has already its public key. If An SDSI name is an S-expression with the word “name” and not she has two options: discard Bob’s certificate or get Bob’s the intended name. For example, jim: (name rafael) is the basic CA’s certificate. After verifying the certificate(s), she can use name “rafael” in the space defined by jim. SDSI names can also Bob’s public key. Now she can communicate securely to Bob be compound, for example, jim: (name rafael adam) is the basic by encrypting messages using his public key. These messages name “adam” defined by rafael and indirectly referenced by jim.
can be part of a session key sharing protocol, such as in [10], in There are several ways to make names globally unique identifiers.
order to use faster symmetric key cryptography for the remaining Because keys—and most likely their hashes—are unique, they communications. For further proof of identity, Alice can send can serve as unique identifiers. Fully-qualified SDSI names must a challenge to Bob encrypted with his public key. Only Bob, include the name of the space in which they are defined. SPKI knowing the corresponding private key, will be able to decrypt supports compatibility with X.509 names by converting those the challenge and respond to it, thus proving his identity.
names to SDSI names, for example (name <root key> <leaf Key pairs need to be updated regularly and new PKCs issued name>) and (name <root key> <CA1> <CA2> . <CAk> mainly for two reasons: the key pair has exceed its predefined <leaf name>) are examples of X.509 names converted to SDSI lifetime or the private key has been lost or compromised. In either case, the PKI must provide a smooth transition from the The SPKI authorization process can be summarized in 6 steps: old key pair to the new one. The worst scenario is when the root 1) Alice wants to access a resource and asks the resource CA’s key has been compromised. In this case, the root CA must owner (or administrator) to grant her access.
generate a new key pair making useless the paths underneath it in 2) The owner decides if the request is valid and what level of the hierarchy until all the revoked certificates issued by the root CA are replaced with new PKCs. X.509 defines one method to 3) The owner creates an authorization certificate for Alice revoke certificates where each CA periodically (e.g., hourly, daily, binding a public key, for which Alice has the corresponding or weekly) issues a signed list containing the serial numbers of private key, to an ACL and signs it. The certificate must be revoked certificates called a Certificate Revocation List (CRL).
Besides checking the signature of the certificate, clients should 4) Alice presents a signed request to access the resource.
get a recent CRL and check that the certificate is not in the list.
Alice’s authorization certificate accompanies this request.
One more aspect defined in PKIX is cross-certification. Cross- 5) The resource manager checks that the authorization cer- certification is used to allow users under one CA or domain to tificate is valid (i.e., signed by the resource owner) and communicate securely with users under a different CA or domain confirms that the signature was made by the key in the when the CAs do not share a common root. Cross-certificates can be issued in one direction or in both directions between two CA’s.
6) Finally, if either the certificate is invalid or the signature is The PKCs we have discussed so far are used to perform bad, the request is denied. Otherwise, Alice gains access to identity-based access, but for many systems rule-based or role- based access is desired instead. These forms of control require As an alternative, authorization could have been performed additional information that is not normally included in PKCs.
using a combination of identity and attribute certificates as in PKIX defines an Attribute Certificate (AC) that binds this extra PMI. Here, Alice can have an SDSI name bound to a public information as a digitally signed data structure with a reference key by an identity certificate, and an attribute certificate binding back to a specific identity based PKC or to multiple such PKCs.
an authorization to her identity. The identity in both certificates Separating identity certificates from attribute certificates is good acts as a mapping field. Alice must present both certificates practice because attributes/roles change frequently while identities when asking for access. The resource manager can check the tend to remain constant. Privilege Management Infrastructure authorization in the attribute certificate as before but also checks (PMI) is defined in [1] as the set of hardware, software, peo- the identity certificate looking for a match with the identity ple, policies and procedures needed to create, manage, store, specified in the AC. If the authorization is correct and the identities match, access is granted. This has the benefit of being more easily audited. However, anonymity may be preferred in Simple Public Key Infrastructure [4] is aimed to provide an some cases. This is a goal that cannot be met using attribute easy, simple and extensible form of PKI with the main purpose being authorization rather than identification. SPKI (pronounced Two more aspects of SPKI are delegation and threshold cer- “spooky”) defines authorization certificates in addition to identity tificates. Authorization certificates can give users the power to certificates used by PKIX. Certificates come in three categories: delegate authorization to another user without having to ask for identity certificates which bind a name to a key <name, key>, a new certificate from the owner of the resource. Delegation can attribute certificates which bind an authorization to a name be in full or limited by the delegator. Threshold certificates are <authorization, name>, and authorization certificates which bind defined by splitting the right of access between n subjects and an authorization directly to a key <authorization, key>.
specifying a threshold value k. The authorization process now works by having k subjects present a request for access. Only cannot be completely sure that every single user having her old when the threshold value is met can access be granted.
key has received her revocation message. Instead, Alice could Validation and revocation of certificates under SPKI, as in add an option field to her certificate pointing out her web page PKIX, is handled by time-constraining certificates with not- or a directory where other users can check her key status. This before-dates and not-after-dates and by using CRLs. Upon re- solution does not scale well. PGP users have too many different ceiving a SPKI certificate, the validity period is checked, and places to check for keys status and they cannot be sure that the then the certificate’s serial number is compared against those in Having given an overview of PKI, we now consider the main aspects of enrollment and certificate issuance.
Pretty Good Privacy (PGP) was designed by Phil Zimmermann in 1991. PGP differs completely from PKIX in its distributed Enrollment and certificate issuance are two things users need approach to key management. PGP does not use certificates and to take care of before using PKIs. These processes can be as long registration authorities. Instead, PGP implements the concept of and complex as in PKIX or very easy as in PGP. In this part we a “web-of-trust” where users generate their key pairs, distribute will refer to many of the concepts already described in sections II- their public keys and ask other PGP users to sign their public A and II-C to compare both methods, highlighting some of their keys, thus constructing a web of users trusting each other.
Alice, a business representative attending a conference in In trusted third-party methods of key management, like PKIX Boston, meets Bob, a business consultant, and after talking they (Public Key Infrastructure using X.509 standard), when a user realize that there are some projects in which both are interested.
Bob wants to obtain a certificate to prove his identity, he must They decide to keep in contact, and at the end of the conference send a request for a certificate to the CA (a central trusted third- they exchange keys to securely communicate with each other.
party). The request may contain Bob’s public key or the CA may Their keys (or hashes) may be impressed in their business cards instead generate a key pair for Bob and distribute it along with and available at some web site or directory from which they can his certificate. To process the request the CA must verify Bob’s be fetched. Carol, an acquaintance of Alice, decides to take part identity and that the public key belongs to him. After that, it will in these projects but wants to communicate with Bob first. Bob create a certificate for Bob and sign it using the CA’s private sends his public key to Carol, but she would have no way to be key. Finally, the CA sends the certificate (and possibly the new sure that the key is really Bob’s key and not that of an impostor private key) to Bob. This process sounds simple but has several trying to steal from Carol, except that Bob sends his key signed by Alice (and possibly some other users). Since Carol knows Alice • It is hard to determine the level of trust in Bob’s identity and trusts her to sign keys, she can be confident that the key is actually Bob’s. From now on, Carol and Bob can communicate • It is hard to define the relationship between Bob and the CA that certified his public key and to specify the relationship The main advantage of PGP is that users can manage their own keys. PGP does not need a central authority saying which keys • Having a “single trusted entity” creates security, administra- are OK to trust and which keys have been compromised. PGP provides each user with a public-ring. A public-ring is a key • Certificates and keys must be securely distributed to end repository where users can store keys they receive and assign levels of trust to them. It is not clear how good it is to leavethe decision about trustworthiness to end users instead of having Referral methods such as PGP solve many of the problems a central authority that takes care of validation and verification mentioned above. PGP employs the concept of “introducers”.
as in PKIX. In the example above, when Carol receives Bob’s Introducers are users of the system signing keys of other users, key, she trusts it because it came signed by Alice. Alice’s key is presumably friends or people they know and with whom they within Carol’s public-ring and has a level of trust high enough exchange keys face-to-face. If Alice knows Bob, she can sign (assigned by Carol since she personally knows Alice) to sign keys.
his key, and then when Bob tries to communicate with Carol Carol can have more keys in her public-ring that are trusted just he will present his key signed by Alice. If Carol also knows for communication but not for signing other keys. Additionally, Alice, she will trust Bob’s identity. This process allows users to Carol can define her own policy so she will accept a new key only construct a web-of-trust. Additionally, users can assign levels of if it is signed, for example, by at least three other keys she trusts trust to the keys they use; some keys may be trusted to sign other for signing. Carol can modify her public-ring and levels of trust keys, and some keys may be trusted just to identify their owners.
at any moment. If a key has been compromised, she can delete However, referral methods are not a complete solution and suffer it so she will not accept a message signed by that key. She can also accept, by her own risk, keys that are not signed or signed • An introducer must be sure of Bob’s identity and that the by people she does not know or trust.
public key presented belongs to him. In our example, this Revocation is not formally addressed in PGP. If Alice’s key likely means Alice has met Bob in person to get his key or has been compromised, she must communicate so immediately.
Alice can create a revocation message saying that her key has • It is very possible that Carol does not know Alice, and so been stolen and that nobody should trust a message signed by that key anymore. Finally, she must create a new pair of keys • Currently, key revocation is not formally addressed for and distribute her new public key. The problem here is that Alice As seen above, enrollment and certificate issuance in PKIX using a collaborative web-based trust scoring system. FreeICP is a process that can take a long time to finish. Online CAs proposes a CA hierarchy with a root CA that certifies two types enhance this process by making it faster. Online enrollment of intermediate CAs: Entry Level (EL) CAs and Verified Identity follows almost the same steps as before, but now instead of (VI) CAs. The main role of an EL CA is to generate short- having the CA carefully verifying users’ information, an online lived certificates online to any user requesting one. The EL CA challenges a user with an e-mail sent to the address provided CA performs minimal validation by following a naming policy, within the request. Once the user successfully answers it, the avoiding duplicated entries and verifying the validity of the e-mail online CA will send her certificate (and maybe her private key).
address by sending a message to it. Through EL CAs, FreeICP This method allows e-mail addresses to be bound to public keys, puts a valid, working certificate into the user’s applications though it relies on the non-existent security of e-mail protocols.
immediately and for free. VI CAs issue long-lived certificates A more secure example of an online CA is a Kerberos CA. Here, once users have met specific levels (scoring) of credibility and Kerberos identities are bound to keys and the identity is securely trustworthiness. The hierarchy can even define several CAs, each verified with a Kerberos ticket. Another difference with traditional with successively more stringent scoring requirements. The VI enrollment is that online CAs usually issue short-lived certificates.
CAs also have both X.509 certificates and PGP key-pairs so they Near the expiration of certificates, users may ask for new ones if needed. Unlike traditional and online enrollment, PGP provides a An EL CA certificate gives the user a fully-functional way completely different solution. There are no central authorities that to identify herself. Applications needing higher levels of trust- take care of the process and the certificates. Users create their own worthiness can insist on a VI CA certificate, forcing the user keys and start using them. Certificates gain value by the signatures to get one by improving her score. The scoring system consists of introducers. Additionally, users can publish their public key of a policy specifying different types of proof of identity that a in directories where other users can retrieve them in order to user can present and the points (score) assigned to them. It also communicate with each other, but this is not a requirement.
specifies two types of validators that are in charge of collecting Scaling enrollment and certificate issuance presents new chal- these proofs: automatic validators and user-driven introductions.
lenges. For PKIX, cross-certification and Bridge CAs (BCA), Automatic validators are programs that verify some of the user’s as described in [18], can be used to allow users under differ- personal data through automated queries on public web sites.
ent domains (and possibly different CAs) to communicate with Addresses and phone numbers, country-specific identifiers in pub- each other. The problem is that solving organizational issues lic national databases, PGP key-based introduction, photographs (especially about the meaning of “trust”) is not always easy. We and other human-verifiable data are examples of personal data discuss this further in section V-B. Besides that, implementing a collected by an automatic validator. User-driven introduction deals large scale PKIX system incurs several costs. Certificate requests with FreeICP users introducing new users to the system and must be manually verified and processed; so new staff must be users presenting cross-certification from other CAs as a proof hired for this task. Online CAs may reduce these costs, but more of identity. One last advantage is that the scoring process is a computational processing and good channels of communication natural solution for contention. If two or more users are claiming are required. Assigning the verification process to already existing the ownership of certain identity, the dispute will be solved by staff can be another option. Hardware related costs are also giving the identity to the user with the highest score since scores important. Those costs may be the most expensive part if the are improved by presenting more and better proofs of identity.
PKI is implemented using some kind of device like smart cards to protect users’ keys. The PKI then needs to provide its users • the level of trust to assign a user’s identity by employing a with special hardware like smart card readers as well. It can be scoring system to reflect trustworthiness.
argued that this is not a direct PKI cost but a cost for users • the relationship between the user and the CA and the way it of the PKI solution. Hardware costs must also include central is implied in the user’s certificate. The CA plays an active equipment to work with smart cards when issuing keys and role in the verification of the user’s identity. Recall that a certificates. Certificate revocation and CRL distribution costs must VI CA certificate is issued once the user has proved, with also be considered. As indicated by the National Institute of certain level of trust, his or her identity.
Standards and Technology (NIST) in [16], a PKI should expect to • not being able to control the trustworthiness of their certifi- revoke about 5 percent of all certificates issued each year because cates, as viewed by others, which is a problem in PGP. The the corresponding private keys have been lost or compromised.
scoring system allows users to improve the trustworthiness Another 5 percent of certificates are expected to be revoked because of users leaving the system. One must also account for certificates generated for completely new users. It is expected that5 percent of the certificates held in a given year will be for these new users. In contrast, the distributed nature of PGP and its zero- In [5], Jon Callas presents a Self-Assembling PKI as a new way cost enrollment solution helps with some scalability issues, but of constructing certificates that helps PKIs provide a widespread now revocation becomes more difficult.
deployment of secure communications. Self-Assembling PKI uses PKI literature presents several other works that try to improve existing PKIs, security standards, and systems to achieve its goals.
enrollment and distribution of certificates and keys. We describe The infrastructure consists of a server sitting within the network three such works and the problems each one solves.
that creates keys and certificates for all of the network users. By sitting inside the network, the program notices the presence of FreeICP [7] combines directory methods with referral methods already authenticated users (users of the network must have been by having a CA hierarchy that mimics PGP’s web-of-trust model authenticated before by another system, probably by providing a combination of user name-password) and automatically creates certificates for them. These certificates can be augmented as more • increases the level of trust in user identities since each information is learned about the users. Notice that no additional program has the ability to validate identities at its own level enrollment is necessary since the user has been already authorized to use the network, and we assume the organization owning the • has a CA that is just an entity that issues public key network has already enrolled the user and hence her identity has certificates. Trust is now managed by each program’s identity already been verified prior to granting access to the network.
Here is an example of the communication process described by Callas. Alice wants to securely send an e-mail to Bob.
Alice connects to her usual mail server. A proxy mediates this Certificates are usually given a fixed lifetime, after which connection, and after she successfully authenticates to the mail they expire. However, it is possible that a certificate becomes server, it creates a short-lived certificate for her. Alice sends the invalid before its expiration. This could happen if the private e-mail to Bob. Maybe more information is learned about Alice key corresponding to the certificate has been compromised.
from this e-mail and is added to her certificate. Since Bob is More frequently though, a person will leave a position within a user on the same mail server, the proxy creates a short-lived an organization, and the management will want to revoke the certificate for him and encrypts Alice’s e-mail using Bob’s public certificate to prevent them from posing as a member any further.
key. Bob connects to his usual mail server and after successful A member could also move within an organization, thus changing authentication, the proxy decrypts Alice’s e-mail and presents it the systems to which she has access. This will likely require to Bob. As an option, the message can be modified to let Bob the revocation of attribute certificates. In [14] it is estimated know that it was delivered securely.
that 10% of certificates will actually need to be invalidated before expiration. Therefore, it is important for most PKIs to • widespread deployment of secure communications.
have methods to perform timely revocation of certificates. In this chapter we discuss some of those methods.
It is important to note that while most systems do have methods to deal with revocation, these can be costly to implement.
• increased level of trust in users identities.
Implementors of a PKI could choose not to address revocation and • no need for a “single trusted entity” or certification authority.
instead use alternatives that minimize the risk of not revoking • no need for distribution of certificates and keys.
keys. A simple solution might be to always use very short- • revocation by the use of short-lived certificates.
term certificates. It takes significant time and effort to crack a key. By reducing the life of the key, the owner reduces the The work in [11] describes the concern of Canada’s Govern- probability that it will be cracked while it is still valid. Another ment to deliver secure online services. The main contribution of alternative is to store keys in tamper-resistant hardware. However, this paper is the separation of registration and enrollment for a this only protects the private key from direct attacks. The public PKI solution. Individuals will register with a central authority key is still exposed, and attacks can be mounted with just the and get an epass. An epass is a pseudo-anonymous public key public key information in order to reveal the private key. Of certificate where the identifier is a Meaningless But Unique course the feasibility of such an attack depends largely upon the Number (MBUN). At this point users are not required to identify algorithm and key size. Additionally, tamper-resistant solutions themselves. Later on, users will need to use government programs, are not based off of well understood mathematical problems that and they will enroll in such programs. The enrollment process we believe to be hard; instead they are based off of electrical consists of a user presenting her epass and proofs of identity engineering or physics problems which have shorter lifespans.
to the program. The program will verify the user’s identity and Just because something is tamper-resistant today, that does not create an association between the MBUN from the user’s epass give one confidence that it will be in a few years. For example, with a Program ID (PID) number. The PID is the index for many tamper resistant technologies, including smart cards, have the user within the program. Enrollment must be done once fallen prey to attacks that analyze electrical signals. This being for each government program on the occasion of its first use.
said, we feel that tamper-resistant hardware is a good second layer Once enrolled, users can authenticate themselves with their epass, of defense but should not solely be relied upon.
and the program will uniquely identify them by the MBUN-PIDmapping.
It is interesting to notice that the Canadian way for secure Certificate Revocation Lists (CRLs) were one of the first online services is very similar to the ideas implemented by methods to revoke certificates. These so called “black-lists” are Microsoft in its .Net Passport single sign-on solution.
lists of all currently valid (meaning non-expired) but revoked The main advantages of this idea are that: certificates. A CA would issue one CRL for all certificates that • it provides a single sign-on solution for online services.
it had revoked. In [16] it was suggested that CAs should issue • data mining between organization can be done using MBUNs CRLs on the order of every two weeks. No matter how often the CRLs are updated, it must be done in a manner that a user • on its own, the certificate (epass) contains no information can verify that she has the latest CRL. This could mean that the user knows it is updated at a specific interval, or the CRLs could • individuals can use more than one epass, allowing them to indicate when the next one would be issued.
fine-tune their anonymity based on their level of privacy Of course, one of the main disadvantages of CRLs is unscala- bility. These lists can become quite large for a user to download.
The problem is exacerbated if revocation information needs to be handling the delta-CRLs at all. The CA does more work now that very fresh. In this case, the CRL must be updated more frequently, it must create more updates, since FCRLs contain the absolutely and hence downloaded all the more frequently. So there is this freshest information. Moreover, it must serve this data or rely on trade-off that we often find between freshness and scalability. At some trusted system to serve it. The total network traffic may the one end we could have no CRLs which is very scalable, but the decrease if people are not willing to pay for the FCRLs. It would information about certificates is stale. On the other end, we could be interesting to see if this system would work socially. People update daily, but this is not very scalable if a user must download do not like to pay for something that they got for free before or many CRLs, even in the age of the networked computer.
things that they do not understand. If the CAs cannot get enough It is important to realize that downloads need not be syn- subscribers, the costs per user for FCRL access would be too chronous, though. This fact can be leveraged to provide scalability high for most individuals. Overall, the main advantage is that by downloading CRLs in times of low network use, such as during the FCRL can contain the absolutely most current information, the evenings. Going a step further, clients could be configured to but this comes at the cost requiring a trusted server that is download CRLs at random times during the evening to avoid always online. This FCRL server can then become a point of bursts of traffic. This would be better than everyone trying to DoS attack. Replication thus becomes necessary for resilience, download certificates at, say, midnight. It has been suggested by but replication among several non-trusted directories is easier some to over-issue CRLs to avoid the bursts of traffic near the than replicating servers providing private data that is being sold.
release off new CRLs. Over-issuing means that new CRLs are Furthermore, what is keeping an organization from caching a very released before all the older ones expire so that there are many current FCRL for all its members? Now the members have fresh different non-expired CRLs at a given moment. In [8], Cooper models how over-issuing affects the peak request rate for CRLs.
Another variant of delta-CRLs is called Sliding Window Delta- While he shows that it does reduce the peak rate effectively, it is CRLs. Presented in [9], Cooper shows how to lower the request important to realize that average workload for a CA is increased, rate of base-CRLs and the peak bandwidth at the directory by and the average request rate for a directory is unchanged.
using his improved delta-CRLs. Typically, a delta-CRL lists all 1) Delta-CRLs: One of the first solutions to address the revoked certificates since the most recently issued base-CRL. So scalability problems of CRLs were delta-CRLs. A delta-CRL is the window over which the information is collected for a delta- just a list of changes to a base CRL. In this situation a complete CRL varies. He suggests using a fixed window size. For example, CRL is issued regularly, but infrequently. In between issues of the a base-CRL may be issued daily with delta-CRLs issued every base CRLs, delta-CRLs are issued that specify new revocations 15 minutes. The window size could be 72 hours, meaning that that have occurred since the release of the last base CRL. This a delta-CRL lists all of the certificates revoked within the past reduces the amount of information that a client must download on 72 hours. If a user never goes say 71 hours without validating a regular basis while still providing information that is fairly fresh.
a certificate, then she will never have to download a base-CRL The end user must still have a mechanism to know that the delta- again! He demonstrates that this is a great improvement over CRL is the freshest out there. So the delta-CRL should be issued traditional delta-CRLs, and he shows how to improve peak request at regular intervals, as well. The most significant disadvantage rates further by over issuing delta-CRLs. Of course, the degree of is that they still do not provide a succinct proof of validity that improvement depends upon optimizing the choice of the window an end user can send to another end user with her certificate.
size for the given base-CRL and delta-CRL periods.
The end user would have to store the base CRL and delta-CRL 2) CRL Distribution Points: Another improvement to CRLs with their certificate to provide proof to an offline agent. Some was specified in the X.509 v2 CRL specifications [6]. In the new methods of revocation provide more succinct proof that a version 2 CRLS, CRL Distribution Points (also called Segmented CRLs) are defined. CRL distribution points fragment the CRL In [6], Adams et al. make two improvements to traditional into smaller parts. If these fragments are organized into logical CRLs as discussed above. The first improvement is almost divisions, it is likely that a user will only need to download functionally identical to delta-CRLs and is more of a political a few fragments rather than the entire CRL. The certificate difference. There is always a balance between freshness and cost specifies which distribution point corresponds to that certificate.
in revocation systems. They feel that because not everyone may be Distribution points can be used with delta-CRLs, as well. Here interested in the absolutely freshest information, it makes sense to the delta-CRLs are broken into fragments—most likely along the charge a premium for the freshest updates. They propose using an same serial number boundaries as the base CRLs—as well. CRL X.509 extension field for what they call the Freshest Revocation distribution points do help to address the problem of scalability Info Pointer (FRIP). This is just a pointer to a special type of by reducing the amount of communication between directories delta-CRL that contains the absolutely freshest information. This and end users. However, it could happen that the fragments of Freshest delta-CRL (FCRL) must be served from a trusted source the CRL do not grow uniformly. Certain distribution points could now since it is issued irregularly, and the client must be assured it grow quite large, and the partitioning of the serial number space is the latest available. However, since it is assumed that the user is purchasing the list, the server must be trusted to some extent The second improvement by Adams et al. in [6] addresses anyway. The purchase price should be enough to make up for the the problem of CRL distribution points that grow non-uniformly.
cost of the CA setting up extra servers.
They create Redirect CRLs (RCRLs) that sit between the end The user is not really benefiting from this system, except that user and the CRLs. The CRL distribution pointer and FRIP the FCRL is more current than a regular delta-CRL. The client now point to redirect CRLs. These redirect CRLs tell users is still downloading as much information as she would with which fragment to look at for the certificate in question. This traditional delta-CRLs. The directory is doing less work. It is not way the serial number space can be repartitioned between CRL distribution points at any time. The problem of course is that there One side effect of this system is that every day a certificate is now more work for the CA, and the client has an extra step holder can get a short proof of the validity of her certificate for of indirection involved in checking any CRL or delta-CRL. We that day. She can bring it with her on a smart card or some would be surprised if the benefit outweighs this extra cost. Adams other media with her certificate to prove validity to an offline et al. provide no evidence that this non-uniform growth of CRL agent. This is the first system we have seen that provides succinct distribution points is actually a problem nor do they indicate how proof of validity to the end user. However, two issues really concern us. First, the CAs now must store private information associated with every certificate. This isn’t a storage issue, but a An alternative to CRLs, which are large signed statements management issue. It is much easier for a CA to protect a few about the status of several certificates, would be signed statements very important private keys from insider compromise than it is about single certificates. Instead of sending CRLs every day, the to protect tens of thousands of pieces of confidential information.
CA could send separate signed statements for every non-expired The second problem is that there is limited granularity to the certificate the CA has published to the directory! It would have to system, and it is fixed once the certificate is issued. It is like they send both positive and negatives statements about certificate status are creating one time signatures, in our example one per day now; otherwise an untrusted directory server could simply neglect for a year. The computational speed of the signature algorithm to send a negative statement, thus leading a client to believe the is directly proportional to the lifetime of a certificate and its certificate is valid. This isn’t a problem with a CRL since the granularity (period of update). It is unclear exactly how much client trusts the CA to indicate all revoked certificates on the list.
faster these one-way functions are compared to traditional public- An untrustworthy directory cannot simply strip out a particular key signature algorithms, but eventually the cost will become certificate from a CRL without invalidating the signature on the unbearable if the update rate is increased enough.
CRL. Thus the client only has to worry about the directory not returning the most current CRL. Dating the CRL and knowingwhen the next one comes out allows the client to notice such Certificate Revocation Trees (CRTs), referred to in [19], are misbehavior by the directory server.
the type first introduced by Paul Kocher in 1998. The basic idea Obviously, this is not a practical solution. While it does of a CRT is that revocation information is provided in the leaves reduce the amount of information downloaded by an end user of a binary hash tree, and the root of this hash tree is signed by significantly, it over-burdens the CA. The CA must not only the CA. To prove that the information a directory gives to a user compute orders of magnitude more signatures, it has to send much is true, it provides the user with the leaf node of interest and the more data to the directories. This extra data is from the signatures minimum number of node values from the rest of the tree in order and the fact that information about valid and revoked certificates recompute the root of the tree. The user then verifies the root value must both be sent. However, Micali [14] does feel that this idea against the signed root that the directory provides. Any alteration has merit in that it is shifting some of the burden away from the to the leaves of the tree will alter the tree’s root. So as long as a directory-to-user communication and back to the communication strong, collision-resistant hash function is used, a directory cannot between the directory and the CA. With CRLs the work-load deceive the user. Also, it only has to provide proof O(lg[n]) in is unbalanced, and most of the traffic is between the users and length, where n is the number of revoked certificates. This is the directory. Micali takes the naive solution above further by much more succinct than an entire CRL, and it may be possible reducing the size of the signature, (hence the data transmitted), for the end user to carry this proof along with her on a smart card and reducing the computational work of performing signatures.
or similar device to prove the current validity of her certificate.
By using the light-weight signatures he proposes, signature sizeis reduced by about one order of magnitude to 100 bits, and thecomputational cost of signing is reduced orders of magnitude. Hecalls this system Certificate Revocation Status (CRS).
The light-weight signatures are created as follows. Let F : {0, 1}100 → {0, 1}100 be a fast one-way function. For everycertificate that the CA issues, it creates two private valuesassociated with that certificate called Y0 and X0. These are each100 bits long. Say that the CA wants to update certificate statusdaily and wants certificates to last for one year before expiration.
Then the CA publishes Y = F 365(Y0) and N = F (N0) as partof the certificate. On day i, the CA publishes Yi = F 365−i(Y0) ifthe certificate is still good. If it has been revoked it publishes N0.
The user checks Yi by verifying that F i(Yi) ≡ Y . If the responseis instead N0, the user checks that F (N0) ≡ N . The security ofthis signature relies completely upon the fact that F cannot be inverted easily. Note that the directory cannot trick the user inany way. If the directory responds with an older Yi, the user will More specifically, the leaf nodes contain information of the detect this. If the directory responds with N0, the certificate must form (i, j) where both certificate i and j are revoked, but no be revoked since otherwise the CA would not have released the certificate number between them is revoked. Such a value can value. All the directory can do is choose not to respond, but it demonstrate that either certificate i or j is revoked, or it can be could do this in any revocation system.
used as positive proof—for any certificate between i and j—that demonstrates validity. Consider the certificate tree in figure 1.
the time, though. WCR also maintains CRLs but with a distinct Suppose a user queries the directory about certificate number 14.
difference; certificates do not necessarily remain on the CRL until Then the directory must supply the leaf node, L2, and also nodes they expire. This is the second difference. A parameter called N0,3, N1,0 and N2,1. These are the siblings of all the nodes on the revocation window size determines how long a certificate is the path from the leaf back to the root. With these nodes and the on the revocation list. More specifically, it specifies an integral leaf, the end user can compute the root which it compares to the number of consecutive CRL publishing dates that the revocation signed root provided by the directory.
information must appear on. By adjusting this parameter, the size Overall, the information sent to the directory is more than in of the CRLs can be adjusted without changing the lifetimes of a simple CRL. However, the benefit is that the end user needs data only on the order of a log of that which a CRL uses. Thisis fine since the CA is only sending data to the directory onceper update, but the directory is constantly communicating datato the end users. So it makes sense to significantly reduce thedata communicated with the end users, even if it comes at asmall cost to the communication sent between the CA and thedirectory. In fact, it is only a quadratic increase in the amount ofdata communicated between the directory and CA.
Naor et al. [15] improved upon Kocher’s CRTs. With Kocher’s CRTs it is possible that the entire hash tree must be recomputedduring an update. Naor et al. sought to save this extra computa-tional work and data transmitted to the directory by reducing theeffect an update has on the hash tree. They accomplish this byusing 2-3 trees instead of simple binary hash trees. 2-3 trees havetwo important properties with respect to their goal: 1) membershipqueries, insertions and deletions only change nodes in the searchpath, and 2) tree nodes have bounded degree. In fact, other treeswith these properties could be used. They mention treaps as analternative with their own set of advantages and disadvantages.
Tree updates—removing expired certificates or adding newlyrevoked certificates—typically involve only the nodes on the path back to the root, but they can also involve the addition or deletionof nodes to rebalance the tree.
In addition to the change at the issuer, namely the specification In their comparisons to CRS and CRLs, Naor et al. find that of the revocation window size, there is a new parameter defined by they have reduced the overall communication between the CA and the user of a certificate. The client defines a clean timer for each directory by orders of magnitude. At the same time they have kept certificate. Put altogether, the protocol for the client is as follows the communication between the user and the directory small when (shown in figure 2). If a client does not have a certificate, she compared to CRLs. They do not compare that communication retrieves a fresh copy and starts her clean timer and a revocation to CRS, probably because they require more client to directory window timer. The clean timer basically determines how fresh a communication. They also do not compare the performance of certificate must be not to have to revalidate it. So if she already their trees to Kocher’s. So it is difficult to predict how much of has the certificate and the clean timer has not expired, she simply a difference their improvements make.
uses the certificate without revalidating. If the clean timer hasexpired, she checks the revocation window timer. If the latter timer has expired, she gets a fresh certificate and resets the timers.
Windowed Certificate Revocation (WCR) is just an improved Otherwise she retrieves the latest CRL (if she does not already method of implementing CRLs, and it applies equally well to have it), and checks the validity of the certificate against the CRL.
delta-CRLs. McDaniel et al. sought a balance between systems If it is on the CRL, she of course drops it. If it is not on the CRL, that always retrieve a fresh certificate and systems using CRLs. It she resets both timers and uses the certificate.
is computationally costly, because of digital signatures, to always Notice that the case when the timers are always set to 0 is retrieve a fresh certificate; and CRLs can be costly in terms of identical to the situation in which only fresh certificates are used.
communication, due to their large size. However, in [13] the The case when the revocation window size is set to infinity is authors should consider that always retrieving fresh certificates the same as using regular CRLs. Only slight modifications are could be more costly than CRLs from the amortized costs of needed to make this work with delta-CRLs. So this is definitely small communications. Regardless, the goal of WCR is to find an improvement to the methods with which they compare their a balance between the two systems through parameters chosen system. More tests would need to be performed to compare it to by the system’s users (both the certificate issuer and users of the certificate). In fact, degenerate cases of WCR turn into the above There are two main differences between CRLs and WCR. First, As Internet connectivity and accessibility have improved, in WCR there must be a method for a user to retrieve a “fresh” people have sought real-time solutions to enhance PKI. These certificate if desired. This service most likely will not be used all services can provide revocation information, offload the work of certificate validation and even be used to enforce organiza- to centralize PKI policies. Clients may request full validation of tional PKI policies. The PKIX community has proposed three a certificate or just ask for construction of a certification path such services: Online Certificate Status Protocol (OCSP), Simple Certificate Validation Protocol (SCVP) and Data Validation and SCVP servers can be trusted or untrusted. An untrusted server Certificate Server (DVCS) protocols.
could supply a certification path. In [2], the authors feel that an untrusted server could also supply revocation information such asCRLs or OCSP responses. There certainly is no problem having OCSP was developed as an alternative to CRLs for the PKIX an untrusted server give a user CRL information. We feel that project. Its purpose was to avoid downloading long CRLs and it may be a little more complicated to have an untrusted server to provide the freshest information possible about certificate provide OCSP responses, and such a protocol must be carefully revocation. An OCSP responder is a trusted server that responds to designed. Obviously, the untrusted SCVP would be giving a a client’s request for information about the revocation status of a client information from an OCSP responder that the client trusts, certificate. A positive response only means that the certificate has though. While path construction may be trivial in single level or not been revoked. It does not imply validity, meaning the OCSP hierarchical PKIs, it can be quite challenging with meshed PKIs responder is not checking the signature on the certificate or its (collections of cross-certified CAs) or what [18] calls bridge- path back to a trusted root. It is not even checking that the serial connected PKIs. Bridge-connected PKIs use Bridge CAs (BCAs) number is that of an issued certificate. Obviously, the responder to connect other meshed and hierarchical PKIs. They consider must be trusted. It could be trusted just to respond for that SCVP servers to be a particular instance of what they call Bridge certificate if the CA issuing the certificate indicates the server as being the official responder for that certificate. A responder could A trusted SCVP server can do more. A trusted server can be also be trusted for all responses if some prior trust relationship as used to handle almost all cryptographic work and network com- been established with the client. An example would be a company munication. By allowing the SCVP server to perform validation that has its own OCSP responder setup to do revocation checking and revocation checks, the client only has to send and receive one message. This could be useful for PDAs with limited wireless In a way, OCSP is really a step back from previously discussed bandwidth and computing power (though cryptography does not certificate revocation methods. It provides shorter responses than take that much CPU load anymore). Even more useful may be full CRLs, but other methods such as CRS provide even shorter the ability to centralize all PKI/PMI policies for an organization responses. Additionally, we are falling back on the use of a with an SCVP server. Using SCVP, the organization has complete trusted third party, namely the OCSP responder. The previously control over how validation is performed. This is particularly discussed methods rely only on untrusted directories. While important when SCVP servers are used as BVAs. Policies can be OCSP does offer the freshest information possible, CRTs can extremely complex and dynamic in bridge-connected PKIs, and offer information nearly as fresh without use of a trusted third the client software is currently not intelligent enough to interpret party. In the OCSP RFC [12], they do not have a graceful way to deal with OCSP responder key compromise. They mention that The authors do note a few important issues. First, a trusted either traditional CRLs can be used for OCSP responders or their SCVP server is trusted as much a root CA. So the keys must keys could be short-lived. It seems that we gain little if we are still be strong and protected carefully. Clearly, compromise of the tied to using CRLs, except in this case the list should be shorter.
key is detrimental and could result in a client accepting ANY We feel that the better of these choices is to frequently change the bogus certificate. Also, it is recommend that the client use an OCSP keys. If archiving of OCSP requests is important, then a unpredictable sequence of identifiers for requests so that it does frequent key change could make audits more complicated. Plus, not fall prey to replay attacks. Lastly, they point out that policy there would still be a need to store CRLs of OCSP keys for information requests and responses are not signed, and hence auditing to work. However, this is a real-time system, and the vulnerable to man-in-the-middle attacks.
responses mean little after the fact. So auditing may not be an Our biggest problem is that the servers are very heavily loaded, issue. In this case, it could be acceptable to use short-lived keys making all of the cryptographic workload even more unbalanced.
as an alternative to revoking OCSP responder keys.
This makes the system even more unscalable. With desktops or An additional scaling problem comes from the fact that all laptops, the client usually has more free CPU time than the server, OCSP responses must be signed. If they are not, someone and moving the burden to the server exacerbates the situation.
can perform a DoS attack by faking messages that say valid So if the client is not a small wireless device with limited certificates have been revoked. But signing every message with bandwidth, the only use we see is in the centralized PKI/PMI a public-key algorithm can overburden a server. It could lead to policy making. This can be quite an advantage in many situations, another type of DoS attack where a malicious user just floods though. This actually helps scaling with bridge-connected PKIs the responder with requests. Caching cannot help us scale either.
because it provides quick updates of complex sets of policies and To prevent replay attacks, the messages must have a nonce, time- may be necessary since most clients are not intelligent enough to stamp or some other unique identifier. Though, if timestamps are interpret and act on those policies. Here an SCVP server acting as used, a client could be configured to accept cached messages up a BVA might not be heavily burdened if it is just set to deal with to a certain age. However, time-stamping has its own set of issues.
certificates for other domains that the client does not understand.
B. Simple Certificate Validation Protocol SCVP is a system that allows clients to offload much of their C. Data Validation Certificate Server Protocols certificate handling to a server. This can help to relieve the work- DVCS is not a replacement for CRLs or OCSP. The purpose is load of a very low powered client, and it allows an organization to extend functionality. In fact, DVCS could not replace CRLs in a large open environment due to scalability issues. A DVCS is like and revocation. In section III, we looked at specific solutions a notary public. It is used to bind a time to a particular event, such that address the scaling issues related to enrollment. We also as the signing of a document. A DVCS issues a Data Validation looked at how the Canadian government has tried to use PKI Certificate (DVC) signing that something happened or was valid at while preserving privacy as best as possible. In section IV, a given time. More specifically, it provides the following services.
we examined some of the more common certificate revocation Certification of Possession of Data is a DVC that states a methods. All of these solutions differ in how they balance the requester possessed data at time x. This is essentially a time stamp amount of communication between the directory and CA with by a trusted third party, namely the DVCS. Certification of Claim the amount of communication between the directory and the end of Possession of Data is almost the same, except that the requester users. Additionally, some of them make trade-offs to work better only shows the DVCS a hash of the data. This is useful if the in an offline environment. Lastly, we looked closely at some of the data needs to be kept private. Again, this is basically just a time newer real-time PKI services such as OCSP, SCVP and DVCS.
stamping service. Validation of Digitally Signed Documents is a These services offer everything from real-time certificate status service that checks signatures on a document, verifies that they checking to complete certificate validation and verification. SCVP are good at a particular time, and signs a DVC stating this fact.
even allows organizations to create central points of management Validation of Public Key Certificates is the same except that the for all certificate handling and PKI policy enforcement.
DVC is validating that a PKC is good at a particular time. This In the end, we found that there are myriad of PKI compo- implies that the DVCS checked the path to a root CA, as well as nents and add-on solutions to balance different kinds of costs.
Depending on the goals and resources of a particular project, the The main benefit of these services is non-repudiation and most scalable PKI solution will look very different. Thus, it is extension of signature validity. By having a DVC, an auditor can impossible to say that PKI does or does not scale, but one can see that the document signature was valid at the time DVC was only say that a particular PKI solution does or does not scale for issued. It doesn’t matter whether the signature key has now been expired or revoked. Without this service a signed document must still be reliably time stamped, and an auditor would have to checkarchives of CRLs to determine the validity of the key (and others [1] A. Arsenault and S. Turner. Internet Draft PKIX: Internet X.509 Public Key Infrastructure: Roadmap, January 2003.
in the verification path) at the time of the original signature. But [2] A. Malpani, R. Housley, and T. Freeman. Internet Draft PKIX-SCVP: Simple now the signature is valid until the DVCS’s key expires. However, Certificate Validation Protocol (SCVP), December 2002.
this can be extended by the DVCS issuing a new DVC before its [3] C. Adams, P. Sylvester, M. Zolotarev, and R. Zuccherato.
Internet X.509 Public Key Infrastructure Data Validation and Certificate As the authors of [3] point out, use of a DVCS would be [4] C. Ellison, B. Frantz, B. Lampson, R. Rivest, B. Thomas, and T. Ylonen.
helpful when performing a transaction involving large sums of RFC 2693: SPKI Certificate Theory, September 1999.
[5] Jon Callas. Improving Message Security With a Self-Assembling PKI. In money. Not only does it check validity of the key for a client 2nd Annual PKI Research Workshop Pre-Proceedings, Gaithersburg, MD, (using OCSP, CRLs or other methods), it provides a DVC which can be used for non-repudiation if needed. However, there is a [6] Carlisle Adams and Robert Zuccherato. A General, Flexible Approach to lot of computation and communication that the DVCS provides [7] Marco Antonio Carnut, Evandro Curvelo Hora, Cristiano Lincoln Mattos, for the client by doing these checks. So we would see DVCS use and Fabio da Silva. FreeICP.ORG: Free Trusted Certificates by Combining being a pay service and likely not to be needed all the time. This the X.509 and PGP Hierarchy Through a Collaborative Trust Scoring Sys-tem. In 2nd Annual PKI Research Workshop Pre-Proceedings, Gaithersburg, is good since it would be hard to scale given the server burden.
Another use might be for a corporation to setup a DVCS server [8] David A. Cooper. A model of certificate revocation. In ACSAC, pages 256–, that employees are required to use. This would create an audit [9] David A. Cooper. A more efficient use of delta-CRLs. In IEEE Symposium trail, and it would allow the company to set strict policies on on Security and Privacy, pages 190–202, 2000.
verification of certificates via the DVCS server.
[10] Whitfield Diffie and Martin E. Hellman. New Directions in Cryptography.
It should be noted that the client still does have the responsibil- IEEE Transactions on Information Theory, IT-22(6):644–654, 1976.
[11] Mike Just. An Overview of Public Key Certificate Support for Canada’s ity of checking the validity of DVCS server certificates through Government On-Line (GOL) Initiative.
traditional methods. In a corporate situation, the client could rely Workshop Pre-Proceedings, Gaithersburg, MD, April 2003.
on the fact of being notified immediately of a compromised DVCS [12] M. Myers, R. Ankney, A. Malpani, S. Galperin, and C. Adams. RFC 2560: X.509 Internet Public Key Infrastructure - Online Certificate Status Protocol key. Other methods may be to use OCSP or CRLs for DVCS key revocation. Using either method, such a compromise is very [13] Patrick McDaniel and Sugih Jamin. Windowed Certificate Revocation. In damaging since it invalidates all the previously issued DVCs with INFOCOM (3), pages 1406–1414, 2000.
[14] S. Micali. Efficient Certificate Revocation. Technical Report MIT/LCS/TM- that key. If a DVC is being used to extend the lifetime of a signature and the DVC is compromised, the signature is now [15] Moni Naor and Kobbi Nissim. Certificate Revocation and Certificate Update.
useless. Redundancy, such as the use of two DVCSs at all times In Proceedings 7th USENIX Security Symposium (San Antonio, Texas),January 1998.
could help, but it is not a solution that helps the scaling issues.
[16] National Institute of Standards and Tables. Public Key Infrastructure Study Strong keys and serious methods to protect them are certainly in Final Report, April 1994. http://csrc.nist.gov/pki/documents/mitre.ps.
[17] Bruce Schneier. Applied Cryptography: Protocols, Algorithms, and Source Code in C. John Wiley & Sons, Inc., second edition, 1996.
[18] William T. Polk, Nelson E. Hastings, and Ambarish Malpani. Public Key Infrastructures that Satisfy Security Goals. IEEE Internet Computing, 7(4),July 2003.
We began by discussing some of the most popular PKI im- [19] Petra Wohlmacher. Digital Certificates: A Survey of Revocation Methods.
plementations, namely PKIX, SPKI and PGP. In all of these In Proceedings ACM Multimedia 2000 - Workshops, November 2000.
systems, there is a need to perform both efficient enrollment

Source: http://slagell.name/Adam_J._Slagell/Publications_files/slagell06a.pdf