一种带有熵监控功能的软件随机数发生器

doi:10.7523/j.issn.2095-6134.2020.06.016

摘要/Abstract

摘要： 随机数发生器（random number generator，RNG）在现代密码学中处于基础而核心的地位，其生成的随机数为密码算法和安全协议等众多密码应用提供基本安全保障。随着移动互联网、物联网等技术的快速发展，传统纯硬件形式的随机数发生器存在硬件更新困难、开发成本高等问题，导致适用范围受限。因此，在计算机、移动终端等设备上通常采用软件随机数发生器（software RNG，SRNG）提供随机数服务。目前，Linux、Android、iOS以及Windows等典型操作系统平台均具备各自的SRNG，提供基于软件的随机数服务。现有的研究工作主要聚焦在熵源熵不足和后处理模块内部状态泄露问题，这是影响SRNG的随机数服务质量的主要问题。为此，设计并实现一种带有熵监控功能的软件随机数发生器（entropy monitoring SRNG，EM-SRNG）架构，该设计利用高精度的纳秒级系统时钟作为非物理熵源。在线的熵监控模块可实现在发生器运行时对未处理数据的熵进行持续检测，并在熵不足的情况下按需调用后处理模块以改善数据的统计特性。另外，EM-SRNG的后处理模块可选用基于SM3和SM4密码算法设计的两种后处理扩展算法，以保证发生器内部状态的前向/后向安全性。通过对所设计的EM-SRNG与Linux随机数发生器（LRNG，目前主流的软件随机数发生器之一）进行对比分析，实验结果表明：在安全性方面，经SP 800-90B测试后发现EM-SRNG的输出质量与LRNG的dev/random提供的数据质量相当，而略好于LRNG的dev/urandom提供的数据质量，每比特的最小熵约为0.94/bit；在速率方面，EM-SRNG的数据产生速率比LRNG的dev/random高4个数量级左右，但由于在结构中嵌入了基于90B统计套件进行在线熵估计，使得EM-SRNG的速率比LRNG的dev/urandom要慢一些，约为4 Mbps。

关键词: 随机数发生器, 熵监控, Linux随机数发生器

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

中图分类号:

刘攀, 陈天宇, 吕娜, 马原, 荆继武. 一种带有熵监控功能的软件随机数发生器[J]. 中国科学院大学学报, 2020, 37(6): 835-847.

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.

参考文献

[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.