Biblio

Random numbers are essential for communications security, as they are widely employed as secret keys and other critical parameters of cryptographic algorithms. The Linux random number generator (LRNG) is the most popular open-source software-based random number generator (RNG). The security of LRNG is influenced by the overall design, especially the quality of entropy sources. Therefore, it is necessary to assess and quantify the quality of the entropy sources which contribute the main randomness to RNGs. In this paper, we perform an empirical study on the quality of entropy sources in LRNG with Linux kernel 5.6, and provide the following two findings. We first analyze two important entropy sources: jiffies and cycles, and propose a method to predict jiffies by cycles with high accuracy. The results indicate that, the jiffies can be correctly predicted thus contain almost no entropy in the condition of knowing cycles. The other important finding is the failure of interrupt cycles during system boot. The lower bits of cycles caused by interrupts contain little entropy, which is contrary to our traditional cognition that lower bits have more entropy. We believe these findings are of great significance to improve the efficiency and security of the RNG design on software platforms.

When it comes to cryptographic random number generation, poor understanding of the security requirements and “mythical aura” of black-box statistical testing frequently leads it to be used as a substitute for cryptanalysis. To make things worse, a seemingly standard document, NIST SP 800–22, describes 15 statistical tests and suggests that they can be used to evaluate random and pseudorandom number generators in cryptographic applications. The Chi-nese standard GM/T 0005–2012 describes similar tests. These documents have not aged well. The weakest pseudorandom number generators will easily pass these tests, promoting false confidence in insecure systems. We strongly suggest that SP 800–22 be withdrawn by NIST; we consider it to be not just irrelevant but actively harmful. We illustrate this by discussing the “reference generators” contained in the SP 800–22 document itself. None of these generators are suitable for modern cryptography, yet they pass the tests. For future development, we suggest focusing on stochastic modeling of entropy sources instead of model-free statistical tests. Random bit generators should also be reviewed for potential asymmetric backdoors via trapdoor one-way functions, and for security against quantum computing attacks.

Virtualized environments are widely thought to cause problems for software-based random number generators (RNGs), due to use of virtual machine (VM) snapshots as well as fewer and believed-to-be lower quality entropy sources. Despite this, we are unaware of any published analysis of the security of critical RNGs when running in VMs. We fill this gap, using measurements of Linux's RNG systems (without the aid of hardware RNGs, the most common use case today) on Xen, VMware, and Amazon EC2. Despite CPU cycle counters providing a significant source of entropy, various deficiencies in the design of the Linux RNG makes its first output vulnerable during VM boots and, more critically, makes it suffer from catastrophic reset vulnerabilities. We show cases in which the RNG will output the exact same sequence of bits each time it is resumed from the same snapshot. This can compromise, for example, cryptographic secrets generated after resumption. We explore legacy-compatible countermeasures, as well as a clean-slate solution. The latter is a new RNG called Whirlwind that provides a simpler, more-secure solution for providing system randomness.