Energy evaluation of software implementations of block ciphers under memory constraints

ABSTRACT

Software implementations of modern block ciphers often require large lookup tables along with code size increasing optimizations like loop unrolling to reach peak performance on general-purpose processors. Therefore, block ciphers are difficult to implement efficiently on embedded devices like cell phones or sensor nodes where run-time memory and program ROM are scarce resources. In this paper we analyze and compare the performance, energy consumption, run-time memory requirements, and code size of the five block ciphers RC6, Rijndael, Serpent, Twofish, and XTEA on the StrongARM SA-1100 processor. Most previous evaluations of block ciphers considered performance as the sole metric of interest and did not care about memory requirements or code size. In contrast to previous work, our study of the performance and energy characteristics of block ciphers has been conducted with "lightweight" implementations which restrict the size of lookup tables to 1 kB and also impose constraints on the code size. We found that Rijndael and RC6 can be well optimized for high performance and energy efficiency, while at the same time meeting the demand for low memory (RAM and ROM) footprint. In addition, we discuss the impact of key expansion and modes of operation on the overall performance and energy consumption of each block cipher. Our simulation results show that RC6 is the most energy-efficient block cipher under memory constraints and thus the best choice for resource-restricted devices.

REFERENCES

• 1: R. J. Anderson, E. Biham, and L. R. Knudsen. Serpent: A proposal for the Advanced Encryption Standard. Technical report, University of Cambridge, 1998.
• 2: ARM Limited. ARM Architecture Reference Manual. ARM Doc No. DDI-0100, Issue H, 2003.
• 3: Guido Bertoni , Luca Breveglieri , Pasqualina Fragneto , Marco Macchetti , Stefano Marchesin, Efficient Software Implementation of AES on 32-Bit Platforms, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.159-171, August 13-15, 2002
• 4: Eli Biham, A Fast New DES Implementation in Software, Proceedings of the 4th International Workshop on Fast Software Encryption, p.260-272, January 20-22, 1997
• 5: Joan Daemen , Vincent Rijmen, The Design of Rijndael, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 6: B. R. Gladman. AES second round implementation experience. Available online at http://fp.gladman.plus.com/cryptography_technology/aesr2/index.htm, 2000.
• 7: Creighton T. R. Hager , Scott F. Midkiff , Jung-Min Park , Thomas L. Martin, Performance and Energy Efficiency of Block Ciphers in Personal Digital Assistants, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications, p.127-136, March 08-12, 2005 [doi>10.1109/PERCOM.2005.29]
• 8: Tim Kindberg , Armando Fox, System Software for Ubiquitous Computing, IEEE Pervasive Computing, v.1 n.1, p.70-81, January 2002 [doi>10.1109/MPRV.2002.993146]
• 9: Yee Wei Law , Jeroen Doumen , Pieter Hartel, Survey and benchmark of block ciphers for wireless sensor networks, ACM Transactions on Sensor Networks (TOSN), v.2 n.1, p.65-93, February 2006 [doi>10.1145/1138127.1138130]
• 10: R. M. Needham and D. J. Wheeler. Tea extensions. Technical report, University of Cambridge, 1997.
• 11: Nachiketh R. Potlapally , Srivaths Ravi , Anand Raghunathan , Niraj K. Jha, Analyzing the energy consumption of security protocols, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871518]
• 12: D. Remondoa and I. G. Niemegeers. Ad-hoc networking in future wireless communications. Computer Communications, 26(1):36--40, 2003.
• 13: R. L. Rivest et al. The RC6#8482; block cipher. Technical report, RSA Laboratories, 1998.
• 14: B. Schneier et al. Twofish: A 128-bit block cipher. Technical report, Counterpane Systems, 1998.
• 15: Amit Sinha , Anantha P. Chandrakasan, JouleTrack: a web based tool for software energy profiling, Proceedings of the 38th conference on Design automation, p.220-225, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378467]
• 16: Security: for ubiquitous computing, John Wiley & Sons, Inc., New York, NY, 2002
• 17: S. Tillich, J. Großschädl, and A. Szekely. An instruction set extension for fast and memory-efficient AES implementation. In Communications and Multimedia Security --- CMS 2005, LNCS 3677 pp. 11--21. Springer Verlag, 2005.
• 18: University of Michigan. Sim-Panalyzer 2.0. Available for download at http://www.eecs.umich.edu/~panalyzer.
• 19: M. Weiser. The computer for the 21st century. Scientific American, 265(3):94--104, 1991.

INDEX TERMS

Keywords:
code size reduction, energy optimization, lightweight cryptography, memory footprint, symmetric cipher