Electrical and Computer Engineering, Carnegie Mellon University

Research

Research Statement

Research Focus

Broadly, my research focuses on how to incentivize trustworthy behavior on the Web. In its infancy, the Internet was a community of a few hundred that made mutual trust a fundamental part of the infrastructure. As engineer and entrpreneur Danny Hillman said of the early Internet, “We didn’t all know each other, but we all kind of trusted each other, and that basic feeling of trust permeated the whole network. . . and in fact, it wasn’t just the people on the network, but it was actually kind of built into the protocols of the Internet itself.”

Unfortunately, as the Web has grown from hundreds to billions of users, this once-ubiquitous sense of mutual trust has vanished. The Web has become increasingly intertwined with our lives, and malicious, untrustworthy behavior aimed at accessing our sensitive financial and identifying information has become commonplace. Even so, the incentives for restoring a sense of trust within the Web community have been woefully misaligned: it is difficult, costly, and error-prone to keep trusted entities accountable and to deploy strong security mechanisms in an Web that was implicitly built on a foundation of trust.

With the goal of rebuilding trust in today’s Web, my past research has addressed the problem of authentication, that is, verifying that an entity or resource has a certain identity or attribute suitable for a particular purpose. The process of authentication is fundamental to making trust decisions: as a real-world analogy, a customer may inspect a store’s facilities or goods to decide whether the store is a trustworthy seller.

My work has specifically focused on public key infrastructures (PKIs), which securely associate public keys used in cryptography with information such as a website or organization name. Without PKIs, Web users may send encrypted communication to the wrong server, completely nullifying the benefits that encryption provides. Therefore, the problem of authentication using PKIs is fundamental to enabling strong, cryptographic security guarantees for end users of today’s Web.

Addressing this problem requires tackling not only deep technical challenges, but also societal and economic hurdles. Improving existing PKIs requires changing or displacing major players in the Web community. Therefore, my work has also focused on studying the incentives at play among these players and how to realign them in order to bring about much-needed change in today’s PKIs.

Below, I will describe two directions that I have taken in my previous and ongoing research, and how this work has contributed to making my vision of an incentivized, trustworthy future Web a reality.

Improving the Security Guarantees of PKIs

In today’s Web, to serve webpages over an encrypted connection (in particular, over HTTPS) and to identify the webpage to clients, a site owner needs to authenticate a public key associated with the site’s domain name. The owner does this by contacting a certificate authority (CA), a trusted entity that verifies the owner’s control of the site along with the desired public key, and issues a digitally signed public key certificate attesting to this verification. A client’s browser or operating system knows and trusts a core set of public keys belonging to specially designated CAs, thus enabling a certificate to serve as a type of digital identity document for the site. Unfortunately, CAs can and do fail to verify a site’s owner and public key with due diligence. This oversight can render the site unavailable, or worse, vulnerable to impersonation attacks in which an attacker masquerades as the real site, collecting sensitive information sent to the site, such as credit card information or login credentials.

My research in this area began with the PoliCert project [11], which aimed to improve upon existing solutions to this longstanding weakness in the Web PKI by giving website operators more control over the certificate issuance and verification processes. Specifically, PoliCert extended previous work [2, 3], which proposed the use of public append-only logs to publicize CA behavior and policies embedded in certificates to list criteria such as a site’s designated, trusted CAs.

In PoliCert, we observed that (1) domains have a single stable policy but may have multiple, periodically renewed certificates, and thus policies should be decoupled from certificates, (2) policies could be extended to govern how users verified certificates as well as how CAs issued certificates, and (3) policies could be enforced hierarchically, allowing sites to protect not only themselves, but also subordinate sites, even if those sites had not yet deployed PoliCert. PoliCert achieved the same level of security as previous work, requiring an adversary to control multiple CAs at once to impersonate a site. At the same time, our implementation of PoliCert imposed a latency overhead of only a few milliseconds, a delay imperceptible by end users.

As I investigated how PoliCert’s insights could be incorporated into existing PKIs, I also began to explore how its insights could shape future PKIs in ecosystems that look radically different from today’s Web. This direction led to the SAINT project [6], which proposed a PKI for authentication in the SCION future Internet architecture [14]. SCION partitions the Internet into groups called isolation domains made up of networks, or autonomous systems (ASes) in networking parlance, in order to limit the effects of misconfigured or malicious routing messages. Each isolation domain is administered by a core set of ASes that connect to core ASes in other isolation domains via traffic peering agreements.

Building SAINT on this fundamentally partitioned design, we adopted a federated model of trust in which the core of each isolated domain took on trusted CA-like roles, and each core certified the cores of other isolation domains to form a “web of trust” enabling global authentication. My main insight in SAINT was that we could federate trust for authentication by building on inter-domain peering relationships, thus leveraging existing business agreements to model mutual trust among domains. I then designed an authentication protocol that allowed users to authenticate sites in trusted isolation domains, even when connected to the Internet through an untrusted isolation domain, a property I called global authentication. I highlighted the security of SAINT by formally defining and proving this and other properties, including a guarantee that an adversary controlling a CA could only impersonate sites in that CA’s isolation domain.

As I worked on SAINT, I considered how the roles of the players in the Web PKI might change with core network protocols. I noted that security mechanisms undergoing active deployment, such as DNSSEC in the Domain Name System, were “conscripting” entities into roles where they had to issue high-value certificates, though at a lower volume than that of traditional CAs. Supervising a bachelor’s thesis project called CASTLE [7], I took a multi-pronged approach to securing certificate issuance for these new CAs.

CASTLE used Flicker [9], which leverages trusted hardware in commodity CPUs and low-level software to isolate the security-sensitive certificate issuance process from a malicious or buggy operating system. Our certificate signing machine also had no network connection and only a webcam-based QR code scanner as an input interface, limiting malicious input to the machine. The issuance protocol itself relied on multi-factor authentication and threshold signature schemes. I analyzed the security of CASTLE and showed that even an adversary who has compromised the signing machine’s operating system must gain access to a threshold number of administrator credentials and trusted devices to issue an unauthorized certificate. In comparing CASTLE to existing open-source CA software, we found that CASTLE’s code base was close to 30% smaller, with CASTLE’s trusted code base being more than 90% smaller than competing systems.

During my work on SAINT, I became aware of the fact that despite ever stronger security guarantees in PKIs, most people do not have a sense of what a good PKI should look like. In part this shortcoming is due to the fact that though the PKI problem has been recognized almost since the advent of public-key cryptography in the late 1970s, we still lack a systematic, rigorous framework for analyzing PKIs. Despite a large body of research in the field of PKI, the security community has not converged on a formal definition of a PKI or a canonical set of properties by which one should be evaluated. While my model in SAINT and several other works have begun to lay this framework, much work remains to be done in addressing this problem. In my plans for future research, I will discuss specific directions I intend to pursue in this area.

Incentives and Deployment for PKIs

In working on PoliCert, I addressed the question of what it meant to give website operators more control over their certificates and why this rebalancing of power was necessary. In a study of the Web PKI ecosystem, I observed that while CAs had a great deal of control in the Web PKI, they often suffered little to no consequences for misbehaving, resulting in a lack of incentives for CAs to behave properly and hold themselves accountable. I thus proposed the concept of certificates as insurance [4], arguing that backing certificates with insurance-like financial commitments would properly realign incentives in the Web PKI.

While studying authentication metrics for the SAINT project, I discovered that the idea of including insurance with certificates had been proposed in the late 1990s [10], though as an example of a well-designed, principled metric for authentication rather than as an accountability mechanism for CAs. I realized that with the surging popularity of cryptocurrencies and smart contracts, such a system was within reach at last.

I brought this idea to fruition in the IKP project [5], which provided incentives for (1) CAs to correctly issue certificates, and (2) all members of the Web PKI to report unauthorized or suspicious certificates. Building on the policy design of PoliCert, I designed a service where site owners could register certificate policies governing the issuance of their certificates, and extended this design to allow CAs to issue reaction policies, which specified actions that would be taken if the issuing CA violated the certificate policy of one of its customers. These reaction policies also specified payouts for anyone who found and reported a certificate that did not comply with its corresponding site.

By modeling and analyzing the payouts in this system as a game, I found a simple set of constraints that ensured strong incentives. Specifically, (1) any CA in IKP who correctly issued certificates would financially profit, (2) no CA that misissued a certificate could financially profit, even when colluding with site owners or those reporting the misissued certificate, and (3) anyone who reported a misissued certificate would financially profit. Moreover, IKP was designed to be able to verify incentive constraints, check reported certificates, and execute reaction policies automatically, meaning that the time between reporting a misissued certificate and sending payouts was only a matter of seconds.

One drawback in my design of IKP was that it required a central authority to handle policy registration, certificate checks, and payout execution. To overcome this hurdle, I built IKP on Ethereum [12], a cryptocurrency that supports smart contracts, or accounts whose behavior is controlled by code stored on the decentralized ledger of transactions [12]. This instantiation of IKP provided two important features: (1) the financial infrastructure necessary for handling payouts, and (2) a way of providing centralized functionality without requiring centralized trust. The use of Ethereum also allowed me to implement certificate policies and reaction policies as smart contracts, allowing a far richer set of policies that can adapt to handle future PKIs and certificate formats, and even allow insurance in multiple PKIs at once. While my Ethereum-based implementation of IKP does impose an operational cost for participants, I found that all recurring operations cost less than one US dollar, a small fraction of the certificates today, which typically cost on the order of hundreds of US dollars.

In addition to my research on incentives, the question of rebalancing control in the Web PKI led me to consider what it would take to deploy improvements to the existing PKI. In a study of deployment efforts in the Web PKI [8], I formulated a model of influences among different players in the Web. I used this model to conclude that focusing initial deployment efforts at browser vendors and CAs were the most viable de- ployment strategies for PKI improvements. I also proposed a lightweight mechanism based on probabilistic data structures to allow sites to securely signal that they had deployed a PKI enhancement, ensuring that attackers could not attempt to impersonate the site using the lower-security, existing PKI.

As I continue to explore this topic, I have observed that before considering how to securely communicate the deployment status of a PKI enhancement, site owners must be able to signal that they are using the PKI in the first place, that is, that they serve their website over HTTPS. Existing mechanisms for enabling this signaling either do not protect all sites, require one HTTPS connection to be made first, or take significantly longer to establish a secure connection, tarnishing the user browsing experience. I am currently investigating approaches to this problem, as well as the implications of a suitable solution for deployment.

Future Directions

Recent years have seen a renewed interest in PKI research and innovations that have protected users against the effects of certificate misissuances. Despite this progress, there is still much work to be done in improving and understanding PKIs and incentives on the Web. To work towards these goals, I plan to investigate several fundamental directions that will bring us closer to a more trustworthy Web.

First, I plan to study and contextualize security failures in the Web PKI. While Internet-wide measurement data [1] has provided us with a near-complete view of certificates in the Web’s PKI, we have a limited understanding of these certificates: we do not know which certificates were misissued, nor do we have suitable heuristics for identifying such certificates. We also have an incomplete picture of trends and security incidents in new yet widely used systems such as Let’s Encrypt (which provides a certificate issuance protocol and free certificates) and Certificate Transparency (CT). I plan to assemble a team to collect data on historical security incidents in the Web PKI to add an intuitive, insightful view of security in the Web PKI to existing certificate data. I anticipate that these insights will highlight common pitfalls in designing PKIs and help inform both specialists and laypeople about the perils of PKI failures.

While I continue to gain new insights into the Web PKI using existing certificate data, I also plan to lead a long-term effort in systematizing and categorizing PKIs. The recent surge in work in the PKI field has led to a wealth of PKI proposals that remains underexplored, and there is a large body of past PKIs that were never widely deployed. These proposals come not only from academia, but also from industry and independent members of the Web community. In order to better understand the intended use cases and the claimed security guarantees of these proposed PKIs, I first plan to extend and formalize existing evaluations of PKIs and their properties [13], which are intuitive yet incomplete and imprecise. I then plan to use this formalization as the basis of a framework we can apply to existing and future PKIs.

I am also passionate about understanding the broader human aspect of PKI challenges. PKIs can be used not only in the Web, but also in enterprise environments and in private, peer-to-peer communication, yet many of the participants in these contexts have a limited understanding of PKIs and how to use them. I therefore plan to extend my work in studying PKI deployability by conducting user studies among Web users, website operators, and if possible, CA administrators. I will also study efforts by systems such as Let’s Encrypt, which in part have seen a surge in usage due to partnerships with major Web hosting providers. While previous usability studies of the Web PKI have focused on the graphical interface and indicators presented to users, I plan to focus on broader hurdles to deploying HTTPS and recently proposed improvements to the Web PKI with the goal of designing more successful deployment strategies.

I then plan to combine my insights into public perceptions of PKI deployment challenges with an extension of my incentive model from IKP in order to formulate a stronger, incentive-based model of PKI deployment. I especially hope to apply this model to the problem of incentivizing the deployment of public log servers in CT, who are responsible for publicizing potentially unauthorized certificates issued by CAs. Currently, these log servers are not compensated for operating, even though they play a critical role in ensuring greater CA accountability; in fact, many of these logs are operated by the CAs themselves! By providing a sound incentivization model for the deployment and operation of public certificate logs, I aim to bring us closer to a Web in which all participants are incentivized to behave in a more trustworthy manner.

Of course, the problem of designing and building trustworthiness back into the Web reaches far beyond PKI. I am confident that my research will bring me into fruitful collaborations and intellectual dialogs with key players from academia and industry, with thinkers from a range of disciplines, both within and outside of my areas of expertise. I envision that as I continue to make advances towards a more secure foundation of incentivized, trustworthy PKIs, I will contribute towards a larger, concerted effort to bring trustworthiness back into the Web.

References

[1] Z. Durumeric, D. Adrian, A. Mirian, M. Bailey, and J. A. Halderman. “A search engine backed by Internet-wide scanning.” In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS), 2015.

[2] T. H.-J. Kim, L.-S. Huang, A. Perrig, C. Jackson, and V. Gligor. “Accountable Key Infrastructure (AKI): A proposal for a public-key validation infrastructure.” In Proceedings of the International World Wide Web Conference (WWW), May 2013.

[3] B. Laurie, A. Langley, and E. Kasper. “Certificate transparency.” RFC 6962, June 2013.

[4] S. Matsumoto and R. M. Reischuk. “Certificates-as-an-Insurance: Incentivizing accountability in SSL/TLS.” In Proceedings of the NDSS Workshop on Security of Emerging Network Technologies (SENT), February 2015.

[5] S. Matsumoto and R. M. Reischuk. “IKP: Turning a PKI around with decentralized automated incentives.” In Proceedings of the IEEE Symposium on Security and Privacy (S&P), May 2017.

[6] S. Matsumoto, R. M. Reischuk, P. Szalachowski, T. H.-J. Kim, and A. Perrig. “Authentication challenges in a global environment.” ACM Transactions on Privacy and Security (TOPS), 20(1), January 2017.

[7] S. Matsumoto, S. Steffen, and A. Perrig. “CASTLE: CA signing in a touchless environment.” In Proceedings of the 32nd Annual Computer Security Applications Conference (ACSAC), December 2016.

[8] S. Matsumoto, P. Szalachowski, and A. Perrig. “Deployment challenges in log-based PKI enhancements.” In Proceedings of the European Workshop on System Security (EuroSec), April 2015.

[9] J. M. Mc Cune, B. Parno, A. Perrig, M. K. Reiter, and H. Isozaki. “Flicker: An execution infrastructure for TCB minimization.” In Proceedings of the ACM European Conference in Computer Systems (EuroSys), Apr. 2008.

[10] M. K. Reiter and S. G. Stubblebine. Toward acceptable metrics of authentication. In Proceedings of the IEEE Symposium on Security and Privacy (S&P), 1997.

[11] P. Szalachowski, S. Matsumoto, and A. Perrig. “PoliCert: Secure and flexible TLS certificate management.” In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS), November 2014.

[12] G. Wood. “Ethereum: A secure decentralised generalised transaction ledger.” White Paper, 2015.

[13] J. Yu and M. Ryan. “Evaluating Web PKIs.” In I. Mistrik, R. Bahsoon, N. Ali, M. Heisel, and B. Maxim, editors, Software Architecture for Big Data and the Cloud, chapter 7. Elsevier, 1 edition, June 2017.

[14] X. Zhang, H.-C. Hsiao, G. Hasker, H. Chan, A. Perrig, and D. G. Andersen. “SCION: Scalability, control, and isolation on next-generation networks.” In Proceedings of the IEEE Symposium on Security and Privacy (S&P), May 2011.

Tag Cloud