随机数发生器的设计与检测

摘要/Abstract

摘要： 随机数发生器(random number generator, RNG)在现代密码学中发挥着不可替代的作用，其生成随机数的不可预测性为密码算法和安全协议等密码应用提供基本的安全保障.一旦随机数的质量无法满足预期，则会导致密码应用存在严重的安全性风险.从RNG设计和检测的角度，对RNG的研究工作进行了全面系统的调研总结.在设计和实现方面，介绍了硬件和软件形式的TRNG研究工作；在检测方面，介绍了黑盒统计检测、熵估计方法和在线测试等RNG检测技术的研究进展.

关键词: 随机数发生器, 设计, 实现, 熵评估, 统计测试

Abstract: Random number generator (RNG) is indispensable for modern cryptography. The unpredictability of the generated random number provides basic security for cryptographic applications, such as cryptographic algorithms and security protocols. Once the quality of the random number cannot satisfy the security requirements as expected, it may lead to the existing of serious security risks in these applications. In this paper, it gives a systematic investigation and summary for the studies of RNGs from the view of design, and testing. On the design and implementation aspect, we introduce the researches on the hardware TRNGs and software TRNGs. On the testing aspect, it includes the research progress of RNG (blackbox) statistical tests, entropy estimation and online tests.

Key words: random number generator (RNG), design, implementation, entropy estimation, statistical test

马原陈天宇吴鑫莹杨静林璟锵荆继武. 随机数发生器的设计与检测[J]. 信息安全研究, 2019, 5(1): 39-49.

参考文献

[1] Bernstein D J, Chang Y A, Cheng C M, et al. Factoring RSA keys from certified smart cards: Coppersmith in the wild[G]// LNCS 8270: Advances in Cryptology – ASIACRYPT 2013. Berlin, German: Springer, 2013: 341-360 [2] Barak B, Shaltiel R, Tromer E. True random number generators secure in a changing environment[G]// LNCS 2779: Cryptographic Hardware and Embedded Systems CHES 2003. Berlin, German: Springer, 2003: 166-180 [3] Ma Y, Lin J, Chen T, et al. Entropy evaluation for oscillator-based true random number generators[G]// LNCS 8731: Cryptographic Hardware and Embedded Systems CHES 2014. Berlin, German: Springer, 2014: 544-561 [4] Sunar B, Martin W J, Stinson D R. A provably secure true random number generator with built-in tolerance to active attacks[J]. IEEE Transactions on computers, 2007, 56(1) [5] Wold K, Tan C H. Analysis and enhancement of random number generator in FPGA based on oscillator rings[J]. International Journal of Reconfigurable Computing, 2009, 2009: 4 [6] Cherkaoui A, Fischer V, Aubert A, et al. A self-timed ring based true random number generator[C]//2013 IEEE 19th Int Symp on Asynchronous Circuits and Systems. Piscataway, NJ: IEEE, 2013: 99-106 [7] Cherkaoui A, Fischer V, Fesquet L, et al. A very high speed true random number generator with entropy assessment[G]// LNCS 8086: Cryptographic Hardware and Embedded Systems CHES 2013. Berlin, German: Springer, 2013: 179-196 [8] Kohlbrenner P, Gaj K. An embedded true random number generator for FPGAs[C]//Proc of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays. New York, NY: ACM, 2004: 71-78 [9] Yang J, Ma Y, Chen T, et al. Extracting More Entropy for TRNGs Based on Coherent Sampling[C]//Security and Privacy in Communication Systems. Berlin, German: Springer, 2016: 694-709 [10] Rozic V, Yang B, Dehaene W, et al. Highly efficient entropy extraction for true random number generators on FPGAs[C]// Proc of 52nd ACM/EDAC/IEEE Design Automation Conference. Piscataway, NJ: IEEE, 2015: 1-6 [11] Markettos A T, Moore S W. The frequency injection attack on ring-oscillator-based true random number generators[G]// LNCS 5747: Cryptographic Hardware and Embedded Systems CHES 2009. Berlin, German: Springer, 2009: 317-331 [12] Hata H, Ichikawa S. FPGA implementation of metastability-based true random number generator[J]. IEICE TRANSACTIONS on Information and Systems, 2012, 95(2): 426-436 [13] Varchola M. FPGA based true random number generators for embedded cryptographic applications[D]. Kosice: Technical University of Kosice, 2008, 1: 74-76 [14] Danger J L, Guilley S, Hoogvorst P. High speed true random number generator based on open loop structures in FPGAs[J]. Microelectronics journal, 2009, 40(11): 1650-1656 [15] Majzoobi M, Koushanfar F, Devadas S. FPGA-based true random number generation using circuit metastability with adaptive feedback control[G]// LNCS 6917: Cryptographic Hardware and Embedded Systems CHES 2011. Berlin, German: Springer, 2011: 17-32 [16] Ergün S. A high-speed truly random number generator based on an autonomous chaotic oscillator[C]//Proc of Asia Pacific Conference on Circuits and Systems 2014. Piscataway, NJ: IEEE, 2014: 217-220 [17] Ergün S, Özog̃uz S. A truly random number generator based on a continuous-time chaotic oscillator for applications in cryptography[G]// LNCS 3733: Computer and Information Sciences ISCIS 2005. Berlin, German: Springer, 2005: 205-214 [18] Koyuncu I, Ozcerit A T, Pehlivan I, et al. Design and implementation of chaos based true random number generator on FPGA[C]//Proc of 22nd Signal Processing and Communications Applications Conf (SIU). Piscataway, NJ: IEEE, 2014: 236-239 [19] Zhou T, Zhou Z, Yu M, et al. Design of a low power high entropy chaos-based truly random number generator[C]//Proc of 2006 IEEE Asia Pacific Conf on Circuits and Systems. Piscataway, NJ: IEEE, 2006: 1955-1958 [20] Davies R B. Exclusive OR (XOR) and hardware random number generators[J]. Retrieved May, 2002, 31: 2013 [Online]. Available: http://www.robertnz.net [21] Von Neumann J. Various techniques used in connection with random digits[J]. National Bureau of Standards, Applied Math Series, 1951, 12(36-38): 1 [22] Dichtl M. Bad and good ways of post-processing biased physical random numbers[G]// LNCS 4593: Fast Software Encryption 2007. Berlin, German: Springer, 2007: 137-152 [23] Lacharme P. Post-processing functions for a biased physical random number generator[G]// LNCS 5086: Fast Software Encryption 2008. Berlin, German: Springer, 2008: 334-342 [24] Colbourn C J, Dinitz J H, Stinson D R. Applications of Combinatorial Designs to Communications, Cryptography, and Networking[J]. Surveys in Combinatorics, 1999:37-100. [25] Sunar B, Martin W J, Stinson D R. A provably secure true random number generator with built-in tolerance to active attacks[J]. IEEE Transactions on computers, 2007, 56(1) [26] Barak B, Halevi S. An architecture for robust pseudo-random generation and applications to/dev/random[C]//Proc of ACM Conf on Computer and Communications Security. New York, NY: ACM, 2005:203 - 212. [27] Gutmann P. Software Generation of Practically Strong Random Numbers[C]//Proc of the 7th USENIX Security Symp. Berkeley, CA: USENIX, 1998 [28] Shamir A. On the generation of cryptographically strong pseudorandom sequences[J]. ACM Transactions on Computer Systems (TOCS), 1983, 1(1): 38-44 [29] Kelsey J, Schneier B, Ferguson N. Yarrow-160: Notes on the design and analysis of the yarrow cryptographic pseudorandom number generator[G]// LNCS 1758: Selected Areas in Cryptography 1999. Berlin, German: Springer, 1999: 13-33 [30] Murray M R V. An Implementation of the Yarrow PRNG for FreeBSD[C]//Proc of BSDCon 2002. Berkeley, CA: USENIX, 2002: 47-53 [31] Viega J. Practical random number generation in software[C]//Proc of 19th Annual Computer Security Applications Conf. Piscataway, NJ: IEEE, 2003: 129-140 [32] Ferguson N, Schneier B. Practical cryptography[M]. New York: Wiley, 2003 [33] Gutterman Z, Pinkas B, Reinman T. Analysis of the linux random number generator[C]//Proc of 2006 IEEE Symp on Security and Privacy (S&P'06). Piscataway, NJ: IEEE, 2006 [34] Dorrendorf L, Gutterman Z, Pinkas B. Cryptanalysis of the random number generator of the windows operating system[J]. ACM Transactions on Information and System Security (TISSEC), 2009, 13(1): 10 [35] Yoo D, Yeom Y. The OpenWRT’s Random Number Generator Designed Like/dev/urandom and Its Vulnerability[C]//Advances in Computer Science and Ubiquitous Computing CSA-CUTE2016. Berlin, German: Springer, 2016: 825-830 [36] Kim S H, Han D, Lee D H. Predictability of Android OpenSSL's pseudo random number generator[C]//Proc of the 2013 ACM SIGSAC conference on Computer & communications security. New York, NY: ACM, 2013: 659-668 [37] Strenzke F. An analysis of OpenSSL’s random number generator[G]// LNCS 9665: Advances in Cryptology EUROCRYPT 2016. Berlin, German: Springer, 2016: 644-669 [38] Federal information processing standards publication fips pub 140-1 [S]. U.S. National Institute of Standards and Technology, Tech. Rep., January 1994 [39] Federal information processing standards publication fips pub 140-2 [S]. U.S. National Institute of Standards and Technology, Tech. Rep., May 2001 [40] Rukhin A, Soto J, Nechvatal J, et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications[R]. Mclean Va: Booz-Allen and Hamilton Inc, 2001 [41] Barker E B, Kelsey J M. Recommendation for random number generation using deterministic random bit generators (revised)[M]. US: US Department of Commerce, Technology Administration, National Institute of Standards and Technology, Computer Security Division, Information Technology Laboratory, 2007 [42] Killmann W, Schindler W. A proposal for: Functionality classes for random number generators[S]. Bonn: Bundesamt fur Sicherheit in der Informationstechnik, 2011 [43] GM/T 0005-2012 随机性检测规范[S]. 北京：国家密码管理局，2012 [44] Marsaglia G. The Marsaglia random number CDROM including the diehard battery of tests of randomness[J]. http://www. stat. fsu. edu/pub/diehard/, 2008 [45] L'Ecuyer P, Simard R. TestU01: AC library for empirical testing of random number generators[J]. ACM Transactions on Mathematical Software (TOMS), 2007, 33(4): 22 [46] Kim S J, Umeno K, Hasegawa A. Corrections of the NIST statistical test suite for randomness[J]. IACR Cryptology ePrint Archive, 2004 [47] Hamano K. The distribution of the spectrum for the discrete Fourier transform test included in SP800-22[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2005, 88(1): 67-73 [48] Hamano K, Kaneko T. Correction of overlapping template matching test included in NIST randomness test suite[J]. IEICE transactions on fundamentals of electronics, communications and computer sciences, 2007, 90(9): 1788-1792 [49] Sulak F, Doğanaksoy A, Ege B, et al. Evaluation of randomness test results for short sequences[G]// LNCS 6338: Sequences and Their Applications SETA 2010. Berlin, German: Springer, 2010: 309-319 [50] Pareschi F, Rovatti R, Setti G. Second-level NIST randomness tests for improving test reliability[C]//Proc of 2007 IEEE Int Symp on Circuits and Systems. Piscataway, NJ: IEEE, 2007: 1437-1440 [51] Pareschi F, Rovatti R, Setti G. On statistical tests for randomness included in the NIST SP800-22 test suite and based on the binomial distribution[J]. IEEE Transactions on Information Forensics and Security, 2012, 7(2): 491-505 [52] Turan M S, DoĞanaksoy A, Boztaş S. On independence and sensitivity of statistical randomness tests[G]// LNCS 5203: Sequences and Their Applications SETA 2008. Berlin, German: Springer, 2008: 18-29 [53] 范丽敏, 冯登国, 陈华. 基于熵的随机性检测相关性研究[J]. 软件学报, 2009, 20(7): 1967-1976 [54] Sulak F, UĞUZ M, Kocak O, et al. On the independence of statistical randomness tests included in the NIST test suite[J]. Turkish Journal of Electrical Engineering & Computer Sciences, 2017, 25(5): 3673-3683 [55] Chen M, Chen H, Fan L, et al. Templates selection in non-overlapping template matching test[J]. Electronics Letters, 2016, 52(18): 1533-1535 [56] Sýs M, Říha Z, Matyáš V. Algorithm 970: Optimizing the NIST Statistical Test Suite and the Berlekamp-Massey Algorithm[J]. ACM Transactions on Mathematical Software (TOMS), 2017, 43(3): 27 [57] Huang J, Lai X. Measuring random tests by conditional entropy and optimal execution order[G]// LNCS 6802: Trusted Systems 2010. Berlin, German: Springer, 2010: 148-159 [58] Killmann W, Schindler W. A design for a physical RNG with robust entropy estimators[G]// LNCS 5154: Cryptographic Hardware and Embedded Systems CHES 2008. Berlin, German: Springer, 2008: 146-163 [59] Baudet M, Lubicz D, Micolod J, et al. On the security of oscillator-based random number generators[J]. Journal of cryptology, 2011, 24(2): 398-425 [60] Zhu S, Ma Y, Chen T, et al. Analysis and Improvement of Entropy Estimators in NIST SP 800-90B for Non-IID Entropy Sources[J]. IACR Transactions on Symmetric Cryptology, 2017, 2017(3): 151-168 [61] Hagerty P, Draper T. Entropy bounds and statistical tests[C]//NIST Random Bit Generation Workshop. Gaithersburg: NIST, 2012: 1319-1327 [62] Kelsey J, McKay K A, Turan M S. Predictive models for min-entropy estimation[G]// LNCS 9293: Cryptographic Hardware and Embedded Systems CHES 2015. Berlin, German: Springer, 2015: 373-392 [63] Schindler W. Efficient online tests for true random number generators[G]// LNCS 2162: Cryptographic Hardware and Embedded Systems CHES 2001. Berlin, German: Springer, 2001: 103-117 [64] Bucci M, Luzzi R. Design of testable random bit generators[G]// LNCS 3659: Cryptographic Hardware and Embedded Systems CHES 2005. Berlin, German: Springer, 2005: 147-156 [65] Fischer V, Lubicz D. Embedded evaluation of randomness in oscillator based elementary TRNG[G]// LNCS 8731: Cryptographic Hardware and Embedded Systems CHES 2014. Berlin, German: Springer, 2014: 527-543 [66] Haddad P, Teglia Y, Bernard F, et al. On the assumption of mutual independence of jitter realizations in P-TRNG stochastic models[C]//Proc of the conf on Design, Automation & Test in Europe. Belgium: European Design and Automation Association, 2014: 39 [67] Lubicz D, Bochard N. Towards an oscillator based TRNG with a certified entropy rate[J]. IEEE Transactions on Computers, 2015, 64(4): 1191-1200 [68] Yang B, Rozic V, Grujic M, et al. On-chip jitter measurement for true random number generators[C]//Proc of 2017 Asian Hardware Oriented Security and Trust Symposium (AsianHOST). Piscataway, NJ: IEEE, 2017: 91-96