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. M. Abdalla and L. Reyzin. A new forward-secure digital signature scheme. Advances in Cryptology -- ASIACRYPT 2000, Lecture Notes in Computer Science, 1976:116--129, Dec. 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. M. Bellare and S. K. Miner. A forward-secure digital signature scheme. Advances in Cryptology -- CRYPTO '99, Lecture Notes in Computer Science, 1666:431--448, Aug. 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. J. N. Bos and D. Chaum. Provably unforgeable signatures. Advances in Cryptology -- CRYPTO '92, Lecture Notes in Computer Science, 740:1--14, 1993.]]
8. R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited. In Proc. of the thirtieth annual ACM symposium on Theory of computing (STOC '98), 1998.]]
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. W. Diffie, P. C. van Oorschot, and M. J. Wiener. Authentication and authenticated key exchanges. Designs, Codes, and Cryptography, 2(2), 1992.]]
15. Y. Dodis, J. Katz, S. Xu, and M. Yung. Key-insulated public key cryptosystems. In Proc. of the 20th Annual IACR Eurocrypt conference (EUROCRYPT '02), 2002.]]
16. Y. Dodis, J. Katz, S. Xu, and M. Yung. Strong key-insulated signature schemes. In Proc. of the 6th Annual International Workshop on Practice and Theory in Public Key Cryptography (PKC '03), 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. L. C. Guillou and J.-J. Quisquater. A "paradoxical" identity-based signature scheme resulting from zero-knowledge. Advances in Cryptology -- CRYPTO '88, Lecture Notes in Computer Science, 403:216--231, Aug. 1988.]]
19. C. Gunther. An identity-based key-exchange protocol. In Proc. of the 7th Annual IACR Eurocrypt conference (EUROCRYPT '89), 1989.]]
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. G. Itkis and L. Reyzin. Forward-secure signatures with optimal signing and verifying. Advances in Cryptology -- CRYPTO '01, Lecture Notes in Computer Science, 2139:332--354, Aug. 2001.]]
22. G. Itkis and L. Reyzin. SiBIR: Signer-base intrusion-resilient signatures. Advances in Cryptology -- CRYPTO '02, Lecture Notes in Computer Science, 2442, Aug. 2002.]]
23. B. Kaliski. Timing attacks on cryptosystems. RSA Bulletin, 2, January 1996.]]
24. P. C. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. Advances in Cryptology -- CRYPTO '96, Lecture Notes in Computer Science, 1109:104--113, 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. H. Krawczyk. Simple forward-secure signatures from any signature scheme. In Proc. of Seventh ACM Conference on Computer and Communications Security, pages 108--115, Nov. 2000.]]
27. T. Malkin, D. Micciancio, and S. Miner. Efficient generic forward-secure signatures with an unbounded number of time periods. In Proc. of the 20th Annual IACR Eurocrypt conference (EUROCRYPT '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 and C. P. Schnorr. Fast signature generation with a fiat-shamir-like scheme. In Proc. of the 8th Annual IACR Eurocrypt conference (EUROCRYPT '90), 1990.]]
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. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120--126, Feb. 1978.]]
35. D. X. Song. Practical forward secure group signature schemes. In Proc. of the 8th ACM Conference on Computer and Communications Security (CCS '01), 2001.]]
36. The OpenSSL Group. OpenSLL, Oct 2003. http://http://www.openssl.org/.]]
37. J. Viega, M. Messier, and P. Chandra. Network Security with OpenSSL. O'Reilly & Associates, Inc., 2002.]]
38. M. J. Wiener. Performance comparison of public-key cryptosystems. CryptoBytes, 4(1), Summer 1998.]]

Index Terms

• Security and privacy

  • Cryptography

    • Public key (asymmetric) techniques

      • Public key encryption