Week 1: Getting up to Speed

This summer, I will be working with Adam Norton and Amir Rahmati on the cryptographic randomness project in the SPQR lab. Our primary goal is to identify sources of entropy that provide sufficient randomness for a truly secure cryptographic system, particularly on devices with limited computing power. For the first week, I read five different research papers on cryptographic randomness to get up to speed on the scope of the project. Included below is a brief summary of each paper as well as the major lessons and conclusions that will be helpful to our team.

Mining your Ps and Qs: Detection of Widespread Weak Keys in Network Devices

This paper details a large-scale experiment aiming to examine the security of random number generation in important cryptographic protocols. The study specifically targets TLS and SSH, performing a scan of the entire IPv4 address space to obtain TLS certificates and SSH host keys. The data shows that headless or embedded devices do not generate sufficient entropy for the PRNG in the protocols to create distinct keys. 5.57% of TLS hosts and 9.60% of SSH hosts shared keys with other hosts because of this problem. Furthermore, by exploiting weaknesses in RSA and DSA, the private keys of 0.5% of TLS hosts and 1.06% of SSH hosts could be computed using the public key. One reason embedded devices do not generate sufficient entropy is because they do not have the resources of traditional PCs, which utilize keyboard input, mouse movement, disk accesses, and other data to provide entropy. However, the final component of the experiment exposes a major reason that embedded devices do not generate sufficient entropy. The most popular software package for implementing a PRNG is /dev/urandom. The study finds that this Linux package exhibits a boot-time entropy hole that causes its random number generator to produce deterministic output. In one case, the non-blocking entropy pool which supplies urandom did not get data from the input pool until 66 seconds after boot, even though OpenSSH seeded its PRNG using urandom well before that. The paper provides helpful advice for anyone trying to create a secure embedded device: avoid using factory default keys or certificates, ensure sources of entropy are effective, test cryptographic randomness on the device, and use hardware random number generators whenever possible.

Analysis of the Linux Random Number Generator

 The goal of this paper is to decipher the complex open-source code describing the Linux RNG that supplies /dev/random and /dev/urandom. The operating system collects entropy through mouse movement, keyboard input, specific interrupts, and disk accesses. This entropy is funneled into a 512 byte primary pool in the form of 2 32-bit words. The first word describes the timing of the event in milliseconds and the second word describes the event type. The primary pool provides entropy bits to the secondary and urandom pools, both of which store up to 128 bytes. The secondary pool outputs to /dev/random, which blocks until the entropy counter of the secondary pool is at a sufficient value. The urandom pool outputs to /dev/urandom, which does not block. Complex mathematics is involved in determining the amount of entropy entering each pool and, in turn, incrementing the entropy counter. The study also finds a vulnerability in the forward security of the system due to the fact that output from the pools is calculated after the state of the pool is updated. An algorithm is presented that can compute the five previous states of a pool with a high entropy counter based on the current state with an overhead of 2⁶⁴ using O(1) memory. This issue can be avoided by computing the output before updating the state of the pool. Additionally, the study notes that OpenWRT, a Linux distribution for wireless routers, is much less secure because it lacks strong sources of entropy such as mouse and keyboard input or disk accesses. The only source it uses are network interrupts, which are easily visible to an external adversary. Finally, the paper provides solutions for a denial-of-service attack based on continuous calls to the blocking /dev/random. This can be avoided by creating a quota per user or group on the consumption of random bits.

How to Generate Cryptographically Strong Sequences of Pseudo Random Bits

With the motivation of devising a robust, secure random number generator in mind, this paper starts out with an excellent coin-flipping analogy to define the key concept that randomness is relative to a specific model of computing with a specific amount of computational resources. Basically, an observer with no resources is unable to determine the outcome of a coin flip with greater than 50% success. However, an observer equipped with a computer capable of taking pictures and tracking the motion of the coin and efficiently calculating its speed and momentum may be able to predict the outcome with greater than 50% success. Keeping this in mind, a random number generator proposed which takes as an input a random seed value s and outputs a sequence of pseudo random bits. The bits are polynomially many in the length of s, each bit can be calculated in time polynomial in the length of s, and, given the first k pseudo-random bits not not s, it is computationally infeasible to calculate the k+1^st bit in the sequence with better than 50% success.

When Good Randomness Goes Bad: Virtual Machine Reset Vulnerabilities and Hedging Deployed Cryptography

There are two different components to this paper. The first is a case study on the nature of snapshots used in virtual machines to reset the state of the system and the security vulnerabilities that arise due to this technique. This study has significant implications because VM managers such as VMWare and VirtualBox are used at the consumer and business level to efficiently manage computing infrastructure and the increasingly popular cloud computing relies on these management services as well. The study found that if a client runs multiple times from the same full reset snapshot, it may end up sending the same premaster secret value required for the RSA protocol to different servers. In terms of TLS servers, a vulnerability arises if multiple servers are run from the same snapshot. If a snapshot of the server was taken after startup, it would save the state of the RNG based on the boot-time seed value. Reuse of that state would lead to multiple servers using the same randomness in DSA. Fixing this vulnerability requires ensuring that the RNG gets sufficient entropy after the snapshot and that OS sources such as /dev/random and /dev/urandom generate randomness immediately preceding the cryptographic operation. The second part of the paper explores the idea of hedging currently deployed cryptography to safeguard against bad randomness and therefore mitigate the risk of RNG failures. The proposed hedging framework preprocesses RNG-derived randomness with other inputs such as mouse and keyboard events to create pseudo randomness for cryptographic operations with very little overhead. The framework can be applied to the OpenSSL code base, which is the cryptographic library for the TLS protocol.

A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications

In the introduction, this paper explains the important difference between random number generators and pseudo random number generators. RNGs use an entropy source to create randomness. On the other hand, PRNGs use random, unpredictable seed values as inputs to generate multiple “pseudorandom” numbers. Therefore, by default, a PRNG requires an RNG to operate off a seed value. The paper then presents a statistical suite of 15 tests to determine whether RNGs and PRNGs produce sufficient randomness. The first test examines a sequence of random bits and assesses the closeness of the fraction of ones to ½ to determine whether the number of ones and zeros is approximately the same as what would be expected in a truly random sequence. The next 14 tests depend on whether this first one passes. The next test checks the proportion of ones within M-bit blocks. For block size M=1, this test is the same as the first test. Another test focuses on the number of runs in the sequence, where a run is defined as an uninterrupted sequence of identical bits. This test determines whether the oscillation between zeros and ones is too fast or too slow. Other tests utilize mathematical techniques such as discrete Fourier transforms, template matching, and Maurer’s test.