Not-So-Random Numbers

This page includes data, scripts, and tools that were used to derive the results in the paper Not-So-Random Numbers in Virtualized Linux and the Whirlwind RNG.

View presentation

Background

To study the workings of the Linux RNGs, /dev/(u)random and get_random_int, we added instrumentation to the Linux kernel to capture inputs and outputs and record internal events. Since disk events trigger yet more inputs into the Linux RNG, we determined that using the standard kernel logging facility printk would do more harm than good since our logs were very large.

Instead, we decided to record all of our log information in kernel memory using a logging mechanism we call the data-recorder. Once an experiment is complete (or the data-recorder memory is full), we transfer the logs from kernel memory to disk by reading from a special device: /dev/data_recorder.

Full kernel source

You can download the full source of the kernel we studied (Linux kernel v3.2.35), with instrumentation in-place here.

Download iRNG

Background

We ported the Linux kernel's RNG /dev/(u)random into a userspace simulator in order to validate our instrumentation and also to experiment with the implementation.

/dev/(u)random simulator (git)

You can get our /dev/(u)random simulator from our public git repository using the following command:

git clone https://bitbucket.org/ace0/linux-devrand-simulator.git

Visit Repo

Download the data and tools we used to derive results that appear in the paper from our public git repository hosted at BitBucket.org.

git clone https://bitbucket.org/ace0/not-so-random-analysis.git

Visit Repo

Requirements

Our analyses were conducted with tools written in bash, C, standard Linux tools, and python v2.6.6. Some python scripts require the python packages scipy and numpy.

Tools

The tools directory contains simple tools (written in C) that interact the Linux RNG. This include the detect-reset tool that can detect a snapshot resumption on a virtual machine with a non-virtualized cycle counter and will sample RNG outputs after detecting a resumption.

Full Datasets

One of our primary sources of data are traces of the Linux RNG collected by booting our instrumented kernel on various platforms. We also collected a large number of outputs from the RNG after resuming from snapshots.

The full set of experimental data is very large (over 10GB). For ease-of-donwload, these data are not included in full in the git repo listed above. Instead, they can be downloaded as a single archive using the button below.

Download Full Dataset

Entropy Estimation

In order to estimate the security of outputs from the Linux RNG, we developed an estimation method that uses statistical hypothesis testing as a heuristic to estimate the entropy in inputs to the RNG. The entropy-estimation directory contains scripts, data, and results used to estimate the security of the Linux RNG and the Whirlwind RNG on a variety of virtual platforms: Xen, VMware, and Amazon's EC2.

Liunx penguin logo

Linux RNG Repeats

Under specific conditions, the Linux RNG generates repeat outputs when reset multiple times from the same full-memory snapshot on Xen and VMware. The linux-rng-repeats directory in the git repository contains repeats that we observed under various conditions on each platform.

Windows 7 Logo

Windows 7 has multiple interfaces for generating secure random numbers: rand_s, CryptGenRandom, and RngCryptoServices. All three interfaces will generate repeat outputs when a process is launched before a snapshot is taken and the snapshot is used more than once.

The windows-rng-repeats directory in the repository above contains RNG outputs collected during our experiments as well as source code built with Microsoft's (free) IDE Visual Studio Express.

The FreeBSD RNG is accessed through the virtual devices /dev/random and /dev/urandom. (The interfaces are identical; /dev/urandom exists only for compatibility with Linux). As with Linux and Windows 7, FreeBSD generates a repeated output stream with each resumption from the same snapshot. The repeated output stream continues until the RNG has received enough new inputs to trigger a re-key of the output generation routine (which uses AES in CTR mode).

The freebsd-rng-repeats directory in the repository above contains our observations of the FreeBSD RNG after resuming from a snapshot multiple times.

FreeBSD Beastie Logo