True random numbers
from Wi-Fi background noise

Pars Mutaf
February'06
Paris, FR.

Abstract

A novel hardware random number generator is introduced. Its randomness source is the Wi-Fi background noise. The C code is explained and made available for download. [sweet! show me the code]
This code was written and tested while visiting La Maison du Bonheur, near Grenoble, between October'05 and January'06. I would like to thank (in alphabetical order):
Mikael (Mike) Bertolini, Annabelle (Annalilou) Bourelle, Pamela (Pimpampoum) Bourelle, Guillaume (Guillaume) Daniel, Benoit (Ben) Laurent, Olivier (Oliv) Meunier, Philippe et Veronique Perrier (Phil et Vero).

Introduction

Any computer engineer knows it. High quality random numbers are difficult (if not impossible) to generate using arithmetic methods in computer. For high quality random numbers, a hardware Random Number Generator (hardware RNG) is needed. Hardware RNGs do not use any arithmetic methods, they use input from physical phenomena which are "naturally" random. True random numbers are, for example, recommended for security, i.e. key generation (see RFC 4086). Another example is Optimistic Duplicate Address Detection (in IPv6). It requires high quality random numbers.

I have been experimenting with a new hardware RNG based on Wi-Fi background noise. Wi-Fi (also known as WLAN, Wireless LAN, or IEEE 802.11) devices measure the background noise in their environment. Electromagnetic noise is a physical phenomena, and hence it (its shape and its variations) should be random, in theory. Using standard Wi-Fi hardware and software, today, the noise level information is accessible to the user. No special hardware is needed. You only need an association with a standard access point (infrastructure mode, or "managed mode" in Linux jargon). The ad hoc mode will be studied later.

In Linux, the character special device /dev/random already provides high quality random numbers. Why bother with an alternative solution? Because, the /dev/random device's entropy sources are the keyboard, mouse pointer, and hard drive (see the theory of operation and C code by Theodore Ts'o). These entropy sources may not be available on handheld or even smaller devices which are, however, likely to be equipped with a wireless interface e.g. Wi-Fi.

HARDWARE & SOFTWARE THAT I USED

  • Laptop computer
  • Linux
  • Wireless extensions and wireless tools (this should be available by default)
  • Intel PRO/Wireless 2200BG
  • Intel PRO/Wireless 2200BG Driver

    • Theory of operation

    Try the iwconfig command (from wireless tools package) on your Wi-Fi equipped computer associated with an access point (managed mode). You should see something like: 
     
      pars@lazylizard:~$ iwconfig
      lo        no wireless extensions.
      
      eth1      no wireless extensions.
      
      eth0      IEEE 802.11g  ESSID:"lepassager"
                Mode:Managed  Frequency:2.462 GHz  Access Point: 00:0F:66:D9:DE:14
                Bit Rate=5.5 Mb/s   Tx-Power=20 dBm
                Retry limit:7   RTS thr:off   Fragment thr:off
                Power Management:off
                Link Quality=55/100  Signal level=-68 dBm  Noise level=-83 dBm
                Rx invalid nwid:0  Rx invalid crypt:0  Rx invalid frag:0
                Tx excessive retries:96  Invalid misc:1   Missed beacon:1

      sit0      no wireless extensions.

      pars@lazylizard:~$
    Some Wi-Fi cards will report "zero" noise level. This is wrong. It is never zero. If you are lucky and you do not have one of those cards, you should see a very small noise level (this is my case as shown above). If so, repeat the iwrandom command and observe how the noise level changes. It is hard to predict "when" it will change. The variations look random (see the initial test results below). The iwconfig command reads /proc/net/wireless to get this information. Here is a snapshot: 
          pars@lazylizard:~$ cat /proc/net/wireless      
      Inter-| sta-|   Quality        |   Discarded packets               | Missed
       face | tus | link level noise |  nwid  crypt   frag  retry   misc | beacon
        eth0: 0000   64.  194.  172.       0      0      0     78      0        0
      pars@lazylizard:~$
    Here we see the signal and noise levels (and many other information that are off topic here). These are reported in unsigned dBm (decibel milliwatt), i.e. dBm+256. Consequently, in the above example 172 corresponds to -84 dBm, or 10-8.4 milliwatt of background noise.

    To generate random bits, I wrote a C code and called it iwrandom.c (available below for download). Here is how it works (illustrated on the left):

    The noise value, itself, does not contain enough entropy to generate random bits. In general, it takes similar values around the average noise level. In iwrandom, the random bits are therefore extracted from noise level variations.

    For this, iwrandom uses the "CounTer" variable (see the code). The noise level is frequently extracted from /proc/net/wireless (here frequently means "as fast as possible"). If the noise level has not changed, CounTer is incremented. When a change is detected, the least significant bit(s) of CounTer is(are) saved. These are the random bits. At this point CounTer is reset. The same procedure is repeated to generate other random bits.

    Downloading and using the code

    You can download the C code here. Compile it as follows: 
          gcc iwrandom.c -o iwrandom
    This will generate the iwrandom file in your current directory. This is the executable file. Type 
          ./iwrandom
    This will generate the following message:

          pars@lazylizard:~/Desktop/iwrandom$ ./iwrandom
      
      Usage: iwrandom -n NUMBER -s SPEED -o FILE
      (where, NUMBER>0, SPEED>0 and top speed is the 8th.)
      Recommended speed is the 2nd speed.
      
      Example command:
             iwrandom -n 1024 -s 2 -o result
      
      pars@lazylizard:~/Desktop/iwrandom$
    Here NUMBER is the number of random bytes that you want to generate. FILE is the name of the output file where the random bytes will be written.

    SPEED is the speed factor for random number generation. It has no unit. It is rather like: 1st speed, 2nd speed, 3rd speed etc. It multiplies the random number generation speed by a factor or your choice. As described above, whenever a noise level change is detected, a number of random bits are taken from the CounTer variable, and CounTer is reset to zero. The speed option determines the number of random bits taken from CounTer (starting from the least significant bit). For example if you select the first speed (-s 1) only the least significant bit of CounTer will be taken for random number generation. The remaining 7 bits will be thrown away. If you select the second speed (-s 2) the two least significant bits of CounTer will be taken, etc. Clearly, the greater the speed value, the faster the random numbers will be generated. Because, a smaller number of bits will be thrown away.

    However, care should be taken. AT HIGH SPEEDS, RANDOMNESS CAN BE LOST. This is probably because the noise level, sometimes, changes frequently. Therefore, the leftmost bits of CounTer may sometimes be "non-randomly zero". Be careful with the SPEED option. High speeds are for experimenting.

    ENT test results

    The randomness testing software that I have been using is called ENT, written by John Walker, and available here. Here is an example ENT result produced with iwrandom: 
    
pars@lazylizard:~/Desktop/iwrandom/RESULTIWRANDOM$ ent result
Entropy = 7.976640 bits per byte.

Optimum compression would reduce the size
of this 8192 byte file by 0 percent.

Chi square distribution for 8192 samples is 263.81, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 126.4719 (127.5 = random).
Monte Carlo value for Pi is 3.117948718 (error 0.75 percent).
Serial correlation coefficient is -0.012639 (totally uncorrelated = 0.0).
pars@lazylizard:~/Desktop/iwrandom/RESULTIWRANDOM$
    In the above example, ENT is applied to the 8192-byte (8K) file "result" produced with iwrandom. ENT performs six different tests. It measures the entropy per byte (ideally 8 bits), compressibility (ideally 0%), performs a Chi square test (ideally 50.00%), calculates the arithmetic mean value (ideally 127.5), the Monte Carlo value for Pi (ideally equals Pi) and the serial correlation coefficient (ideally 0).

    Here are 10 results obtained with iwrandom (at 2nd speed) and 10 results obtained with /dev/random:

    FILE Size Entropy Comp ChiSqr Mean Pierr Scc
    iwrandom-s2-r1 8192 7.976640 0% 50.00% 126.4719 0.75% -0.012639
    iwrandom-s2-r2 8192 7.977084 0% 50.00% 127.0900 1.13% -0.014197
    iwrandom-s2-r3 8192 7.977875 0% 50.00% 127.9049 0.55 % 0.005516
    iwrandom-s2-r4 8192 7.975658 0% 25.00% 127.4629 1.21% -0.003286
    iwrandom-s2-r5 8192 7.974438 0% 10.00% 127.4209 2.43% -0.016758
    iwrandom-s2-r6 8192 7.977012 0% 50.00% 127.7972 1.86% 0.001800
    iwrandom-s2-r7 8192 7.981149 0% 95.00% 126.6578 1.30% 0.003421
    iwrandom-s2-r8 8192 7.978407 0% 50.00% 127.4510 2.33% -0.001519
    iwrandom-s2-r9 8192 7.974169 0% 10.00% 127.8157 0.18 % -0.021584
    iwrandom-s2-r10 8192 7.977851 0% 50.00 % 127.6062 2.51% -0.002849

    FILE Size Entropy Comp ChiSqr Mean Pierr Scc
    devrandom-r1 8192 7.973796 0% 5.00% 127.3165 0.74% 0.005814
    devrandom-r2 8192 7.981868 0% 99.00% 127.4762 0.55% 0.010902
    devrandom-r3 8192 7.979595 0% 75.00% 127.4924 1.78% -0.009067
    devrandom-r4 8192 7.976297 0% 50.00% 127.2339 0.46% -0.014335
    devrandom-r5 8192 7.980761 0% 95.00% 126.2734 0.83% 0.022369
    devrandom-r6 8192 7.976833 0% 50.00% 127.4653 1.39% 0.008806
    devrandom-r7 8192 7.978933 0% 75.00% 127.4277 1.39% 0.023459
    devrandom-r8 8192 7.976584 0% 50.00% 127.3192 0.55% 0.007596
    devrandom-r9 8192 7.976848 0% 50.00% 128.2788 1.97% 0.017584
    devrandom-r10 8192 7.976315 0% 25.00% 127.8433 0.75% 0.008954

    It can be noted that iwrandom and /dev/random produce similar results. For more interpretation of the results check here. The most difficult test to pass the Chi square test. Quoting John Walker, "If the percentage is greater than 99% or less than 1%, the sequence is almost certainly not random. If the percentage is between 99% and 95% or between 1% and 5%, the sequence is suspect. Percentages between 90% and 95% and 5% and 10% indicate the sequence is almost suspect."

    iwrandom successfully passed the chi square test. Below is an ENT test result produced with larger, 80122 byte, random data generated with iwrandom. The result is promising. 

    pars@lazylizard:~/Desktop/iwrandom$ ent iwrandom-s2-rBIG
Entropy = 7.997535 bits per byte.

Optimum compression would reduce the size
of this 80122 byte file by 0 percent.

Chi square distribution for 80122 samples is 272.23, and randomly
would exceed this value 25.00 percent of the times.

Arithmetic mean value of data bytes is 127.8388 (127.5 = random).
Monte Carlo value for Pi is 3.152549989 (error 0.35 percent).
Serial correlation coefficient is -0.000224 (totally uncorrelated = 0.0).
pars@lazylizard:~/Desktop/iwrandom$

    These files are available on demand.

    For further comparison, you can also check the ENT results obtained by the random.org team. Their randomness source is the atmospheric noise from a radio. Note that this technique is similar to that of iwrandom. However, with iwrandom no special hardware is needed. It uses commodity Wi-Fi equipment.

    That's all folks!

    Questions, comments... Feel free to send e-mail to iwrandom@gmail.com.

    When you execute the iwrandom command, you should see something like: 

    pars@lazylizard:~/Desktop/iwrandom$ ./iwrandom -n 10 -s 2 -o result

Creating output file 'result'... OK.
Checking "/proc/net/wireless"... OK.
Checking noise level variations... OK.

Generating random numbers (2nd speed):
<00001011> 1 of 10 bytes OK.
<00111010> 2 of 10 bytes OK.
<10111100> 3 of 10 bytes OK.
<11101011> 4 of 10 bytes OK.
<11011110> 5 of 10 bytes OK.
<00010111> 6 of 10 bytes OK.
<11101010> 7 of 10 bytes OK.
<11001111> 8 of 10 bytes OK.
<00000111> 9 of 10 bytes OK.
<01100010> 10 of 10 bytes OK.
Generated 0.7 bytes per second on the average.

pars@lazylizard:~/Desktop/iwrandom$
    The program first checks the presence of /proc/net/wireless, where the noise values will be read. If this fails, you probably do not have wireless tools. Next, noise levels variations are checked. The program will block until a change is detected. As described above, iwrandom is based on noise level variations. If, for some reason, the noise level does not change, the program will block. You can exit with Ctrl-C, in this case. The noise level may be constant (or, zero), if for example your Wi-Fi device, or driver does not report low noise levels. If you think that this is your case, please tell me which Wi-Fi hardware and driver you are using. Or, there may be a bug in my parsing code, and it fails to read /proc/net/wireless on your system correctly, for some reason that I could not foresee! Please tell me in this case.