A software random number generator with entropy monitoring function

doi:10.7523/j.issn.2095-6134.2020.06.016

Abstract

Abstract: Random number generator (RNG) is the foundation and core of modern cryptography. The random number generated by RNG provides basic security for many cryptographic applications, such as cryptographic algorithms and security protocols. With the development of mobile Internet, Internet of things and other technologies,the traditional hardware-based random number generator has the problems of difficult hardware update and high development cost, which limits its application scope. Therefore, software RNG (SRNG) is usually used in computers, mobile terminals and other devices to provide random number services. At present, Linux, Android, Windows, and other typical operating system platforms have their own SRNG, providing software-based random number generation services. The existing research focuses on the lack of entropy of the entropy source and the internal state leakage of the post-processing module, which is the main problem affecting the random number service quality of SRNG. Therefore, a software random number generator with entropy monitoring (entropy monitoring SRNG, EM-SRNG) is designed and implemented in this paper, which uses high-precision nanosecond system clock as non-physical entropy source. The online entropy monitoring module can continuously detect the entropy of the unprocessed data when the generator is running, and call the post-processing module to improve the statistical characteristics of the data when the entropy is insufficient. In addition, the post-processing module of EM-SRNG can choose two post-processing extension algorithms designed based on SM3 and SM4 cryptography algorithms to ensure the forward/backward security of the internal state of the generator. By comparing the EM-SRNG and the Linux random number generator (LRNG, one of the current mainstream SRNGs), the experimental results show that, in terms of security, through SP 800-90B test, it is found that the output quality of EM-SRNG is equal to the data quality provided by LRNG dev/random, but slightly better than that provided by LRNG dev/random, with the minimum entropy of about 0.94/bit per bit; in terms of rate, the data generation rate of EM-SRNG is about 4 orders of magnitude higher than that of LRNG dev/random, but because the 90B statistical suite is embedded in the structure for online entropy estimation, the speed of EM-SRNG is slower than that of LRNG dev/urandom, which is about 4 Mbps.

Key words: random number generator, entropy monitoring, Linux random number generator

CLC Number:

LIU Pan, CHEN Tianyu, LÜ Na, MA Yuan, JING Jiwu. A software random number generator with entropy monitoring function[J]. , 2020, 37(6): 835-847.

References

[1] Ma Y, Chen T, Lin J, et al. Entropy estimation for ADC sampling based true random number generators[J]. IEEE Transactions on Information Forensics and Security, 2019,14(11):2887-2900.
[2] Varchola M. FPGA based true random number generators for embedded cryptographic applications[D]. Slovakia:Technical University of Kosice, 2008.
[3] Von J Neumann. Various techniques used in connection with random digits[J]. National Bureau of Standards Applied Math Series, 1951, 12:36-38.
[4] ISO/IEC 18031. Information technology-security techniques-random bit generation[S]. Berlin:International Organization for Standardization, 2011.
[5] Li W, Chen H, Chen H. Research on ARM TrustZone[J]. Getmobile Mobile Computing & Communications, 2019, 22(3):17-22.
[6] Ferraiuolo A, Baumann A, Hawblitzel C, et al. Komodo:using verification to disentangle secure-enclave hardware from software[C]//Proceedings of the 26th Symposium on Operating Systems Principles. New York:ACM, 2017:287-305.
[7] Gutterman Z, Pinkas B, Reinman T. Analysis of the linux random number generator[C]//IEEE Symposium on Security and Privacy. Oakland:IEEE, 2006:371-385.
[8] Strenzke F. An analysis of OpenSSL's random number generator[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Vienna:Springer, 2016:644-669.
[9] Kelsey J, Schneier B, Ferguson N. Yarrow-160:notes on the design and analysis of the yarrow cryptographic pseudorandom number generator[C]//International Workshop on Selected Areas in Cryptography. Kingston:Springer, 1999:13-33.
[10] Viega J. Practical random number generation in software[C]//Proceedings of the 19th Annual Computer Security Applications Conference Proceedings. Las Vegas:IEEE, 2003:129-140.
[11] 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):1-32.
[12] Szor P. Return-to-LIBC attack blocking system and method:US, 7287283[P]. 2007-10-23.
[13] Checkoway S, Davi L, Dmitrienko A, et al. Return-oriented programming without returns[C]//Proceedings of the 17th ACM conference on Computer and communications security. Chicago:ACM, 2010:559-572.
[14] National Institute of Standards & Technology. Recommendation for random number generation using deterministic random bit generators[S]. Gaithersburg:NIST Special Publication 800-90A, 2012.
[15] Bernstein, Daniel J, Lange, et al. Dual EC:a standardized back door[J]. Journal of Neurosurgery Spine, 2015, 6(3):256-281.
[16] 牛佳敏. Dual_EC_DRBG算法后门事件及NSA在其中的角色[J]. 数据通信, 2015(3):13-15.
[17] Killmann W, Schindler W. AIS 31:functionality classes and evaluation methodology for true (physical) random number generators[S]. Bonn:Bundesamt für Sicherheit in der Informationstechnik (BSI), 2001.
[18] Barak B, Halevi S. A model and architecture for pseudo-random generation with applications to/dev/random[C]//ACM Conference on Computer & Communications Security. Chicago:ACM, 2005:203-212.
[19] National Institute of Standards & Technology. A statistical test suite for the validation of random number generators and pseudo random number generators for cryptographic applications[S]. Gaithersburg:NIST Special Publication 800-22, 2010.
[20] L'Ecuyer P, Simard R J. TestU01:AC library for empirical testing of random number generators[J]. ACM Transactions on Mathematical Software (TOMS), 2007, 33(4):22.
[21] Alani M M. Testing randomness in ciphertext of block-ciphers using DieHard tests[J]. IJCSNS International Journal of Computer Science and Network Security, 2010, 10(4):53-57.
[22] 国家密码管理局. 信息安全技术二元序列随机性检测方法:GB/T 32915-2016[S]. 北京:中国标准出版社, 2016.
[23] National Institute of Standards & Technology. Recommendation for the entropy sources used for random bit generation[S]. Gaithersburg:NIST Special Publication 800-90B, 2018.
[24] Hofmann O S, Dunn A M, Kim S, et al. Ensuring operating system kernel integrity with OSck[C]//ACM SIGARCH Computer Architecture News. New York:ACM, 2011, 39(1):279-290.
[25] Lee H, Moon H, Jang D, et al. KI-Mon:a hardware-assisted event-triggered monitoring platform for mutable kernel object[C]//Proceedings of the 22th USENIX Security Symposium. Washington DC:USENIX, 2013:511-526.
[26] Jiang F, Cai Q, Lin J, et al. TF-BIV:transparent and fine-grained binary integrity verification in the cloud[C]//Proceedings of the 35th Annual Computer Security Applications Conference. San Juan:ACM, 2019:57-69.
[27] Cohney S, Kwong A, Paz S, et al. Pseudorandom black swans:cache attacks on CTR DRBG[C]//IEEE Symposium on Security and Privacy (SP). San Francisco:IEEE, 2020:750-767.