Abstract
True random number generators (TRNGs) are crucial to the implementations of cryptographic algorithms and protocols. The quality of randomness directly influences the security of cryptographic systems. Oscillator-based sampling is popular in the design of TRNGs due to its nice properties of elegant structure and high speed. However, the credibility of randomness generated from high-speed oscillator-based TRNGs, especially ring oscillator-based (RO-based) ones, is still in controversy. This is mainly because pseudo-randomness is hardly distinguished from true randomness and RO-based TRNGs are susceptible to external perturbations. In this paper, we present a stochastic model to evaluate the entropy of oscillator-based TRNGs, and then deduce the requirement of design parameters (including the sampling interval) for sufficient entropy per random bit, i.e., to ensure true randomness. Furthermore, we design a jitter measuring circuit to verify the theory, and the theoretical results are confirmed by both the simulation and practical experiments. Finally, we apply the stochastic model to analyze the effect of deterministic perturbations, and demonstrate that the randomness of RO-based TRNGs (under deterministic perturbations) can be overestimated and predicting the “random” bits could be possible.
Chapter PDF
Similar content being viewed by others
References
Amaki, T., Hashimoto, M., Mitsuyama, Y., Onoye, T.: A worst-case-aware design methodology for noise-tolerant oscillator-based true random number generator with stochastic behavior modeling. IEEE Transactions on Information Forensics and Security 8(8), 1331–1342 (2013)
Baudet, M., Lubicz, D., Micolod, J., Tassiaux, A.: On the security of oscillator-based random number generators. J. Cryptology 24(2), 398–425 (2011)
Bernard, F., Fischer, V., Valtchanov, B.: Mathematical model of physical RNGs based on coherent sampling. Tatra Mountains Mathematical Publications 45(1), 1–14 (2010)
Bochard, N., Bernard, F., Fischer, V., Valtchanov, B.: True-randomness and pseudo-randomness in ring oscillator-based true random number generators. Int. J. Reconfig. Comp. 2010 (2010)
Bucci, M., Germani, L., Luzzi, R., Trifiletti, A., Varanonuovo, M.: A high-speed oscillator-based truly random number source for cryptographic applications on a smart card IC. IEEE Transactions on Computers 52(4), 403–409 (2003)
Coppock, W.R., Philbrook, C.R.: A mathematical and physical analysis of circuit jitter with application to cryptographic random bit generation. Major qualifying project report, Worcester Polytechnic Institute (2005)
Dichtl, M., Golić, J.D.: High-speed true random number generation with logic gates only. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 45–62. Springer, Heidelberg (2007)
Fischer, V., Bernard, F., Bochard, N., Varchola, M.: Enhancing security of ring oscillator-based trng implemented in FPGA. In: FPL, pp. 245–250 (2008)
Haddad, P., Teglia, Y., Bernard, F., Fischer, V.: On the assumption of mutual independence of jitter realizations in P-TRNG stochastic models. In: IEEE Design, Automation and Test in Europe Conference and Exhibition (DATE), pp. 1–6 (2014)
Hajimiri, A., Limotyrakis, S., Lee, T.H.: Jitter and phase noise in ring oscillators. IEEE Journal of Solid-State Circurts 34(6) (1999)
Information Technology Laboratory: FIPS 140-2: Security Requirement For Cryptographic Modules (2011)
Killmann, W., Schindler, W.: A design for a physical RNG with robust entropy estimators. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 146–163. Springer, Heidelberg (2008)
Markettos, A.T., Moore, S.W.: The frequency injection attack on ring-oscillator-based true random number generators. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 317–331. Springer, Heidelberg (2009)
Marsaglia, G.: Diehard Battery of Tests of Randomness, http://www.stat.fsu.edu/pub/diehard/
Petrie, C., Connelly, J.: A noise-based IC random number generator for applications in cryptography. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 47(5), 615–621 (2000)
Rukhin, A., et al.: A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST Special Publication 800–22, http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf
Sunar, B., Martin, W.J., Stinson, D.R.: A provably secure true random number generator with built-in tolerance to active attacks. IEEE Transactions on Computers 56(1), 109–119 (2007)
Valtchanov, B., Aubert, A., Bernard, F., Fischer, V.: Modeling and observing the jitter in ring oscillators implemented in FPGAs. In: DDECS, pp. 158–163 (2008)
Valtchanov, B., Fischer, V., Aubert, A., Bernard, F.: Characterization of randomness sources in ring oscillator-based true random number generators in FPGAs. In: DDECS, pp. 48–53 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ma, Y., Lin, J., Chen, T., Xu, C., Liu, Z., Jing, J. (2014). Entropy Evaluation for Oscillator-Based True Random Number Generators. In: Batina, L., Robshaw, M. (eds) Cryptographic Hardware and Embedded Systems – CHES 2014. CHES 2014. Lecture Notes in Computer Science, vol 8731. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44709-3_30
Download citation
DOI: https://doi.org/10.1007/978-3-662-44709-3_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44708-6
Online ISBN: 978-3-662-44709-3
eBook Packages: Computer ScienceComputer Science (R0)