Fine-Grained Control of Security CapabilitiesDAN BONEHStanford UniversityXUHUA DINGSingapore Management UniversityandGENE TSUDIKUniversity of California, IrvineWe present a new approach for fine-grained control over users’ security privileges (fast revocationof credentials) centered around the concept of an on-line semi-trusted mediator (SEM). The use ofa SEM in conjunction with a simple threshold variant of the RSA cryptosystem (mediated RSA)offers a number of practical advantages over current revocation techniques. The benefits includesimplified validation of digital signatures, efficient certificate revocation for legacy systems andfast revocation of signature and decryption capabilities.Thispaperdiscussesboththearchitectureand the implementation of our approach as well as its performance and compatibility with theexisting infrastructure. Experimental results demonstrate its practical aspects.Categories and Subject Descriptors: E.3 [Data Encryption]—Public key cryptosystems; K.6.5[Management of Computing and Information Systems]: Security and ProtectionGeneral Terms: Algorithms, SecurityAdditional Key Words and Phrases: Certificate Revocation, Digital Signatures, Public Key Infra-structure1. INTRODUCTIONWe begin this article with an example to illustrate the premise of this work.Consider an organization—industrial, government, or military—where all em-ployees (referred to as users) have certain authorizations. We assume that aPublicKeyInfrastructure(PKI)isavailableandallusershavedigitalsignature,ThisworkwassupportedbytheDefenseAdvancedProjectAgency(DARPA)undercontractF30602-99-1-0530. An earlier version of this paper was presented, in part, at the 2001 Usenix SecuritySymposium.Authors’ addresses: D. Boneh, Stanford University, Computer Science Dept., Gates 475, Stanford,CA 94305-9045; email: [email protected]; X. Ding, School of Information Systems, SingaporeManagement University, Singapore 25976; email: [email protected]; G. Tsudik, School of ICS,458 CS Building, Irvine CA 92697-3425; email: [email protected] to make digitalor hard copies of part or all of this work forpersonal or classroom use isgranted without fee providedthat copies are notmade or distributed for profitor direct commercialadvantage and that copies show this notice on the first page or initial screen of a display alongwith the full citation. Copyrights for components of this work owned by others than ACM must behonored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers,to redistribute to lists, or to use any component of this work in other works requires prior specificpermission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 1515Broadway, New York, NY 10036 USA, fax: +1 (212) 869-0481, or [email protected] 2004 ACM 1533-5399/04/0200-0060 $5.00ACM Transactions on Internet Technology, Vol. 4, No. 1, February 2004, Pages 60–82.Fine-Grained Control of Security Capabilities•61as well as en/de-cryption, capabilities. In the course of performing routine ev-eryday tasks, users take advantage of secure applications, such as email, filetransfer, remote log-in and web browsing.Now suppose that a trusted user (Alice) does something that warrants im-mediate revocation of her security privileges. For example, Alice might be fired,or she may suspect that her private key has been compromised. Ideally, imme-diately following revocation, the key holder, either Alice herself or an attacker,should be unable to perform any security operations or use any secure applica-tions. Specifically, this might mean:—The key holder cannot read any secure email. This includes encrypted emailthat already resides on Alice’s email server (orlocal host) and possible futureemail erroneously encrypted for Alice. Although encrypted email may bedelivered to Alice’s email server, the key holder should be unable to decryptit.—The key holder cannot generate valid digital signatures on any further mes-sages. However, signatures generated by Alice prior to revocation may needto remain valid.—The key holder cannot authenticate itself to corporate servers (and otherusers) as a legitimate user.Throughout the paper, we use email as an example application. While it isa popular mechanism for general-purpose communication, our rationale alsoapplies to other secure means of information exchange.To provide immediate revocation it is natural to first consider traditionalrevocation techniques. Many revocation methods have been proposed; they canbe roughly classified into two prominent types: 1) explicit revocation structuressuch as Certificate Revocation Lists (CRLs) and variations on the theme, and2) real time revocation checking such as the Online Certificate Status Protocol(OCSP) [Myers etal. 1999] andits variants.In bothcases,some trustedentitiesare ultimately in charge of validating user certificates. However, the aboverequirements for immediate revocation are impossible to satisfy with existingtechniques. This is primarily because they do not provide fine-grained enoughcontrol over users’ security capabilities. Supporting immediate revocationwithexistingrevocation techniqueswouldresult inheavyperformance costand verypoor scalability, as discussed in Section 8.As pointed out in McDaniel and Rubin [2000], since each revocation tech-nique exhibits a unique set of pros and cons, the criteria for choosing the besttechnique should be based on the specifics of the target application environ-ment. Fast revocation and fine-grained control over users’ security capabilitiesare the motivating factors for our work. However, the need for these features isclearlynotuniversalsincemanycomputingenvironments(e.g.,atypicaluniver-sity campus) arerelatively “relaxed” and do not warrantemploying fast revoca-tion techniques. However, there are plenty of government, corporate and mili-tarysettings wherefast revocationandfine-grained controlare veryimportant.Organization. This paper is organized as follows. The next section providesan overview of our work. The technical details of the architecture are presentedACM Transactions on Internet Technology, Vol. 4, No. 1, February 2004.62•D. Boneh et al.in Section 3 and Section 4, respectively. Then, Section 5 shows four exten-sions. Sections 6 and 7 describe the implementation and performance results,respectively. A comparison with current revocation techniques is presentedSection 8, followed by the overview of