Tamper-resistant whole program partitioning

ABSTRACT

Due to limited available memory (of the order of Kilobytes) on embedded devices (such as smart cards), we undertake an approach of partitioning the whole program when it does not fit in the memory. The program partitions are downloaded from the server on demand into the embedded device just before execution. We devise a method of partitioning the code and data of the program such that no information regarding the control flow behavior of the program is leaked out. This property is called tamper resistance and it is very important for secure embedded devices such as smart cards which could hold sensitive information and/or carry out critical computation such as financial transactions. A preliminary solution to this problem was proposed in our earlier work [1]. This work proposes a new and more comprehensive solution to the problem. First, we propose a new policy which is based on keeping nothing in terms of partitions on the smart card. This policy is unlike the one in previous work which mandated keeping partitions in memory to which control flow was guaranteed to return. Based on this new policy, a new partitioning algorithm is proposed for minimal safe partitions which reduces their memory requirements over previous work. The drawback of this new policy is however lower execution speed due to frequent communication encountered. In order to not significantly degrade performance, we propose caching frequently executed functions on the smart card without violation of tamper resistance. A framework is designed to determine the set of functions to be cached in conjunction with specific minimal safe partitions. Further reduction in memory requirements is achieved due to the data partitioning.The decrease in memory footprint over the previous method is 27% for code memory and 32.4% for data memory on average. The speed-up over the old method is quite significant when applied to whole programs in large benchmarks (500 times on average). The conclusion is that previous method [1] is not suitable as a whole program partitioning strategy whereas the new proposed method is a viable solution.

REFERENCES

• 1: Tao Zhang , Santosh Pande , Andre dos Santos , Franz Josef Bruecklmayr, Leakage-proof program partitioning, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581651]
• 2: Jason Tey, Study on Multi-Application Smart Card, http://web.singnet.com.sg/~jasontey/project.htm
• 3: Paul C. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.104-113, August 18-22, 1996
• 4: 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
• 5: Stanford SUIF Compiler Infrastructure, The SUIF 2 compiler documentation set, Stanford University, Sep.2000. http://suif.stanford.edu/suif/index.html.
• 6: Mach-SUIF Backend Compiler, The Machine-SUIF 2.1 compiler documentation set. Harvard University, Sep. 2000, http://ececs.harvard.edu/hube/research/machsuif.html.
• 7: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 8: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States
• 9: http://wwwww.arm.com/app.nsf/html/security?OpenDocument&style=ARM_Powered_Products
• 10: M.R. Guthaus et al. "MiBench: A Free, Commercially representative Embedded Benchmark Suite." In the Fourth IEEE Workshop on Workload Characterization, Dec. 2001.
• 11: Helena Handschuh , Pascal Paillier , Jacques Stern, Probing Attacks on Tamper-Resistant Devices, Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems, p.303-315, August 12-13, 1999
• 12: O. Kommerling and M. G. Kuhn, Design principles for tamper-resistant smartcard processors, Proceedings of USENIX Workshop on Smartcard Technology, 1999, pp. 9--20.
• 13: Ross Anderson, Markus Kuhn, Tamper Resistance - a Cautionary Note, proceedings of the Second Usenix Workshop on Electronic Commerce, pp. 1--11, November 1996.
• 14: T. S. Messerges, E. A. Dabbish, and R. H. Sloan, Investigations of power analysis attacks on smartcards, Proceedings of USENIX Workshop on Smartcard Technology, 1999, pp. 151--161.
• 15: D. Boneh, R. A. DeMillo, and R. J. Lipton, On the importance of checking cryptographic protocols for faults, Proceedings of EUROCRYPT '97 (W. Fumy, ed.), Lecture Notes in Computer Science, vol. 1233, Springer-Verlag, 1997, pp. 37--51.
• 16: Christian Collberg, Clark Thomborson, and Douglas Low. A taxonomy of obfuscating transformations. Technical Report 148, Department of Computer Science, University of Auckland, July 1997.
• 17: David Aucsmith, Tamper Resistant Software: An Implementation, Proceedings of the First International Workshop on Information Hiding, p.317-333, May 30-June 01, 1996

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Smartcards

General Terms:
Design, Performance, Security

Keywords:
mobile code, program partitioning, ramper resistance, smart card