LETRNG — A Lightweight and Efficient True Random Number Generator for GNU/Linux Systems

Yucong Chen; Fangfang Zhu; Yanshan Tian; Shuaixin Xu; Lihong Han; Qingguo Zhou; Nam Ling

doi:10.26599/TST.2022.9010005

Tsinghua Science and Technology 2023, 28(2): 370-385 https://doi.org/10.26599/TST.2022.9010005

Open Access | Issue | Published: 29 September 2022

LETRNG — A Lightweight and Efficient True Random Number Generator for GNU/Linux Systems

Show Author's Information Hide Author's Information Yucong Chen^{¹^,²}, Fangfang Zhu^², Yanshan Tian^¹, Shuaixin Xu^¹, Lihong Han^¹, Qingguo Zhou^¹(

), Nam Ling^³

1School of Information Science and Engineering, Lanzhou University, Lanzhou 730000, China

2Institute of Modern Physics, Chinese Academy of Sciences, Lanzhou 730000, China

3Department of Computer Science and Engineering, Santa Clara University, Santa Clara, CA 95053 USA

Keywords:

GNU/Linux system, true random number generator, complex system, inherent randomness, non-determinism

Cite this article:

Chen Y, Zhu F, Tian Y, et al. LETRNG — A Lightweight and Efficient True Random Number Generator for GNU/Linux Systems. Tsinghua Science and Technology, 2023, 28(2): 370-385. https://doi.org/10.26599/TST.2022.9010005

Download citation

EndNote(RIS)

BibTeX

733

Views

Downloads

Citations

Crossref

WoS

Scopus

CSCD

Abstract Full text About this article

Abstract

Unpredictable and irreproducible digital keys are required to modulate security-related information in secure communication systems. True random number generators (TRNGs) rather than pseudorandom number generators (PRNGs) are required for the highest level of security. TRNG is a significant component in the digital security realm for extracting unpredictable binary bitstreams. Presently, most TRNGs extract high-quality "noise" from unpredictable physical random phenomena. Thus, these applications must be equipped with external hardware for collecting entropy and converting them into a random digital sequence. This study introduces a lightweight and efficient true random number generator (LETRNG) that uses the inherent randomness of a central processing unit (CPU) and an operating system (OS) as the source of entropy. We then utilize a lightweight post-processing method based on XOR and fair coin operation to generate an unbiased random binary sequence. Evaluations based on two famous test suites (NIST and ENT) show that LETRNG is perfectly capable of generating high-quality random numbers suitable for various GNU/Linux systems.

Full text

Abstract

Full text

Outline

About this article

LETRNG — A Lightweight and Efficient True Random Number Generator for GNU/Linux Systems

Show Author's information Hide Author's Information Yucong Chen^{¹^,²}, Fangfang Zhu^², Yanshan Tian^¹, Shuaixin Xu^¹, Lihong Han^¹, Qingguo Zhou^¹(

), Nam Ling^³

1School of Information Science and Engineering, Lanzhou University, Lanzhou 730000, China

2Institute of Modern Physics, Chinese Academy of Sciences, Lanzhou 730000, China

3Department of Computer Science and Engineering, Santa Clara University, Santa Clara, CA 95053 USA

Abstract

Keywords: GNU/Linux system, true random number generator, complex system, inherent randomness, non-determinism

References(52)

[1]

B. Kerrigan and Y. Chen, A study of entropy sources in cloud computers: Random number generation on cloud hosts, in Proc. 6^th Int. Conf. on Mathematical Methods, Models and Architectures for Computer Network Security, St. Petersburg, Russia, 2012, pp. 286–298.

DOI Google Scholar

[2]

F. Goichon, C. Lauradoux, G. Salagnac, and T. Vuillemin, Entropy transfers in the Linux random number generator, HAL preprint HAL Id: 1409.4842, 2014.

Google Scholar

[3]

L. Sumter, Cloud computing: Security risk, in Proc. 48^th Ann. Southeast Regional Conf., Oxford, MS, USA, 2010, p. 112.

DOI Google Scholar

[4]

M. Mowbray and S. Pearson, A client-based privacy manager for cloud computing, in Proc. 4^th Int. ICST Conf. on communication System software and middleware, Dublin, Ireland, 2009, p. 5.

DOI Google Scholar

[5]

D. Lin and A. Squicciarini, Data protection models for service provisioning in the cloud. in Proc. 15^th ACM Symp. on Access Control Models and Technologies, Pittsburgh, PA, USA, 2010, pp. 183–192.

DOI Google Scholar

[6]

C. Yuan, Y. Zhong, and S. Yang, Composite chaotic pseudo-random sequence encryption algorithm for compressed video, Tsinghua Science and Technology, vol. 9, no. 2, pp. 234–241, 2004.

Google Scholar

[7]

G. Zhong, K. Xiong, Z. Zhong, and B. Ai, Internet of things for high-speed railways, Intelligent and Converged Networks, vol. 2, no. 2, pp. 115–132, 2021.

DOI Google Scholar

[8]

X. Wang, X. Qin, and L. Teng, A novel true random number generator based on mouse movement and a one-dimensional chaotic map, Mathem. Probl. Eng., vol. 2012, p. 931802, 2012.

DOI Google Scholar

[9]

K. Wallace, K. Moran, E. Novak, G. Zhou, and K. Sun, Toward sensor-based random number generation for mobile and IoT devices, IEEE Internet Things J., vol. 3, no. 6, pp. 1189–1201, 2016.

DOI Google Scholar

[10]

Z. Gutterman, B. Pinkas, and T. Reinman, Analysis of the Linux random number generator, in Proc. 2006 IEEE Symp. on Security and Privacy, Berkeley/Oakland, CA, USA, 2006, pp. 371–385.

DOI Google Scholar

[11]

T. Suzuki and M. Kaminaga, A true random number generator method embedded in wireless communication systems, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., vol. E103.A, no. 4, pp. 686–694, 2020.

DOI Google Scholar

[12]

V. Fischer and M. Drutarovský, True random number generator embedded in reconfigurable hardware, in Proc. 4^th Int. Workshop on Cryptographic Hardware and Embedded Systems, Redwood Shores, CA, USA, 2002, pp. 415–430.

DOI Google Scholar

[13]

M. Bucci and R. Luzzi, Design of testable random bit generators, in Proc. 7^th Int. Workshop on Cryptographic Hardware and Embedded Systems, Edinburgh, UK, 2005, pp. 147–156.

DOI Google Scholar

[14]

I. T. Chen, Random numbers generated from audio and video sources. Mathem. Probl. Eng., vol. 2013, p. 285373, 2013.

DOI Google Scholar

[15]

S. Poli, S. Callegari, R. Rovatti, and G. Setti, Post-processing of data generated by a chaotic pipelined ADC for the robust generation of perfectly random bitstreams, in Proc. 2004 Int. Symp. on Circuits and Systems, Vancouver, Canada, 2004, p. IV–585.

Google Scholar

[16]

Y. Ma, T. Chen, J. Lin, J. Yang, and J. Jing, Entropy estimation for ADC sampling-based true random number generators, IEEE Trans. Inf. Forensics Secur., vol. 14, no. 11, pp. 2887–2900, 2019.

DOI Google Scholar

[17]

E. Fatemi-Behbahani, K. Ansari-Asl, and E. Farshidi, A new approach to analysis and design of chaos-based random number generators using algorithmic converter, Circuits Syst. Signal Process., vol. 35, no. 11, pp. 3830–3846, 2016.

DOI Google Scholar

[18]

Y. Dodis, D. Pointcheval, S. Ruhault, D. Vergnaud, and D. Wichs, Security analysis of pseudo-random number generators with input: /dev/random is not robust. in Proc. 2013 ACM SIGSAC Conf. on Computer & Communications Security, Berlin, Germany, 2013, pp. 647–658.

DOI Google Scholar

[19]

A. Colesa, R. Tudoran, and S. Banescu, Software random number generation based on race conditions, in Proc. 2008 10^th Int. Symp. on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania, 2008, pp. 439–444.

DOI Google Scholar

[20]

G. Souaki and K. Halim, Random number generation based on MCU sources for IoT application. in Proc. 2017 Int. Conf. on Advanced Technologies for Signal and Image Processing (ATSIP), Fez, Morocco, 2017, pp. 1–6.

DOI Google Scholar

[21]

D. Davis, R. Ihaka, and P. Fenstermacher, Cryptographic randomness from air turbulence in disk drives, in Proc. 14^th Annu. Int. Cryptology Conf. on Advances in Cryptology, Santa Barbara, CA, USA, 1994, pp. 114–120.

DOI Google Scholar

[22]

P. Lacharme, Post-processing functions for a biased physical random number generator, in Proc. 15^th Int. Workshop on Fast Software Encryption, Lausanne, Switzerland, 2008, pp. 334–342.

DOI Google Scholar

[23]

J. S. Teh, W. Teng, A. Samsudin, and J. Chen, A post-processing method for true random number generators based on hyperchaos with applications in audio-based generators, Front. Comput. Sci., vol. 14, no. 6, p. 146405, 2020.

DOI Google Scholar

[24]

V. Rožić and I. Verbauwhede, Hardware-efficient post-processing architectures for true random number generators, IEEE Trans. Circuits Syst. II Express Briefs, vol. 66, no. 7, pp. 1242–1246, 2019.

DOI Google Scholar

[25]

L. Gantel, A. Duc, L. Steiner, F. Vannel, A. Upegui, and F. Gluck, A FPGA-based post-processing and validation platform for random number generators, in Proc. 2020 IEEE Int. Parallel and Distributed Processing Symp. Workshops, New Orleans, LA, USA, 2020, pp. 123–126.

DOI Google Scholar

[26]

M. Davis and S. Niphadkar, LibMTPRNG: A multithreaded pseudo random number generator, https://www.drdobbs.com/parallel/libmtprng-a-multithreaded-pseudo-random/216900024.

[27]

J. B. Lacy, Cryptolib: Cryptography in software, in Proc. 4^thUSENIX UNIX Security Symp., Santa Clara, CA, USA, 1993.

Google Scholar

[28]

S. Müller, CPU time jitter based non-physical true random number generator, https://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html, 2013.

[29]

N. Mc Guire, Principles and implementation of esrngs – embarrassingly simple random number generators for gnu/Linux, presented at the (4th Real-Time Linex Workshop, Chapel Hill, NC, USA, 2012, p. 26.

[30]

A. Alkassar, T. Nicolay, and M. Rohe. Obtaining true-random binary numbers from a weak radioactive source. in Proc. Int. Conf. on Computational Science and its Applications, Singapore, 2005, pp. 634–646.

DOI Google Scholar

[31]

J. Ladyman, J. Lambert, and K. Wiesner, What is a complex system? Eur. J. Phil. Sci., vol. 3, no. 1, pp. 33–67, 2013.

DOI Google Scholar

[32]

N. Mc Guire, P. Okech, and G. Schiesser, Analysis of inherent randomness of the Linux kernel, presented at the 11^th Real-Time Linux Workshop, Dresden, Germany, 2009, p. 41.

Google Scholar

[33]

V. M. Weaver, D. Terpstra, and S. Moore, Non-determinism and overcount on modern hardware performance counter implementations, in Proc. 2013 IEEE Int. Symp. on Performance Analysis of Systems and Software, Austin, TX, USA, 2013, pp. 215–224.

DOI Google Scholar

[34]

J. Hughes and J. O’Donnell, Expressing and reasoning about non-deterministic functional programs, in Proc. 1989 Glasgow Workshop on Functional Programming, Fraserburgh, Scotland, 1989, pp. 308–328.

DOI Google Scholar

[35]

M. Hocko and T. Kalibera. Reducing performance non-determinism via cache-aware page allocation strategies. in Proc. 1^st Joint WOSP/SIPEW Int. Conf. on Performance Engineering, San Jose, CA, USA, 2010, pp. 223–234.

DOI Google Scholar

[36]

R. J. Wysocki, CPU performance scaling, https://www. kernel.org/doc/html/v5.4/admin-guide/pm/cpufreq.html, 2017.

[37]

B. A. Nejmeh, NPATH: A measure of execution path complexity and its applications, Commun. ACM, vol. 31, no. 2, pp. 188–200, 1988.

DOI Google Scholar

[38]

P. Okech, N. M. Guire, and W. Okelo-Odongo, Inherent diversity in replicated architectures, arXiv preprint arXiv: 1510.02086, 2015.

Google Scholar

[39]

P. Okech, N. McGuire, and C. Fetzer, Investigating execution path non-determinism in the Linux kernel, presented at 15^th Real Time Linux Workshop, Lugano-Manno, Switzerland, 2013, p. 15.

Google Scholar

[40]

S. Goswami, An introduction to kprobes, https://lwn.net/Articles/132196/, 2005.

[41]

L. Wang, C. Zhang, Z. Wu, N. Mc Guire, and Q. Zhou, SIL4Linux: An attempt to explore Linux satisfying sil4 in some restrictive conditions, presented at 11^th Real-Time Linux Workshop, Dresden, Germany, 2009, p. 28.

Google Scholar

[42]

A. Jbara, A. Matan, and D. G. Feitelson, High-MCC functions in the Linux kernel, Emp. Softw. Eng., vol. 19, no. 5, pp. 1261–1298, 2014.

DOI Google Scholar

[43]

Y. Gao, Z. Zheng, and F. Qin, Analysis of Linux kernel as a complex network, Chaos Solitons Fractals, vol. 69, pp. 246–252, 2014.

DOI Google Scholar

[44]

L. Wang, P. Yu, Z. Wang, C. Yang, and Q. Ye, On the evolution of Linux kernels: A complex network perspective, J. Softw. Evol. Process., vol. 25, no. 5, pp. 439–458, 2013.

DOI Google Scholar

[45]

L. Han, Q. Zhou, J. Zhang, X. Yang, R. Zhou, and J. Tang, Polymorphism and consistency: Complex network based on execution trace of system calls in Linux kernels, Int. J. Mod. Phys. C, vol. 31, no. 9, p. 2050126, 2020.

DOI Google Scholar

[46]

G. Cox, C. Dike, and D. J. Johnston, Intel’s digital random number generator (DRNG). In Proc. 2011 IEEE Hot Chips 23 Symp. (HCS), Stanford, CA, USA, 2011, pp. 1–13.

DOI Google Scholar

[47]

D. E. Eastlake, J. I. Schiller, and Steve Crocker, Randomness Requirements for Security, , 2005.

DOI

[48]

P. Diaconis, S. Holmes, and R. Montgomery, Dynamical bias in the coin toss, SIAM Rev., vol. 49, no. 2, pp. 211–235, 2007.

DOI Google Scholar

[49]

L. E. Bassham, A. L. Rukhin, J. Soto, J. R. Nechvatal, M. E. Smid, E. B. Barker, S. D. Leigh, M. Levenson, M. Vangel, D. L. Banks, et al., Sp 800-22 Rev. 1a. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, Gaithersburg, MD, USA: National Institute of Standards & Technology, 2010.

DOI

[50]

J. Walker, ENT: A pseudorandom number sequence test program, https://www.fourmilab.ch/random/, 2008.

[51]

C. Camara, H. Martín, P. Peris-Lopez, and L. Entrena, A true random number generator based on gait data for the internet of you, IEEE Access, no. 8, pp. 71642–71651, 2020.

DOI Google Scholar

[52]

A. L. Rukhin, J. Soto, J. R. Nechvatal, M. E. Smid, E. B. Barker, S. D. Leigh, M. Levenson, M. Vangel, D. L. Banks, and N. A. Heckert, A statistical test suite for random and pseudorandom number generators for cryptographic applications, , 2010.

DOI

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 15 December 2021

Revised: 20 February 2022

Accepted: 21 February 2022

Published: 29 September 2022

Issue date: April 2023

Copyright

Acknowledgements

The authors would like to thank Nicholas Mc Guire for his thoughtful advices and review. This work was partially supported by National Key R&D Program of China (No. 2020YFC0832500), Fundamental Research Funds for the Central Universities (Nos. lzujbky-2021-sp47, lzujbky-2020-sp02, lzujbky-2019-kb51, and lzujbky-2018-k12), and the National Natural Science Foundation of China (No. 61402210). We also gratefully acknowledge the support of NVIDIA Corporation with the donation of the Jetson-TX1 used for this research.

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).