Virtual monotonic counters and count-limited objects using a TPM without a trusted OS

ABSTRACT

A trusted monotonic counter is a valuable primitive that enables a wide variety of highly scalable offline and decentralized applications that would otherwise be prone to replay attacks, including offline payment, e-wallets, virtual trusted storage, and digital rights management (DRM). In this paper, we show how one can implement a very large number of virtual monotonic counters on an untrusted machine with a Trusted Platform Module (TPM) or similar device, without relying on a trusted OS. We first present a log-based scheme that can be implemented with the current version of the TPM (1.2) and used in certain applications. We then show how the addition of a few simple features to the TPM makes it possible to implement a hash-tree-based scheme that not only offers improved performance and scalability compared to the log-based scheme, but also makes it possible to implement count-limited objects (or ``clobs'' for short) -- i.e., encrypted keys, data, and other objects that can only be used when an associated virtual monotonic counter is within a certain range. Such count-limited objects include n-time use keys, n-out-of-m data blobs, n-copy migratable objects, and other variants, which have many potential uses in digital rights management (DRM), digital cash, itinerant computing, and other application areas.

REFERENCES

• 1: S. Balfe, A. Lakhani, and K. Paterson. Securing peer-to-peer networks using trusted computing. In C. Mitchell, editor, Trusted Computing, chapter 10. IEE, 2005.
• 2: L. Bauer, K. D. Bowers, F. Pfenning, and M. K. Reiter. Consumable credentials in logic-based access control. Technical Report CMU-CYLAB-06-002, CyLab, Carnegie Mellon University, Feb. 2006.
• 3: Stefan Brands, Untraceable Off-line Cash in Wallets with Observers (Extended Abstract), Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology, p.302-318, August 22-26, 1993
• 4: Ernie Brickell , Jan Camenisch , Liqun Chen, Direct anonymous attestation, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030103]
• 5: Laurent Bussard , Refik Molva, One-Time Capabilities for Authorizations without Trust, Proceedings of the Second IEEE International Conference on Pervasive Computing and Communications (PerCom'04), p.351, March 14-17, 2004
• 6: D. Chaum. Blind signatures for untraceable payments. In Advances in Cryptology - Crypto '82 Proceedings, pages 199--203. Plenum Press, 1982.
• 7: D. Chess, B. Grosof, C. Harrison, D. Levine, C. Parris, and G. Tsudik. Itinerant agents for mobile computing. IEEE Personal Communications, 2(5):34--49, Oct. 1985.
• 8: A. Dent and G. Price. Certificate management using distributed trusted third parties. In C. Mitchell, editor, Trusted Computing, chapter 9. IEE, 2005.
• 9: E. Gallery. An overview of trusted computing technology. In C. Mitchell, editor, Trusted Computing, chapter 3. IEE, 2005.
• 10: E. Gallery and A. Tomlinson. Secure delivery of conditional access applications to mobile receivers. In C. Mitchell, editor, Trusted Computing, chapter 7. IEE, 2005.
• 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: S. Goldwasser, G. Rothblum, and Y. Kalai. One-time programs. Personal communication, June 2006.
• 13: F. Hohl. Time limited blackbox security: Protecting mobile agents from malicious hosts. Lecture Notes in Computer Science, 1419, 1998.
• 14: IBM. Linux TPM Device Driver. http://tpmdd.sourceforge.net/.
• 15: IBM. SecureBlue. http://domino.watson.ibm.com/ comm/pr.nsf/pages/news.20060410_security.html, 2006.
• 16: Intel. LaGrande Technology. http://www.intel.com/technology/security/, 2003.
• 17: H. Kim, J. Baek, B. Lee, and K. Kim. Secret computation with secrets for mobile agent using one-time proxy signature. In Proceedings of the 2001 Symposium on Cryptography and Information Security, 2001.
• 18: U. Maheshwari, R. Vingralek, and W. Shapiro. How to Build a Trusted Database System on Untrusted Storage. In Proceedings of OSDI 2000, 2000.
• 19: R. Merkle. A certified digital signature. In manuscript, 1979.
• 20: C. Mitchell, editor. Trusted Computing. The Institution of Electrical Engineers, 2005.
• 21: M. Naor and K. Nissim. Certificate revocation and certificate update. In Proceedings 7th USENIX Security Symposium (San Antonio, Texas), 1998.
• 22: L. Nguyen and R. Safavi-Naini. Dynamic k-times anonymous authentication. In Applied Cryptography and Network Security (ACNS 2005), volume 3531 of Lecture Notes in Computer Science, pages 318--333, 2005.
• 23: Siani Pearson, Trusted Computing Platforms: TCPA Technology in Context, Prentice Hall PTR, Upper Saddle River, NJ, 2002
• 24: M. Peinado, P. England, and Y. Chen. An overview of NGSCB. In C. Mitchell, editor, Trusted Computing, chapter 4. IEE, 2005.
• 25: L. F. G. Sarmenta, M. van Dijk, C. W. O'Donnell, J. Rhodes, and S. Devadas. Virtual Monotonic Counters and Count-Limited Objects using a TPM without a Trusted OS (Extended Version). MIT CSAIL Technical Report (to be published), Sept. 2006. http://publications.csail.mit.edu/.
• 26: Alan Shieh , Dan Williams , Emin Gün Sirer , Fred B. Schneider, Nexus: a new operating system for trustworthy computing, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom [doi>10.1145/1095810.1118613]
• 27: 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]
• 28: I. Teranishi, J. Furukawa, and K. Sako. k-times anonymous authentication (extended abstract). In ASIACRYPT 2004, volume 3329 of Lecture Notes in Computer Science, pages 308--322, 2004.
• 29: Trusted Computing Group. TPM v1.2 specification changes. https://www.trustedcomputinggroup.org/groups/tpm/TPM_1_2_Changes_final.pdf, 2003.
• 30: Trusted Computing Group. TCG TPM Specification version 1.2, Revisions 62--94 (Design Principles, Structures of the TPM, and Commands). https://www.trustedcomputinggroup.org/specs/TPM/, 2003-2006.
• 31: Dan Williams , Emin Gün Sirer, Optimal Parameter Selection for Efficient Memory Integrity Verification Using Merkle Hash Trees, Proceedings of the Network Computing and Applications, Third IEEE International Symposium on (NCA'04), p.383-388, August 30-September 01, 2004

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Microprocessor/microcomputer applications; Smartcards

  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Design, Security

Keywords:
certified execution, e-wallet memory integrity checking, key delegation, stored-value, trusted storage