Abstract
This paper describes the design of the random number generator (RNG) in the Caernarvon high assurance smart card operating system. Since it is used in the generation of cryptographic keys and other sensitive materials, the RNG has a number of stringent security requirements that the random bits must be of good quality i.e. the bits must not be predictable or biased. To this end, a number of standards such as the German AIS 31 mandate that true random bits be continuously tested before use in sensitive applications such as key generation. A key issue in implementing this standard is that such testing before use in key generation greatly increases the attack surface for side-channel attacks. For example, template attacks which can extract information about the random bits from even a single run provided we use the same bits at many different points in the computation. Because of these potential risks, the Caernarvon operating system uses pseudo random number generators which are initially seeded by externally generated high quality random bits, and then perturbed by bits from the true random number generator. We describe a PRNG design which yields high quality random bits while also ensuring that it is not susceptible to side-channel attacks and provide an informal argument about its effectiveness.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agrawal, D., Archambeault, B., Rao, J.R., Rohatgi, P.: The EM side-channel(s). In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 29–45. Springer, Heidelberg (2003)
Bagini, V., Bucci, M.: A design of reliable true random number generator for cryptographic applications. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 204–218. Springer, Heidelberg (1999)
Barker, E., Kelsey, J.: Recommendation for random number generation using deterministic random bit generators (revised). NIST SP800-90, National Institute of Standards and Technology, Gaithersburg, MD (March 2007), http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf
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)
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)
Campbell, J., Easter, R.J.: Annex c: Approved random number generators for FIPS PUB 140-2, security requirements for cryptographic modules. FIPS PUB 140-2, Annex C, National Institute of Standards and Technology, Gaithersburg, MD (Draft of July 31, 2009), http://csrc.nist.gov/publications/fips/fips140-2/fips1402annexc.pdf
Chari, S., Rao, J.R., Rohatgi, P.: Template attacks. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 13–28. Springer, Heidelberg (2003)
Chari, S.N., Diluoffo, V.V., Karger, P.A., Palmer, E.R., Rabin, T., Rao, J.R., Rohatgi, P., Scherzer, H., Steiner, M., Toll, D.C.: Method, apparatus and system for resistence to side channel attacks on random number generators. United States Patent No. 7496616 (Filed November 12, 2004, Issued February 24, 2009)
Common Criteria for Information Technology Security Evaluation, Part 3: Security assurance requirements. Version 2.3 CCMB2005-08-003 (August 2005), http://www.commoncriteriaportal.org/public/files/ccpart3v2.3.pdf
Common Criteria for Information Technology Security Evaluation, Parts 1, 2, and 3. Version 2.3 CCMB2005-08-001, CCMB2005-08-002, and CCMB2005-08-003 (August 2005), http://www.commoncriteriaportal.org/thecc.html
Digital signature standard. FIPS PUB 186-2, with Change Notice 1, 5 October 2001, National Institute of Standards and Technology, Gaithersburg, MD (January 2000), http://csrc.nist.gov/publications/fips/archive/fips186-2/fips186-2.pdf
Dole, B.: Distributed state random number generator and method for utilizing same. United States Patent No. US6628786B1, September 30 (2003)
Epstein, M., Hars, L., Krasinski, R., Rosner, M., Zheng, H.: Design and implementation of a true random number generator based on digital circuit artifacts. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds.) CHES 2003. LNCS, vol. 2779, pp. 152–165. Springer, Heidelberg (2003)
Functionality classes and evaluation methodology for deterministic random number generators. AIS 20, Version 1, Bundesamt für Sicherheit in der Informationstechnik (BSI), Bonn, Germany, December 2 (1999), http://www.bsi.bund.de/zertifiz/zert/interpr/ais20e.pdf
Functionality classes and evaluation methodology for physical random number generators. AIS 31, Version 1, Bundesamt für Sicherheit in der Informationstechnik (BSI), Bonn, Germany, September 25 (2001), http://www.bsi.bund.de/zertifiz/zert/interpr/ais31e.pdf
ISO 7816-3, Identification cards - Integrated circuit(s) with contacts - Part 3: Electronic signals and transmission protocols, Second edition. ISO Standard 7816-3, International Standards Organization (December 1997)
Karger, P.A.: The importance of high-assurance security in pervasive computing. In: Hutter, D., Müller, G., Stephan, W., Ullmann, M. (eds.) Security in Pervasive Computing. LNCS, vol. 2802, p. 9. Springer, Heidelberg (2004), http://web.archive.org/web/20040524183841/http://www.dfki.de/spc2003/karger.pdf
Karger, P.A., Toll, D.C., McIntosh, S.K.: Processor requirements for a high security smart card operating system. In: Proc. 8th e-Smart Conference. Eurosmart, Sophia Antipolis, France, September 19-21 (2007), Available as IBM Research Division Report RC 24219 (W0703-091), http://domino.watson.ibm.com/library/CyberDig.nsf/Home
Killman, W., Schindler, W.: A proposal for: Functionality classes and evaluation methodology for true (physical) random number generators. Tech. rep., T-Systems debis Systemhaus Information Security Services and Bundesamt für Sicherheit in der Informationstechnik (BSI), Bonn, Germany (September 25, 2001), http://www.bsi.bund.de/zertifiz/zert/interpr/trngk31e.pdf
Kocher, P., Jaffe, J., Jun, B.: Differential Power Analysis: Leaking Secrets. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 143–161. Springer, Heidelberg (1999)
Maher, D.P., Rance, R.J.: Random number generators founded on signal and information theory. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 219–230. Springer, Heidelberg (1999)
Petit, C., Standaert, F.X., Pereira, O., Malkin, T., Yung, M.: A block cipher based pseudo random number generator secure against side-channel key recovery. In: ASIACCS 2008, Tokyo, Japan, March 18–20, pp. 56–65 (2008)
Schellhorn, G., Reif, W., Schairer, A., Karger, P., Austel, V., Toll, D.: Verification of a formal security model for multiapplicative smart cards. In: Cuppens, F., Deswarte, Y., Gollmann, D., Waidner, M. (eds.) ESORICS 2000. LNCS, vol. 1895, pp. 17–36. Springer, Heidelberg (2000)
Scherzer, H., Canetti, R., Karger, P.A., Krawczyk, H., Rabin, T., Toll, D.C.: Authenticating Mandatory Access Controls and Preserving Privacy for a High-Assurance Smart Card. In: Snekkenes, E., Gollmann, D. (eds.) ESORICS 2003. LNCS, vol. 2808, pp. 181–200. Springer, Heidelberg (2003)
Schindler, W., Killmann, W.: Evaluation criteria for true (physical) random number generators used in cryptographic applications. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 431–449. Springer, Heidelberg (2003)
Security IC platform protection profile. Tech. Rep. BSI-PP-0035, developed by Atmel, Infineon Technologies AG, NXP Semiconductors, Renesas Technology Europe, and STMicroelectronics, registered and certified by Bundesamt für Sicherheit in der Informationstechnik (BSI), Bonn, Germany, June 15 (2007), http://www.commoncriteriaportal.org/files/ppfiles/pp0035b.pdf
Security requirements for cryptographic modules. FIPS PUB 140-2, Change Notice 2, National Institute of Standards and Technology, Gaithersburg, MD, December 3 (2002), http://csrc.nist.gov/publications/fips/fips140-2/fips1402.pdf
Draft - security requirements for cryptographic modules. FIPS PUB 140-3, National Institute of Standards and Technology, Gaithersburg, MD, April 6 (2007), http://csrc.nist.gov/publications/fips/fips140-3/fips1403Draft.pdf
Sprunk, E.J.: Robust random number generator. United States Patent No. US6253223B1, June 26 (2001)
Tempest fundamentals (u). Declassified in 2000 under Freedom of Information Act NACSIM 5000, National Security Agency, Ft. George G. Meade, MD, February 1 (1982), http://cryptome.org/nacsim-5000.zip
Toll, D.C., Karger, P.A., Palmer, E.R., McIntosh, S.K., Weber, S.: The caernarvon secure embedded operating system. Operating Systems Review 42(1), 32–39 (2008)
Tsoi, K.H., Leung, K.H., Leong, P.H.W.: Compact FPGA-based true and pseudo random number generators. In: 11th Annual IEEE Symp. on Field-Programmable Custom Computing Machines, Napa, CA, April 9–11 (2003)
Walsh, J.J., Biesterfeldt, R.P.: Method and apparatus for generating random numbers. United States Patent No. US6480072B1, November 12 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chari, S.N. et al. (2010). Designing a Side Channel Resistant Random Number Generator. In: Gollmann, D., Lanet, JL., Iguchi-Cartigny, J. (eds) Smart Card Research and Advanced Application. CARDIS 2010. Lecture Notes in Computer Science, vol 6035. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12510-2_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-12510-2_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12509-6
Online ISBN: 978-3-642-12510-2
eBook Packages: Computer ScienceComputer Science (R0)