×

On the security of oscillator-based random number generators. (English) Zbl 1251.94021

Summary: Physical random number generators (a.k.a. TRNGs) appear to be critical components of many cryptographic systems. Yet, such building blocks are still too seldom provided with a formal assessment of security, in comparison to what is achieved for conventional cryptography. In this work, we present a comprehensive statistical study of TRNGs based on the sampling of an oscillator subject to phase noise (a.k.a. phase jitters). This classical layout, typically instantiated with a ring oscillator, provides a simple and attractive way to implement a TRNG on a chip. Our mathematical study allows one to evaluate and control the main security parameters of such a random source, including its entropy rate and the biases of certain bit patterns, provided that a small number of physical parameters of the oscillator are known. In order to evaluate these parameters in a secure way, we also provide an experimental method for filtering out the global perturbations affecting a chip and possibly visible to an attacker. Finally, from our mathematical model, we deduce specific statistical tests applicable to the bitstream of a TRNG. In particular, in the case of an insecure configuration, we show how to recover the parameters of the underlying oscillator.

MSC:

94A60 Cryptography
60G35 Signal detection and filtering (aspects of stochastic processes)
62M07 Non-Markovian processes: hypothesis testing
65C10 Random number generation in numerical analysis
94A17 Measures of information, entropy
Full Text: DOI

References:

[1] A. Abcunas, C. Coughlin, G. Pedro, D. Reisberg, Evaluation of random number generators on FPGAs. Technical report, Worcester Polytechnic Institute, 2004
[2] Bock, H.; Bucci, M.; Luzzi, R., An offset-compensated oscillator-based random bit source for security applications, CHES, 268-281 (2004) · Zbl 1104.68466
[3] W. Coppock, C. Philbrook, A mathematical and physical analysis of circuit jitter with application to cryptographic random bit generation. Technical report, Worcester Polytechnic Institute, 2005
[4] Cox, D. R.; Miller, H. D., The Theory of Stochastic Processes (1977), Boca Raton: CRC Press, Boca Raton · Zbl 0359.60004
[5] Demir, A.; Mehrotra, A.; Roychowdhury, J., Phase noise in oscillators: A unifying theory and numerical methods for characterisation, DAC ’98: Proceedings of the 35th Annual Conference on Design Automation, 26-31 (1998), New York: ACM, New York
[6] Dichtl, M.; Golic, J. D., High-speed true random number generation with logic gates only, CHES, 45-62 (2007) · Zbl 1301.65006
[7] Epstein, M.; Hars, L.; Krasinski, R.; Rosner, M.; Zheng, H., Design and implementation of a true random number generator based on digital circuit artifacts, CHES, 152-165 (2003)
[8] Hajimiri, A.; Lee, T., A general theory of phase noise in electrical oscillators, IEEE J., 33, 2, 179-194 (1998)
[9] Hajimiri, A.; Limotyrakis, S.; Lee, T., Jitter and phase noise in ring oscillators, IEEE J., 34, 6, 790-804 (1999)
[10] Killmann, W.; Schindler, W., A design for a physical RNG with robust entropy estimators, CHES, 146-163 (2008)
[11] NIST SP800-22 rev. 1. A statistical test suite for random and pseudorandom number generators for cryptographic applications, August 2008
[12] J. Pliam, The disparity between work and entropy in cryptology. Cryptology ePrint Archive, Report 1998/024, 1998
[13] Schindler, W., A stochastical model and its analysis for a physical random number generator presented at CHES 2002, Cryptography and Coding, 276-289 (2003) · Zbl 1123.94360
[14] Schindler, W.; Killmann, W., Evaluation criteria for true (physical) random number generators used in cryptographic applications, CHES, 431-449 (2002) · Zbl 1019.65502
[15] Shannon, C. E., A mathematical theory of communication, Bell Syst. Tech. J., 27, 379-423 (1948) · Zbl 1154.94303
[16] Sunar, B.; Martin, W. J.; Stinson, D. R., A provably secure true random number generator with built-in tolerance to active attacks, IEEE (2007) · Zbl 1391.94799
[17] Tijms, H. C., A First Course in Stochastic Models (2003), New York: Wiley, New York · Zbl 1088.60002
[18] Valtchanov, B.; Aubert, A.; Bernard, F.; Fischer, V., Modeling and observing the jitter in ring oscillators implemented in FPGAs, 11th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems, 1-16 (2008), New York: IEEE, New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.