Cryptographic Key Reliable Lifetimes: Bounding the Risk of Key Exposure in the Presence of Faults | SpringerLink
Skip to main content
Springer Nature Link
Log in

Cryptographic Key Reliable Lifetimes: Bounding the Risk of Key Exposure in the Presence of Faults

  • Conference paper
Fault Diagnosis and Tolerance in Cryptography (FDTC 2006)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 4236))

Abstract

With physical attacks threatening the security of current cryptographic schemes, no security policy can be developed without taking into account the physical nature of computation.

In this paper we adapt classical reliability modeling techniques to cryptographic systems. We do so by first introducing the notions of Cryptographic Key Failure Tolerance and Cryptographic Key Reliable Lifetimes. Then we offer a framework for the determination of reliable lifetimes of keys for any cryptographic scheme used in the presence of faults, given an accepted (negligible) error-bound to the risk of key exposure. Finally we emphasize the importance of selecting keys and designing schemes with good values of failure tolerance, and recommend minimal values for this metric. In fact, in standard environmental conditions, cryptographic keys that are especially susceptible to erroneous computations (e.g., RSA keys used with CRT-based implementations) are exposed with a probability greater than a standard error-bound (e.g., 2− − 40) after operational times shorter than one year, if the failure-rate of the cryptographic infrastructure is greater than 1.04×10− − 16 failures/hours.

A preliminary version of this paper appeared as a COSIC Technical Report.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Anderson, R.J.: Liability and Computer Security: Nine Principles. In: Gollmann, D. (ed.) ESORICS 1994. LNCS, vol. 875, pp. 231–245. Springer, Heidelberg (1994)

    Google Scholar 

  2. Anderson, R.J.: Why Cryptosystems Fail. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, pp. 215–227 (1993)

    Google Scholar 

  3. Anderson, R.J.: Why Cryptosystems Fail. Communications if the ACM (November 1994)

    Google Scholar 

  4. Anderson, R.J., Bezuidenhout, S.: On the Security of Prepayment Metering Systems (to appear)

    Google Scholar 

  5. Aumüller, C., Bier, P., Fischer, W., Hofreiter, P., Seifert, J.P.: Fault Attacks on RSA with CRT: Concrete Results and Practical Countermeasures. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 260–275. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  6. Bertoni, G., Breveglieri, L., Koren, I., Maistri, P., Piuri, V.: Error Analysis and Detection Procedures for a Hardware Implementation of the Advanced Encryption Standard. IEEE Transactions on Computers 52(4), 493–505 (2003)

    Article  Google Scholar 

  7. Bertoni, G., Breveglieri, L., Koren, I., Maistri, P., Piuri, V.: On the Propagation of Faults and Their Detection in a Hardware Implementation of the Advanced Encryption Standard. In: Proc. Int’l Conf. Application-Specific Systems, Architectures, and Processors (ASAP 2002), pp. 303–312 (2002)

    Google Scholar 

  8. Bertoni, G., Breveglieri, L., Koren, I., Piuri, V.: Fault Detection in the Advanced Encryption Standard. In: Proc. Conf. Massively Parallel Computing Systems (MPCS 2002), pp. 92–97 (2002)

    Google Scholar 

  9. Biham, E., Shamir, A.: Differential Fault Analysis of Secret Key Cryptosystems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 513–525. Springer, Heidelberg (1997)

    Google Scholar 

  10. Blaze, M., Diffie, W., Rivest, R., Schneier, B., Shimomura, T., Thompson, E., Wiener, M.: Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security, Report of ad-hoc panel of cryptographers and computer scientists (January 1996), Available via: http://www.crypto.com/papers/

  11. Boeyen, S., Howes, T., Richard, P.: Internet X.509 Public Key Infrastructure LDAPv2 Schema, Internet Engineering Task Force, RFC 2587 (June 1999), available via: http://www.ietf.org/rfc/rfc2587.txt

  12. Boneh, D., DeMillo, R.A., Lipton, R.J.: On the Importance of Checking Computations. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 37–51. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  13. Boneh, D., DeMillo, R.A., Lipton, R.J.: On the Importance of Checking Cryptographic Protocols for Faults. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 37–51. Springer, Heidelberg (1997)

    Google Scholar 

  14. Boneh, D., DeMillo, R.A., Lipton, R.J.: On the Importance of Eliminating Errors in Cryptographic Computations. Journal of Cryptology 14(2), 101–119 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  15. Ciet, M., Joye, M.: Elliptic Curve Cryptosystems in the Presence of Permanent and Transient Fault, Cryptology ePrint Archive, Report 2003/028 (2003), available via: http://eprint.iacr.org/2003/028

  16. Dottax, E.: Fault Attacks on NESSIE Signature and Identification Schemes, report NES/DOC/ENS/WP5/031/1 of the NESSIE Project (2002), https://www.cosic.esat.kuleuven.be/nessie/reports/phase2/SideChan_1.pdf

  17. ECRYPT - European Network of Excellence in Cryptology, ECRYPT Yearly Report on Algorithms and Keysizes (2004), D.SPA.10, Revision 1.1 (March 17, 2005), http://www.ecrypt.eu.org/documents/D.SPA.10-1.1.pdf

  18. ETSI, SR 002 176 V1.1.1 Special Report, Electronic Signatures and Infrastructures (ESI); Algorithms and Parameters for Secure Electronic Signatures (March 2003)

    Google Scholar 

  19. Federal Information Processing Standards Publication 140-2, Security Requirements for Cryptographic Modules

    Google Scholar 

  20. Giraud, C.: DFA on AES, Cryptology ePrint Archive, Report 2003/008 (2003), available via: http://eprint.iacr.org/2003/008

  21. Graham, P., Caffrey, M., Zimmerman, J., Sundararajan, P., Johnson, E., Patterson, C.: Consequences and Categories of SRAM FPGA Configuration SEUs. In: Proc. of Military and Aerospace Applications of Programmable Logic Devices (MAPLD 2003), September 9-11 (2003)

    Google Scholar 

  22. Iyer, R.K., Lee, I.: Measurement-Based Analysis of Software Reliability. In: Lyu, M. (ed.) Handbook of Sofware Reliability Engineering, pp. 303–358. IEEE Computer Society Press and McGraw-Hill (1996)

    Google Scholar 

  23. Ishai, Y., Sahai, A., Wagner, D.: Private Circuits: Securing Hardware against Probing Attacks. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 463–481. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  24. Harvey, I.: The DFC Cipher: an attack on careless implementations. In: The Rump Session of Second AES Candidate Conference (AES2), March 22-23 (1999)

    Google Scholar 

  25. Kaliski, B.: TWIRL and RSA Key Size, RSA Laboratories Technical Notes, Revised (May 6, 2003)

    Google Scholar 

  26. Karri, R., Kaijie, W., Mishra, P., Yongkook, K.: Fault-Based Side-Channel Cryptanalysis Tolerant Rijndael Symmetric Block Cipher Architecture. In: Proc. Defect and Fault Tolerance in VLSI Systems (DFN 2001), pp. 418–426 (2001)

    Google Scholar 

  27. Lenstra, A.K.: Memo on RSA signature generation in the presence of faults, Available at: http://cm.bell-labs.com/who/akl/rsa.doc

  28. Lenstra, A.K.: Unbelievable security. Matching AES security using public key systems. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 67–86. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  29. Lenstra, A.K., Verheul, E.R.: Selecting Cryptographic Key Sizes. Journal of Cryptology 14(4), 255–293 (2001)

    MATH  MathSciNet  Google Scholar 

  30. Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)

    Book  Google Scholar 

  31. Micali, S., Reyzin, L.: Physically Observable Cryptography. Cryptology ePrint Archive: Report 2003/120 (2003), http://eprint.iacr.org/2003/120

  32. NESSIE Consortium, Portfolio of Recommended Cryptographic Primitives (February 27, 2003), Available via: http://www.cryptonessie.org/

  33. NIST, Special Publication 800-57: Recommendation for Key Management, Part 1: General Guideline. Draft (January 2003), Available at: http://csrc.nist.gov/CryptoToolkit/tkkeymgmt.html

  34. Normand, E.: Single Event Upset at Ground Level. IEEE Transactions on Nuclear Science 43(6) (December 1996)

    Google Scholar 

  35. Orman, H., Hoffman, P.: Determining Strengths For Public Keys Used For Exchanging Symmetric Keys, Internet Engineering Task Force, RFC 3766/BCP 86 (April 2004), Available via: http://www.ietf.org/rfc/rfc3766.txt

  36. Piret, G., Quisquater, J.J.: A Differential Fault Attack Technique against SPN Structures, with Applications to the AES and KHAZAD. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds.) CHES 2003. LNCS, vol. 2779, pp. 77–88. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  37. RSA Labs, A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths, RSA Labs Bulletin #13, Available at: http://www.rsasecurity.com/rsalabs/

  38. SQUALE Consortium, Dependability Assessment Criteria (January 1999), http://www.newcastle.research.ec.org/squale/SQUALE4.pdf

  39. Shamir, A.: Method and Apparatus for protecting public key schemes from timing and fault attacks, U.S. Patent Number 5, 991, 415 (November 1999); also presented at the rump session of EUROCRYPT 1997 (1997)

    Google Scholar 

  40. Trivedi, K.S.: Probability and Statistics with Reliability, Queueing, and Computer Science Applications, 2nd edn. John Wiley and Sons, New York (2001)

    Google Scholar 

  41. Wagner, D.: Cryptanalysis of a provably secure CRT-RSA algorithm. In: the Proceedings of ACM Conference on Computer and Communications Security, pp. 92–97 (2004)

    Google Scholar 

  42. Williams, L.C.: A Discussion of the Importance of Key Length in Symmetric and Asymmetric Cryptography, Available via: http://www.giac.org/practical/gsec/LorraineWilliamsGSEC.pdf

Download references

Author information

Authors and Affiliations

  1. Andxor S.r.l., via F.lli Gracchi, 27, Cinisello Balsamo (MI), 20092, Italy

    Alfonso De Gregorio

Authors
  1. Alfonso De Gregorio
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Electronics and Information Technology, Politecnico di Milano, Milano, Italy

    Luca Breveglieri

  2. Department of Electrical and Computer Engineering,, University of Massachusetts, Amherst, MA, USA

    Israel Koren

  3. École normale supérieure, Équipe de cryptographie, 45 rue d’Ulm, F-75230, Paris cedex 05, France

    David Naccache

  4. Institute for Computer Science, University of Innsbruck, 6020, Innsbruck, Austria

    Jean-Pierre Seifert

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

De Gregorio, A. (2006). Cryptographic Key Reliable Lifetimes: Bounding the Risk of Key Exposure in the Presence of Faults. In: Breveglieri, L., Koren, I., Naccache, D., Seifert, JP. (eds) Fault Diagnosis and Tolerance in Cryptography. FDTC 2006. Lecture Notes in Computer Science, vol 4236. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11889700_14

Download citation

  • DOI: https://doi.org/10.1007/11889700_14

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-46250-7

  • Online ISBN: 978-3-540-46251-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation