Abstract
Digital signatures are one of the most important applications of microprocessor smart cards. The most widely used algorithms for digital signatures, RSA and ECDSA, depend on finite field engines. On 8-bit microprocessors these engines either require costly coprocessors, or the implementations become very large and very slow. Hence the need for better methods is highly visible. One alternative to RSA and ECDSA is the Merkle signature scheme which provides digital signatures using hash functions only, without relying on any number theoretic assumptions. In this paper, we present an implementation of the Merkle signature scheme on an 8-bit smart card microprocessor. Our results show that the Merkle signature scheme provides comparable timings compared to state of the art implementations of RSA and ECDSA, while maintaining a smaller code size.
Chapter PDF
Similar content being viewed by others
References
Rijndaelfurious implementation (January 2008), http://point-at-infinity.org/avraes/
Atmel. Overview of secure avr microcontrollers 8-/16-bit risc cpu (2007), http://www.atmel.com/products/SecureAVR/
Atmel. Specifications of the atmega128 microcontroller (2007), http://www.atmel.com/dyn/resources/prod_documents/doc2467.pdf
Buchmann, J., Coronado, C., Dahmen, E., Döring, M., Klintsevich, E.: CMSS - an improved merkle signature scheme. In: Barua, R., Lange, T. (eds.) INDOCRYPT 2006. LNCS, vol. 4329, pp. 349–363. Springer, Heidelberg (2006)
Buchmann, J., Dahmen, E., Klintsevich, E., Okeya, K., Vuillaume, C.: Merkle signatures with virtually unlimited signature capacity. In: Katz, J., Yung, M. (eds.) ACNS 2007. LNCS, vol. 4521, pp. 31–45. Springer, Heidelberg (2007)
Buchmann, J., Dahmen, E., Schneider, M.: Merkle tree traversal revisited (manuscript, 2008), http://www.cdc.informatik.tu-darmstadt.de/mitarbeiter/dahmen.html
Cheng, X., Li, W., Znati, T. (eds.): WASA 2006. LNCS, vol. 4138. Springer, Heidelberg (2006)
Coronado, C.: On the security and the efficiency of the merkle signature scheme. Cryptology ePrint Archive, Report 2005/192 (2005), http://eprint.iacr.org/
Dods, C., Smart, N.P., Stam, M.: Hash based digital signature schemes. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 96–115. Springer, Heidelberg (2005)
Driessen, B., Poschmann, A., Paar, C.: Comparison of Innovative Signature Algorithms for WSNs. In: Proceedings of the First ACM Conference on Wireless Network Security (to appear)
ePractice.eu. Belgian electronic ID card officially launched (April 2003), http://www.epractice.eu/document/2139
Digital signature standard (DSS). FIPS PUB 186-2 (2007), http://csrc.nist.gov/publications/fips/
Ganesan, P., Venugopalan, R., Peddabachagari, P., Dean, A., Mueller, F., Sichitiu, M.: Analyzing and modeling encryption overhead for sensor network nodes. In: WSNA 2003: Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, pp. 151–159. ACM Press, New York (2003)
Gura, N., Patel, A., Wander, A., Eberle, H., Shantz, S.C.: Comparing elliptic curve cryptography and rsa on 8-bit cpus. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 119–132. Springer, Heidelberg (2004)
Labor, D.: Crypto-avr-lib (January 2008), http://www.das-labor.org/wiki/Crypto-avr-lib
Lenstra, A.K.: Key lengths. Contribution to The Handbook of Information Security (2004), http://cm.bell-labs.com/who/akl/key_lengths.pdf
Liu, A., Ning, P.: TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks. Technical Report TR-2007-36, North Carolina State University, Department of Computer Science (November 2007)
Luk, M., Perrig, A., Whillock, B.: Seven cardinal properties of sensor network broadcast authentication. In: Proceedings of the fourth ACM workshop on Security of ad hoc and sensor networks, pp. 147–156 (2006)
Menezes, A.J., Vanstone, S.A., van Oorschot, P.C.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)
Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218–238. Springer, Heidelberg (1990)
Naor, D., Shenhav, A., Wool, A.: One-time signatures revisited: Have they become practical. Cryptology ePrint Archive, Report 2005/442 (2005), http://eprint.iacr.org/
Steinberger, J.P.: The collision intractability of mdc-2 in the ideal-cipher model. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 34–51. Springer, Heidelberg (2007)
Viega, J.: The AHASH Mode of Operation (manuscript, 2004), http://www.cryptobarn.com/
Yu-long, S., Jian-feng, M., Qing-qi, P.: An Access Control Scheme in Wireless Sensor Networks. In: IFIP International Conference on Network and Parallel Computing Workshops, 2007, pp. 362–367 (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 IFIP International Federation for Information Processing
About this paper
Cite this paper
Rohde, S., Eisenbarth, T., Dahmen, E., Buchmann, J., Paar, C. (2008). Fast Hash-Based Signatures on Constrained Devices. In: Grimaud, G., Standaert, FX. (eds) Smart Card Research and Advanced Applications. CARDIS 2008. Lecture Notes in Computer Science, vol 5189. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85893-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-85893-5_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85892-8
Online ISBN: 978-3-540-85893-5
eBook Packages: Computer ScienceComputer Science (R0)