Controlled physical random functions and applications

ABSTRACT

The cryptographic protocols that we use in everyday life rely on the secure storage of keys in consumer devices. Protecting these keys from invasive attackers, who open a device to steal its key, is a challenging problem. We propose controlled physical random functions (CPUFs) as an alternative to storing keys and describe the core protocols that are needed to use CPUFs. A physical random functions (PUF) is a physical system with an input and output. The functional relationship between input and output looks like that of a random function. The particular relationship is unique to a specific instance of a PUF, hence, one needs access to a particular PUF instance to evaluate the function it embodies. The cryptographic applications of a PUF are quite limited unless the PUF is combined with an algorithm that limits the ways in which the PUF can be evaluated; this is a CPUF. A major difficulty in using CPUFs is that you can only know a small set of outputs of the PUF—the unknown outputs being unrelated to the known ones. We present protocols that get around this difficulty and allow a chain of trust to be established between the CPUF manufacturer and a party that wishes to interact securely with the PUF device. We also present some elementary applications, such as certified execution.

REFERENCES

• 1: Alves, T. and Felton, D. 2004. Trustzone: Integrated hardware and software security. ARM. White paper.
• 2: Ross Anderson , Markus Kuhn, Tamper resistance: a cautionary note, Proceedings of the 2nd conference on Proceedings of the Second USENIX Workshop on Electronic Commerce, p.1-1, November 18-21, 1996, Oakland, California
• 3: Ross J. Anderson , Markus G. Kuhn, Low Cost Attacks on Tamper Resistant Devices, Proceedings of the 5th International Workshop on Security Protocols, p.125-136, April 07-09, 1997
• 4: Ross J. Anderson, Security Engineering: A Guide to Building Dependable Distributed Systems, John Wiley & Sons, Inc., New York, NY, 2001
• 5: Carroll, A., Juarez, M., Polk, J., and Leininger, T. 2002. Microsoft “palladium”: A business overview. In Microsoft Content Security Business Unit.
• 6: Chinnery, D. and Keutzer, K. 2002. Closing the Gap Between ASIC & Custom. Kluwer Academic Publi., Boston, MA.
• 7: Distributed.Net. http://distributed.net/.
• 8: Gassend, B. 2003. Physical Random Functions. M.S. thesis, Massachusetts Institute of Technology.
• 9: Blaise Gassend , Dwaine Clarke , Marten van Dijk , Srinivas Devadas, Controlled Physical Random Functions, Proceedings of the 18th Annual Computer Security Applications Conference, p.149, December 09-13, 2002
• 10: Blaise Gassend , Dwaine Clarke , Marten van Dijk , Srinivas Devadas, Silicon physical random functions, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586132]
• 11: Blaise Gassend , G. Edward Suh , Dwaine Clarke , Marten van Dijk , Srinivas Devadas, Caches and Hash Trees for Efficient Memory Integrity Verification, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.295, February 08-12, 2003
• 12: Blaise Gassend , Daihyun Lim , Dwaine Clarke , Marten van Dijk , Srinivas Devadas, Identification and authentication of integrated circuits: Research Articles, Concurrency and Computation: Practice & Experience, v.16 n.11, p.1077-1098, September 2004 [doi>10.1002/cpe.v16:11]
• 13: Peter Gutmann, Secure deletion of data from magnetic and solid-state memory, Proceedings of the 6th conference on USENIX Security Symposium, Focusing on Applications of Cryptography, p.8-8, July 22-25, 1996, San Jose, California
• 14: Daniel Jackson, Automating first-order relational logic, Proceedings of the 8th ACM SIGSOFT international symposium on Foundations of software engineering: twenty-first century applications, p.130-139, November 06-10, 2000, San Diego, California, United States
• 15: Daniel Jackson, Alloy: a lightweight object modelling notation, ACM Transactions on Software Engineering and Methodology (TOSEM), v.11 n.2, p.256-290, April 2002 [doi>10.1145/505145.505149]
• 16: Paul C. Kocher , Joshua Jaffe , Benjamin Jun, Differential Power Analysis, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.388-397, August 15-19, 1999
• 17: Lee, J.-W., Lim, D., Gassend, B., Suh, G. E., van Dijk, M., and Devadas, S. 2004. A technique to build a secret key in integrated circuits with identification and authentication applications. In Proceedings of the IEEE VLSI Circuits Symposium. IEEE, New York.
• 18: David J. Lie , Mark Horowitz, Architectural support for copy and tamper-resistant software, Stanford University, Stanford, CA, 2004
• 19: David Lie Chandramohan Thekkath , Mark Mitchell , Patrick Lincoln , Dan Boneh , John Mitchell , Mark Horowitz, Architectural support for copy and tamper resistant software, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.168-177, November 2000, Cambridge, Massachusetts, United States
• 20: Lim, D. 2004. Extracting Secret Keys from Integrated Circuits. M.S. thesis, Massachusetts Institute of Technology.
• 21: Lim, D., Lee, J. W., Gassend, B., Suh, G. E., van Dijk, M., and Devadas, S. 2005. Extracting secret keys from integrated circuits. IEEE Trans. VLSI Syst. 13, 10, 1200--1205.
• 22: Microsoft. Next-Generation Secure Computing Base. http://www.microsoft.com/resources/ngscb/defaul.mspx.
• 23: Pappu Srinivasa Ravikanth , Stephen A. Benton, Physical one-way functions, Massachusetts Institute of Technology, 2001
• 24: Pappu Srinivasa Ravikanth , Stephen A. Benton, Physical one-way functions, Massachusetts Institute of Technology, 2001
• 25: SETI@Home.
• 26: Skoric, B., Tuyls, P., and Ophey, W. 2005. Robust key extraction from physical unclonable functions. In Proceedings of the Applied Cryptography and Network Security Conference 2005, J. Ionnidis, A. Keromytis, and M. Yung, Eds. Lecture Notes in Computer Science, vol. 3531. Springer-Verlag. New York. 407--422.
• 27: Sean W. Smith , Steve Weingart, Building a high-performance, programmable secure coprocessor, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.9, p.831-860, April 23, 1999
• 28: G. Edward Suh , Dwaine Clarke , Blaise Gassend , Marten van Dijk , Srinivas Devadas, AEGIS: architecture for tamper-evident and tamper-resistant processing, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782838]
• 29: G. Edward Suh , Charles W. O'Donnell , Ishan Sachdev , Srinivas Devadas, Design and Implementation of the AEGIS Single-Chip Secure Processor Using Physical Random Functions, Proceedings of the 32nd annual international symposium on Computer Architecture, p.25-36, June 04-08, 2005
• 30: Torlak, E., van Dijk, M., Gassend, B., Jackson, D., and Devadas, S. 2006. Knowledge flow analysis for security protocols. http://arxiv.org/abs/cs/0605109.
• 31: Trusted Computing Group. 2004. TCG Specification Architecture Overview Revision 1.2. http://www.trustedcomputinggroup.com/home.
• 32: Tuyls, P., Skoric, B., Stallinga, S., Akkermans, A., and Ophey, W. 2005. Information theoretical security analysis of physical unclonable functions. In Proceedings Conf on Financial Cryptography and Data Security 2005, A. Patrick and M. Yung, Eds. Lecture Notes in Computer Science, vol. 3570. Springer-Verlag, New York. 141--155.
• 33: Neil H. E. Weste , Kamran Eshraghian, Principles of CMOS VLSI design: a systems perspective, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 34: Yee, B. S. 1994. Using secure coprocessors. Ph.D. thesis, Carnegie Mellon University.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Security, Theory

Keywords:
Certified execution, physical random function, physical security, physical unclonable function, trusted computing