On the performance, feasibility, and use of forward-secure signatures

ABSTRACT

Forward-secure signatures (FSSs) have recently received much attention from the cryptographic theory community as a potentially realistic way to mitigate many of the difficulties digital signatures face with key exposure. However, no previous works have explored the practical performance of these proposed constructions in real-world applications, nor have they compared FSS to traditional, non-forward-secure, signatures in a non-asymptotic way.We present an empirical evaluation of several FSS schemes that looks at the relative performance among different types of FSS as well as between FSS and traditional signatures. Our study provides the following contributions: first, a new methodology for comparing the performance of signature schemes, and second, a thorough examination of the practical performance of FSS. We show that for many cases the best FSS scheme has essentially identical performance to traditional schemes, and even in the worst case is only 2-4 times slower. On the other hand, we also show that if the wrong FSS configuration is used, the performance can be orders of magnitude slower. Our methodology provides a way to prevent such misconfigurations, and we examine common applications of digital signatures using it.We conclude that not only are forward-secure signatures a useful theoretical construct as previous works have shown, but they are also, when used correctly, a very practical solution to some of the problems associated with key exposure in real-world applications. Through our metrics and our reference implementation we provide the tools necessary for developers to efficiently use FSS.

REFERENCES

• 1: Michel Abdalla , Leonid Reyzin, A New Forward-Secure Digital Signature Scheme, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.116-129, December 03-07, 2000
• 2: R. Anderson. Two remarks on public-key cryptology From Invited Lecture, Fourth ACM Conference on Computer and Communications Security (April, 1997). http://www.cl.cam.ac.uk/TechReports/UCAM-CL-TR-549.pdf.
• 3: ANSI X9.62-1998. Public key cryptography for the financial services industry: Rhe elliptic curve digital signature algorithm (ECDSA), 1998.
• 4: Mihir Bellare , Sara K. Miner, A Forward-Secure Digital Signature Scheme, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.431-448, August 15-19, 1999
• 5: M. Bellare and B. S. Yee. Forward-security in private-key cryptography. In Topics in Cryptology - CT-RSA '03, The Cryptographers' Track at the RSA Conference 2003, 2003.
• 6: M. Blaze and J. Lacy. Simple Unix time quantization package, 1995. http://islab.oregonstate.edu/documents/People/blaze/quantize.shar.
• 7: Jurjen N. Bos , David Chaum, Provably Unforgeable Signatures, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.1-14, August 16-20, 1992
• 8: Ran Canetti , Oded Goldreich , Shai Halevi, The random oracle methodology, revisited (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.209-218, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276741]
• 9: R. Canetti, S. Halevi, and J. Katz. A forward-secure public-key encryption scheme. In Proc. of the 21st Annual IACR Eurocrypt conference (EUROCRYPT '03), 2003.
• 10: Certicom Research. SEC 2: Recommended elliptic curve domain parameters, Sep. 2000. http://www.secg.org/secg_docs.htm.
• 11: G. D. Crescenzo, N. Ferguson, R. Impagliazzo, , and M. Jakobsson. How to forget a secret. STACS '99, Lecture Notes in Computer Science, 1563:500--509, 1999.
• 12: T. Dierks and C. Allen. The TLS protocol. RFC 2246, IETF, January 1999.
• 13: W. Diffie and M. E. Hellman. Multiuser cryptographic techniques. In AFIPS Conference Proceedings, volume~45, pages 109--112, 1976.
• 14: Whitfield Diffie , Paul C. Van Oorschot , Michael J. Wiener, Authentication and authenticated key exchanges, Designs, Codes and Cryptography, v.2 n.2, p.107-125, June 1992 [doi>10.1007/BF00124891]
• 15: Yevgeniy Dodis , Jonathan Katz , Shouhuai Xu , Moti Yung, Key-Insulated Public Key Cryptosystems, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.65-82, May 02, 2002
• 16: Yevgeniy Dodis , Jonathan Katz , Shouhuai Xu , Moti Yung, Strong Key-Insulated Signature Schemes, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.130-144, January 06-08, 2003
• 17: A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. Advances in Cryptology - CRYPTO '86, Lecture Notes in Computer Science, 263:181--187, 1986.
• 18: Louis C. Guillou , Jean-Jacques Quisquater, A "Paradoxical" Indentity-Based Signature Scheme Resulting from Zero-Knowledge, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.216-231, August 21-25, 1988
• 19: Christoph G. Günther, An identity-based key-exchange protocol, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.29-37, November 1990, Houthalen, Belgium
• 20: P. Gutmann. Secure deletion of data from magnetic and solidstate memory. In Proceedings of 6th USENIX UNIX Security Symposium. USENIX Association, July 1996. San Jose, CA.
• 21: Gene Itkis , Leonid Reyzin, Forward-Secure Signatures with Optimal Signing and Verifying, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.332-354, August 19-23, 2001
• 22: Gene Itkis , Leonid Reyzin, SiBIR: Signer-Base Intrusion-Resilient Signatures, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.499-514, August 18-22, 2002
• 23: B. Kaliski. Timing attacks on cryptosystems. RSA Bulletin, 2, January 1996.
• 24: 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
• 25: A. Kozlov and L. Reyzin. Forward-secure signatures with fast key update. In Proc. of the 3rd International Conference on Security in Communication Networks (SCN '02), 2002.
• 26: Hugo Krawczyk, Simple forward-secure signatures from any signature scheme, Proceedings of the 7th ACM conference on Computer and communications security, p.108-115, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352617]
• 27: Tal Malkin , Daniele Micciancio , Sara K. Miner, Efficient Generic Forward-Secure Signatures with an Unbounded Number Of Time Periods, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.400-417, May 02, 2002
• 28: R. C. Merkle. A digital signature based on a conventional encryption function. Advances in Cryptology -- CRYPTO '89, Lecture Notes in Computer Science, pages 428--446, 1989.
• 29: National Institute of Standards and Technology. Digital signature standard, FIPS 186-2, 2000.
• 30: National Institute of Standards and Technology. Advanced encryption standard, FIPS 197, 2001.
• 31: NESSIE consortium. Portfolio of recommended cryptographic primitives, February 2003. http://www.cryptonessie.org.
• 32: H. Ong , C. P. Schnorr, Fast signature generation with a Fiat Shamir—like scheme, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.432-440, February 1991, Aarhus, Denmark
• 33: N. Provos. Encrypting virtual memory. In Proceedings of the 9th USENIX Security Symposium, pages 35--44. USENIX Association, Aug. 2000. Denver, CO.
• 34: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 35: Dawn Xiaodong Song, Practical forward secure group signature schemes, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502015]
• 36: The OpenSSL Group. OpenSLL, Oct 2003. http://http://www.openssl.org/.
• 37: Jon Viega , Pravir Chandra , Matt Messier, Network Security with Openssl, O'Reilly & Associates, Inc., Sebastopol, CA, 2002
• 38: M. J. Wiener. Performance comparison of public-key cryptosystems. CryptoBytes, 4(1), Summer 1998.

INDEX TERMS

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

General Terms:
Design, Performance, Security

Keywords:
digital signatures, forward-secure signatures