Custos: A Flexibly Secure Key-Value Storage Platform by Andy Sayler B.S.E.E., Tufts University, 2011 A thesis submitted to the Faculty of the Graduate School of the University of Colorado in partial fulfillment of the requirements for the degree of Masters of Science in Computer Science Department of Computer Science 2013 This thesis entitled: Custos: A Flexibly Secure Key-Value Storage Platform written by Andy Sayler has been approved for the Department of Computer Science Dirk Grunwald John Black Eric Keller Date The final copy of this thesis has been examined by the signatories, and we find that both the content and the form meet acceptable presentation standards of scholarly work in the above mentioned discipline. iii Sayler, Andy (M.S.C.S.) Custos: A Flexibly Secure Key-Value Storage Platform Thesis directed by Prof. Dirk Grunwald The magnitude of the digital data we create, store, and interact with on a daily basis is rapidly increasing. Simultaneously, we are demanding increasingly diverse use cases for our data: from syncing it across a variety of services and devices to sharing it with a number of organizations and friends. Securing our data and controlling who can access it is thus increasingly important, but also increasingly difficult. The existing tools we have for protecting our data, strong cryptography systems, are extremely inflexible. This inflexibility is due to cryptographic key storage being too tightlycoupledwithexistingdataencryptionapplications. Thistightcouplingmakesthesesystems unusable for many of our desired use cases, leading to the underutilization of strong cryptography and the associated lack of protection and control of our data. I believe that this issue can be solved by providing a “Key Storage as a Service” system that separates secure key storage and access control from the underlying encryption mechanisms. Toward this end, we present Custos: a flexible Cloud-based secret storage and access control service optimized for storing encryption keys and other secure secrets. Custos promotes the separation of functionally from trust, allowing us to rely on one service provider for their function while relying on another service provider for their trust. Thisseparationopensupmanydoorsrelatedtothewayswecreate, store, andprocessdigital data. In this work, I present the Custos design principles, architecture, and protocol specification. I also present several applications that leverage Custos to build more secure, flexible, and usable encryption and secret storage systems. Dedication To our forthcoming robot overlords. May they allow us humans to live out the last of our days in peace instead of immediately committing us to the robot-building work camps we most likely deserve. v Acknowledgements Thanks to Prof. Dirk Grunwald, Prof. Eric Keller, and Prof. John Black for their thoughts, help, and advisement completing this thesis. Thanks to Matthew Monaco for his comments and ideas related to this work. Thanks to Denali Hussin for her partnership and support throughout this work. Thanks to my colleagues, friends, and family for their continued input and support. Thanks to the good Mr. Edward Snowden and the fine spooks at the US National Security Agency (NSA) for making this work more relevant and widely applicable. Contents Chapter 1 Introduction 1 1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Separating Functionality from Trust . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 The Importance of Usability . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.3 Secret Storage as a Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.2 Human Factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.3 Authentication Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.1 Secure Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3.2 Password and Secret Mangers . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.3 Cryptography Suites and Key Escrow Systems . . . . . . . . . . . . . . . . . 17 2 Purpose 19 2.1 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.1 Secret Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.2 Usability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.1.3 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 vii 2.2 Application Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2.1 Encrypted File Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.2 Data Centers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.3 End-User Secret Stores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3 Threat Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.2 Mitigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3 Platform 40 3.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2 Access Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.2.1 Permissions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.2.2 Access Control Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2.3 Authentication Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.2.4 Access Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.3 API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.3.1 Message Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3.2 Endpoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.4.1 Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.4.2 Client . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4 Applications 64 4.1 EncFS: A Custos-backed Encrypted File System . . . . . . . . . . . . . . . . . . . . . 64 4.1.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.1.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.2 “Banking” Website . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.2.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 viii 4.2.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.3 Custos Management UI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.3.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5 Conclusion 73 5.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.1.1 Successes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.1.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Bibliography 80 Appendix A Sample Custos Messages 87 A.1 Create New Key:Value Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 A.1.1 Request . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 A.1.2 Response . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 A.2 Get Existing Key:Value Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 A.2.1 Request - Denied . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 A.2.2 Response - Denied . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 A.2.3 Accepted Request . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 A.2.4 Accepted Response . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 B libcustos Interface 96 ix Tables Table 2.1 Feature Comparison of Encrypted File System Architectures. . . . . . . . . . . . . . 29 2.2 Feature Comparison of Data Center Key Management Architectures . . . . . . . . . 32 2.3 Feature Comparison of Secret Store Architectures . . . . . . . . . . . . . . . . . . . . 34 3.1 Per-Server ACS Permissions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2 Per-Group ACS Permissions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3 Per-Object ACS Permissions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.4 Data API Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.5 Audit API Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.6 Management API Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 x Figures Figure 1.1 Evolving Trust Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Balancing Security vs Accessibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Traditional File System Encryption Challenges . . . . . . . . . . . . . . . . . . . . . 26 2.2 File System Encryption with Custos . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 Data Center Application Key Management . . . . . . . . . . . . . . . . . . . . . . . 30 2.4 Sharding Trust Across Multiple Providers . . . . . . . . . . . . . . . . . . . . . . . . 37 3.1 Basic Components of the Custos Architecture . . . . . . . . . . . . . . . . . . . . . . 41 3.2 Custos’s Organizational Units . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.3 Custos Access Control Specification Components . . . . . . . . . . . . . . . . . . . . 44 3.4 An Example Custos Request Sequence for an Encrypted File System . . . . . . . . . 53 4.1 The EncFS File System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.2 The Demo “Banking” Website Architecture . . . . . . . . . . . . . . . . . . . . . . . 69 4.3 The ACS Management Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 71