Got Entropy ?

So I have been planning a series of podcasts on Cryptographic Controls. In the process of this planning, I fell into one of the classic traps that crypto-geeks fall into: obsessing about random number generators (RNGs).

(FYI, for the impatient, click here.)

There are two ways to generate random numbers on computers: (1) use a software program called a Pseudorandom Number Generator (PRNG) or (2) use a hardware random number generator. A Pseudorandom Number Generator uses a seed value to generate a sequence of numbers that appear random. The problem is that the same seed generates the same random sequence. The hardware based RNG observes and samples some physical phenomenon which is random, such as cosmic rays, RF noise, etc. (aka Entropy).

RNGs are important in Information Security because they are used to generate encryption keys, salts, etc. Historically, attacking RNGs has proven effective, such as the defeat of Netscape’s HTTPS sessions.

Most operating systems utilize a hybrid approach, implementing a PseudoRandom Number Generator that has a seed that is regularly updated through the collection of random hardware events. This process is called Entropy Collection or Entropy Harvesting. For most applications, this approach should be completely sufficient. However, one of the key assumptions is that the operating system has been up and running long enough for the seed value itself to become hard to predict through the collection of Entropy. Also, many of the Entropy collecting events come from properties of hardware devices, such as the minor variations in hard drive rate of rotation. As such, there are a few circumstances where the OS RNG may not be good enough for strong cryptographic key generation:

  • Live Boot CD ( The start state of the RNG may be predictable. )
  • Virtualized Hosts ( OS may be dependent on simulated events for randomness. )

( Given the exploding popularity of virtualization, this is an area worthy of research. Stay tuned. )

Design of the Got Entropy Service

Many RNGs (such as the one included in Linux, as well as OpenSSL’s) allow the addition of entropy from outside sources. So I started looking to Entropy sources I could use to bolster the RNGs on my virtual hosts (and other uses…). While I was looking into this, it occurred to me that I had an unused TV tuner card, a PVR-350.

When a TV is tuned to a channel with no local station, the ‘snow’ on the screen is RF noise (the same as the static between stations on AM radios). But, for reasons beyond our scope, you never use a direct physical observation as the RNG. You have to ‘de-skew and whiten’ the data prior to sampling it. Here is the process that I use:

  1. Collect about 3 minutes of video ( about 130 MB data ).
  2. Using a random key and IV, encrypt the data ( using openssl & AES-128-CBC ).
  3. Discard the first 32k of the file.
  4. Use each of the following 32k blocks as samples.
  5. Compress each sample with SHA-256.
  6. Discard the last block.
  • Steps 2 and 3 remove any patterns, such as MPEG file formatting, from the data.
  • Steps 4 and 5 generate a 32-byte random value ( 1024 to 1 compression in the hash ).

Check it out at http://gotentropy.artofinfosec.com

Can an Attacker Broadcast a Signal to Undermine This?

Such an attacker could not remove RF noise from the received signal. Our eyes and brains are good at filtering out the noise in the TV video, but there is a lot of it. Part of the noise comes from the atmospheric background RF, but there are also flaws (noise) in the tuner’s radio and analog-to-digital capture circuitry.

I think this is a pretty strong RNG, and I have provided an interface for pulling just the values.

Also, I have written a script ( getEntropy.sh ) that will pull Entropy from the service and seed it into /dev/random on Linux.

Results from ENT

Here are results, from a sample run of the Got Entropy, analyzed by ENT ( A Pseudorandom Number Sequence Test Program provided by John Walker of http://www.fourmilab.ch – Thanks, John! ).

  • Entropy = 7.999987 bits per byte
  • Optimum compression would reduce the size of this 13366112 byte file by 0 percent.
  • Chi square distribution for 13366112 samples is 233.85, and randomly would exceed this value 82.48 percent of the time.
  • Arithmetic mean value of data bytes is 127.4767 (127.5 = random).
  • Monte Carlo value for Pi is 3.143054786 (error = 0.05 percent).
  • Serial correlation coefficient is -0.000078 (totally uncorrelated = 0.0).

Resources for the Curious…

Cheers, Erik

2 thoughts on “Got Entropy ?

  1. Bill Ricker

    Don’t try this on an HD-TV channel!

    The claim that TV RF noise is un-attackable doesn’t convince; it can be no stronger than AES’s resistance to a chosen plaintext attack, and could be much weaker. The video signal and tuner is AM not FM, so there is no capture effect (good) but if the transmitted signal is enough stronger than the noise power, the number of bits of noise remaining at the A/D output after Automatic Gain Control (AGC) can be arbitrarily limited.

    Please run your capture and statistical test with the tuner set to a strong nearby TV channel (analog not HD-TV, although Analog mode tuner with HD-TV signal would be interesting too) .

    What effect would using a non-random, non-secret key and IV for the AES step have on entropy dispersion? On attack by jamming? If I beam NTSC equivalent of all-ones on your channel strongly enough, and I know your key and IV and above procedure, your only entropy comes from any quantization errors in the A/D, if any, and dispersion liimiting ability to detect which point capture was initiated?

    If I broadcast a pre-recorded snow-patttern, with proper framing, would you notice?
    If I broadcast deterministic PRNG output, without framing, could i the attacker determine where you started capture except by brute force? With that, how much does the dispersion of quantization errors save you?

  2. Dave S.

    Why not just use a dedicated hardware RNG which uses radioactive decay, generated white noise, or quantum events to generate randomness, if your application is important? There are numerous devices now which have drivers for all OS’es.

Comments are closed.