Random Notes

From Noah.org
Jump to navigationJump to search


Random Notes

This is not a collection of random notes. This is a collection of notes about random numbers.

/dev/random and /dev/urandom

The file /dev/random is the direct interface to the Linux kernel entropy pool and cause reads to block when the entropy pool is empty. The file /dev/urandom is an unblocked interface to the entropy pool. It will reuse the entropy if it runs out. It does blend this through a pseudorandom number generator, so you shouldn't actually see repeated patterns in the numbers; however, these numbers are not considered as random the numbers from /dev/random. This random source may not be as secure for software that depends on random numbers for security.

/dev/random is a limited resource

The device /dev/random is better, but it is "slow" because it depends on a limited resource. It reads directly from the Linux kernel entropy pool to give you truly random numbers. The entropy pool generates truly random numbers by sampling data from the environment such as clock drift and timing of input from device drivers. This sampled data is blended and tested to ensure that it is truly random and without bias. This is an expensive operation, so the kernel constantly maintains a pool (cache) of random numbers which can be read from /dev/random. The problem is that once you have read all the random numbers from the pool further read operations must block until the kernel writes more random numbers into the pool. You see just how slow this is by running the following command:

dd if=/dev/random bs=1 | od -x

You should see a bunch of random hex digits dumped after which `dd` will block and then slowly print new random numbers as the pool gets filled. You may notice that if you move your mouse a lot that new random numbers will be printed more quickly. This shows that the kernel gets some of its environmental input from the mouse device driver.

You can see how many random bytes are in the pool by looking at the file /proc/sys/kernel/random/entropy_avail. If you watch this file (`watch -n 1 cat /proc/sys/kernel/random/entropy_avail`) you may see that the number goes up and down. This is because various services running in the background and even kernel device drivers also read from the entropy pool. In particular, services that use SSL will deplete the entropy pool. If you "waste" the entropy pool by running `dd if=/dev/random bs=1 | od -x` then you may slow down these services because they much block until more entropy is available. Also, if you have many processes running which all use SSL then they may slow each other down. The CPU load will be load, but load average will go up as more processes are forced to block waiting for more entropy.

One way to increase the speed of the supply to the entropy pool is to use a dedicated hardware random number generator. These devices provide a good entropy source much more quickly than what the kernel can obtain from the environment. The Ubuntu package rng-tools can be used to setup and control sources of entropy.

Another way to increase the speed of the supply to the entropy pool is to hack the kernel entropy pool to make it less random (less good). In general, you should not notice the difference, but be aware that you may compromise secure applications such as web services and anything that accepts SSL connections. This doesn't create a huge back door into these applications, but if you are dealing with valuable sensitive data then you shouldn't be playing around with mathematics that you do not understand. In other words, if lives, money, or your job is at stake then get a real hardware random number generator... To hack the kernel entropy pool you must install rng-tools. Then edit /etc/default/rng-tools and edit or insert a line for HRNGDEVICE to the following:

HRNGDEVICE=/dev/urandom

Finally, restart the `rngd` daemon:

sudo service rng-tools restart
 # or
sudo /etc/init.d/rng-tools restart

Doing this basically bypasses /dev/random with data from /dev/urandom. You can now read as much data from /dev/random as you want without blocking. Remember, this is a horrible thing to do. It will make security and statistics nerds go into a rage. I only show this because it is a good learning experience.

testing random numbers for randomness

There are a few Ubuntu packages which provide tools for testing the quality of random number generators. rng-tools, ent, and dieharder. The openssl command is also useful for testing.

sudo aptitude install ent rng-tools dieharder

generate test data

Both dieharder and openssl can be used to generate pseudorandom numbers. I use opensll to generate pseudorandom numbers. The following generates a 1 GB file named "entropy.bin". This uses the password 1234567890 as the seed.

dd if=/dev/zero bs=1000000 count=1000 | openssl aes-256-cbc -e -pass pass:1234567890 -out entropy.bin
cat entropy.bin | rngtest

The output can also be fed directly to a random number tester:

dd if=/dev/zero bs=1000000 count=1000 | openssl aes-256-cbc -e -pass pass:1234567890 | rngtest

Note that 1 GB is insufficient for dieharder. It needs over 100 GB of data for testing, so it's better to feed the output of openssl directly to dieharder.

cat /dev/zero | openssl aes-256-cbc -e -pass pass:1234567890 | dieharder -a -g 200

You should find that aes-256-cbc is a very good random number generator. It should be since AES is the state of the art for block ciphers. The down-side of using it as a pseudorandom number generator is that it is slow compared to a dedicated PRNG such as Mersenne Twister MT19937. You can compare the timing as follows:

time cat /dev/zero | openssl aes-256-cbc -e -pass pass:1234567890 | dieharder -a -g 200
time dieharder -a -g 13

Both give excellent results, but Mersenne Twister MT19937 (-g 13) is about twice as fast as OpenSSL aes-256-cbc (MT19937: 1049 s, OpenSSL aes-256-cbc: 2127 s).

ent

The ent testing tool is easy to use. Interpreting these values is beyond the scope of this introduction.

dd if=/dev/urandom bs=1 count=1000000 | ent

rngtest in rng-tools

The rngtest utility will test a given stream against the FIPS 140-2 randomness tests. It is very easy to use and the results are fairly easy to read. It operates on blocks of 20000 bits at a time. After testing a report is printed showing the number of blocks that successfully passed or failed a given test. Note that if you test a large number of blocks that you should expect a few failures.

cat entropy.bin | rngtest

If you have a limitless random number source then you might want to display statistics after a given number of bits have been tested. The rngtest tool tests blocks of 20000 bits at a time. It throws away the first 32 bits of any input stream. The following will test /dev/urandom forever and print statistics every 10000 blocks (200000032 bits, or about 25 MB).

cat /dev/urandom | rngtest -b 10000

dieharder

Dieharder is both a random number generator and a RNG tester. It contains a large number of tests and RNG algorithms to test against. Dieharder requires lots of sample data for testing. The tests take a long time to run. For testing a file of random bytes I use the following command:

cat entropy.bin | dieharder -a -g 200

The -a option selects all tests. The -g NNN option selects a random number source. In the first example below -g 200 selects raw binary from stdin. Many other random number sources may be selected. Most sources choose internal Dieharder generators. For example, the following two examples are equivalent.

cat /dev/urandom | dieharder -a -g 200
dieharder -a -g 501

Dieharder can be used to test other random number testers by generating random numbers. The following will generate 1 MB of random numbers using algorithm 13 (Mersenne Twister MT19937) with starting seed 0. The Mersenne Twister MT19937 algorithm is a 32-bit generator, so I select 250000 iterations to produce 1 MB.

dieharder -g 13 -S 0 -t 250000 -o -B | rngtest

You can see that selecting a different seed can cause some tests to fail. This is normal. Over a large number of blocks no RNG will always pass every FIPS 140-2 test.

dieharder -g 13 -S 1 -t 250000 -o -B | rngtest

online testing

CAcert has an online testing tool. It requires a minimum of 12 MB of binary data for testing. See http://www.cacert.at/random/

More reading

An old analysis of the Linux Random Number Generator (LRNG) written by Gutterman, Pinkas, and Reinman can be found here: http://eprint.iacr.org/2006/086.pdf

This is a good directory of information about random numbers http://www.cs.berkeley.edu/~daw/rnd/

'Mouse Trap Entropy Generator' -- A truly random number generator

Most natural sources of random numbers, including radioactive decay, have a non-random bias, which may make the numbers unsuitable for many applications. Sources of biased natural randomness can be fed into a randomness extractor to remove bias to generate a stream of more mathematically perfect random numbers. A cryptographically secure pseudo-random number generator (CSPRNG) is often used as a randomness extractor. John von Neumann created one of the earliest randomness extractors.

Common sources of natural random numbers include Geiger counters recording the decay of radioactive elements; electronic amplifiers set to amplify thermal noise; cameras recording lava lamps; and the motion of a computer mouse moved by a human. None of these produce good random numbers without a little bit of extra work.

Here I present a very simple and cheap source of natural random numbers. This source requires almost no tools or expertise besides a screw-driver. What I have done is remove the sensor board from a USB mouse and attach it to the side of an Xmas tree bubble light. The bubbles from the light trigger the motion sensor of the mouse, which is fed into a custom Python program I wrote. In principle this is similar to Lava Lamp random number generators; however, the construction is significantly simpler.

Bubble lights consist of a sealed glass vial filled with Methylene chloride. The bottom of the glass vial is placed against a small incandescent light bulb. The heat from the bulb causes the Methylene chloride to boil and bubble. The bubbles float to the top of the vial where the vapor condenses back into liquid. The extremely low vapor pressure of Methylene chloride allows it to maintain a continuous process of boiling and condensation in a very small tube. The heat of a human hand is enough to drive continuous boiling. Other solvents with low vapor pressures would work, but Methylene chloride has the added advantage that it is relatively non-toxic and it is one of the few volatile solvents which is non-flammable, so it is safe to attach the bubble-lights to a tree, as opposed to hanging tubes of boiling gasoline or acetone on your Xmas tree.

#!/usr/bin/env python
# vim:set ft=python fileencoding=utf-8 sr et ts=4 sw=4 : See help 'modeline'

"""
SYNOPSIS

    entropy-source [-h,--help] [-v,--verbose] [--version] INPUT_DEVICE

DESCRIPTION

    This must be run as root.

    The INPUT_DEVICE must be a file in '/etc/input/', such as
    '/etc/input/event4'. Do not use the '/etc/input/mouse*' devices.

    Note that you may wish to disable the entropy mouse under X11.
    This will not disable it under /dev/input, so it will still
    be a source of entropy.
    First identify which mouse you wish to disable.
        xinput --list
    Next find the ID of the 'Device Enabled' property of the mouse.
        xinput --list-props 16
    Finally, set the 'Device Enabled' property to zero.
        xinput --set-prop 16 145 0

    FIXME: Some of the ioctl command constants are not generated
    in a portable way under Python. To work around this, you can
    compile the following tiny C program which will print out the
    value of the command constants. This should get around any issues
    with word size and endianess.

    #include <stdio.h>
    #include <linux/input.h> 
    int main (int argc, char *argv[]) {
        printf("EVIOCGNAME(255): %u\n", EVIOCGNAME(255));
        printf("EVIOCGBIT(0, 255): %u\n", EVIOCGBIT(0, 255));
        printf("EVIOCGID: %u\n", EVIOCGID);
        printf("EVIOCGVERSION: %u\n", EVIOCGVERSION);
    }

EXAMPLES

    $ sudo ./entropy-source /dev/input/event4 >> entropy-source.bin &
    [1] 4711
    $ sudo ./entropy-source /dev/input/event4 | od -x
    0000000 0bbd b360 4887 5b06 213e 53e3 becc bd08
    0000020 4552 056f 6698 be45 2e67 f78a 43b1 44ee

    The following example will show the raw bits, with bias,
    as they are pulled from the input device. This is useful
    to see how fast the device is generating bits.
    $ sudo ./entropy-source --raw /dev/input/event4
    011000001110010000010001011001100110111011010111101111111
    100000100110011001000101110001000100100101101011011000110

    $ sudo ./entropy-source /dev/input/event4 >> entropy-source.bin &
    $ ./histogram.py entropy-source.bin | egrep -v "^\s*#" | awk '{print $2}' | graph --auto-abscissa 1.0 -r 0.1 -u 0.1 -h 0.8 -w 0.8 --bitmap-size 1024x768 -F HersheySans -T png | display -

EXIT STATUS

    This exits with status 0 on success and 1 otherwise.
    This exits with a status greater than 1 if there was an
    unexpected run-time error.

AUTHOR

    Noah Spurrier <noah@noah.org>

LICENSE

    This license is approved by the OSI and FSF as GPL-compatible.
        http://opensource.org/licenses/isc-license.txt

    Copyright (c) 2012, Noah Spurrier <noah@noah.org>
    PERMISSION TO USE, COPY, MODIFY, AND/OR DISTRIBUTE THIS SOFTWARE FOR ANY
    PURPOSE WITH OR WITHOUT FEE IS HEREBY GRANTED, PROVIDED THAT THE ABOVE
    COPYRIGHT NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES.
    THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
    WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
    MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
    ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
    WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
    ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
    OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

VERSION

    Version 1
"""

import sys
import os
import struct
import time
import fcntl
import time
import traceback
import optparse

# From from pycopia.OS.Linux.IOCTL Keith Dart <keith@kdart.com>
# From ioctl.h
# ioctl command encoding: 32 bits total, command in lower 16 bits,
# size of the parameter structure in the lower 14 bits of the
# upper 16 bits.
# Encoding the size of the parameter structure in the ioctl request
# is useful for catching programs compiled with old versions
# and to avoid overwriting user space outside the user buffer area.
# The highest 2 bits are reserved for indicating the ``access mode''.
# NOTE: This limits the max parameter size to 16kB -1 !
#
# The following is for compatibility across the various Linux
# platforms.  The i386 ioctl numbering scheme doesn't really enforce
# a type field.  De facto, however, the top 8 bits of the lower 16
# bits are indeed used as a type field, so we might just as well make
# this explicit here.  Please be sure to use the decoding macros
# below from now on.
INT = "i"
INT2 = "ii"
INT5 = "iiiii"
SHORT = "h"
USHORT = "H"
SHORT4 = "hhhh"

sizeof = struct.calcsize

_IOC_NRBITS = 8
_IOC_TYPEBITS = 8
_IOC_SIZEBITS = 14
_IOC_DIRBITS = 2
_IOC_NRMASK = ((1 << _IOC_NRBITS)-1)
_IOC_TYPEMASK = ((1 << _IOC_TYPEBITS)-1)
_IOC_SIZEMASK = ((1 << _IOC_SIZEBITS)-1)
_IOC_DIRMASK = ((1 << _IOC_DIRBITS)-1)
_IOC_NRSHIFT = 0
_IOC_TYPESHIFT = (_IOC_NRSHIFT+_IOC_NRBITS)
_IOC_SIZESHIFT = (_IOC_TYPESHIFT+_IOC_TYPEBITS)
_IOC_DIRSHIFT = (_IOC_SIZESHIFT+_IOC_SIZEBITS)
IOCSIZE_MASK = (_IOC_SIZEMASK << _IOC_SIZESHIFT)
IOCSIZE_SHIFT = (_IOC_SIZESHIFT)

# direction bits
_IOC_NONE = 0
_IOC_WRITE = 1
_IOC_READ = 2

def _IOC(dir,type,nr,FMT):

    return int((((dir)  << _IOC_DIRSHIFT) | \
         ((type) << _IOC_TYPESHIFT) | \
         ((nr)   << _IOC_NRSHIFT) | \
         ((FMT) << _IOC_SIZESHIFT)) & 0xffffffff )

# used to create numbers
# type is the assigned type from the kernel developers
# nr is the base ioctl number (defined by driver writer)
# FMT is a struct module format string.
def _IO(type,nr): return _IOC(_IOC_NONE,(type),(nr),0)
def _IOR(type,nr,FMT): return _IOC(_IOC_READ,(type),(nr),sizeof(FMT))
def _IOW(type,nr,FMT): return _IOC(_IOC_WRITE,(type),(nr),sizeof(FMT))
def _IOWR(type,nr,FMT): return _IOC(_IOC_READ|_IOC_WRITE,(type),(nr),sizeof(FMT))

# used to decode ioctl numbers
def _IOC_DIR(nr): return (((nr) >> _IOC_DIRSHIFT) & _IOC_DIRMASK)
def _IOC_TYPE(nr): return (((nr) >> _IOC_TYPESHIFT) & _IOC_TYPEMASK)
def _IOC_NR(nr): return (((nr) >> _IOC_NRSHIFT) & _IOC_NRMASK)
def _IOC_SIZE(nr): return (((nr) >> _IOC_SIZESHIFT) & _IOC_SIZEMASK)

# taken from /usr/include/linux/input.h
EVIOCGVERSION   = _IOR(69, 0x01, INT)           # get driver version
EVIOCGID        = _IOR(69, 0x02, SHORT4)        # get device ID
EVIOCGREP       = _IOR(69, 0x03, INT2)          # get repeat settings
EVIOCSREP       = _IOW(69, 0x03, INT2)          # set repeat settings
EVIOCGKEYCODE   = _IOR(69, 0x04, INT2)          # get keycode
EVIOCSKEYCODE   = _IOW(69, 0x04, INT2)          # set keycode
EVIOCGKEY       = _IOR(69, 0x05, INT2)          # get key value
EVIOCGNAME      = _IOC(_IOC_READ, 69, 0x06, 255)# get device name
EVIOCGPHYS      = _IOC(_IOC_READ, 69, 0x07, 255)# get physical location
EVIOCGUNIQ      = _IOC(_IOC_READ, 69, 0x08, 255)# get unique identifier
EVIOCRMFF       = _IOW(69, 0x81, INT)           # Erase a force effect
EVIOCSGAIN      = _IOW(69, 0x82, USHORT)        # Set overall gain
EVIOCSAUTOCENTER= _IOW(69, 0x83, USHORT)        # Enable or disable auto-centering
EVIOCGEFFECTS   = _IOR(69, 0x84, INT)           # Report number of effects playable at the same time
EVIOCGRAB       = _IOW(69, 0x90, INT)          # Grab/Release device

# these take parameters.
def EVIOCGBIT(evtype, len=255):
    return _IOC(_IOC_READ, 69, 0x20 + evtype, len)  # get event bits
def EVIOCGABS(abs):
    return _IOR(69, 0x40 + abs, INT5)       # get abs value/limits
def EVIOCGSW(len):
    return _IOC(_IOC_READ, 69, 0x1b, len)   # get all switch states
def EVIOCGLED(len):
    return _IOC(_IOC_READ, 69, 0x19, len)   #  get all LEDs

#struct input_event {
#        struct timeval time; = {long seconds, long microseconds}
#        unsigned short type;
#        unsigned short code;
#        unsigned int value;
#};

EVFMT = "llHHi"
EVsize = struct.calcsize(EVFMT)

EV_SYN = 0x00
EV_KEY = 0x01
EV_REL = 0x02
EV_ABS = 0x03
EV_MSC = 0x04
EV_SW = 0x05
EV_LED = 0x11
EV_SND = 0x12
EV_REP = 0x14
EV_FF = 0x15
EV_PWR = 0x16
EV_FF_STATUS = 0x17
EV_MAX = 0x1f
EV_NAMES = {
    EV_SYN: "Sync",
    EV_KEY: "Keys or Buttons",
    EV_REL: "Relative Axes",
    EV_ABS: "Absolute Axes",
    EV_MSC: "Miscellaneous",
    EV_SW: "Switches",
    EV_LED: "Leds",
    EV_SND: "Sound",
    EV_REP: "Repeat",
    EV_FF: "Force Feedback",
    EV_PWR: "Power Management",
    EV_FF_STATUS: "Force Feedback Status",
}

class Event(object):

    """This represents a kernel input event from a device in /dev/input/.
    This stores the event type, time, event code, and event value.
    """

    def __init__(self, time=0.0, evtype=0, code=0, value=0):

        self.time = time # timestamp of the event in Unix time.
        self.evtype = evtype # even type (one of EV_* constants)
        self.code = code     # a code related to the event type
        self.value = value   # custom data - meaning depends on type above

    def __str__(self):

        return "time: %f, evtype: 0x%x, code: 0x%x, value: 0x%x" % \
                    (self.time, self.evtype, self.code, self.value)

    def encode(self):

        tv_sec, tv_usec = divmod(self.time, 1.0)
        return struct.pack(EVFMT, long(tv_sec), long(tv_usec*1000000.0), self.evtype, self.code, self.value)

    def decode(self, ev):

        tv_sec, tv_usec, self.evtype, self.code, self.value = struct.unpack(EVFMT, ev)
        self.time = float(tv_sec) + float(tv_usec)/1000000.0


class EventDevice(object):

    def __init__(self, filename=None):

        self._fd = None
        self._eventq = []
        self.filename = None
        self.name = None
        self.driver_version = None
        self.idbus = None
        self.idvendor = None
        self.idproduct = None
        self.idversion = None
        self.caps = None
        if filename:
            self.open(filename)

    def has_feature(self, evtype):

        return self.caps >> evtype & 1

    def __str__(self):

        ev_names = []
        for (evtype, ev_name) in EV_NAMES.items():
            if self.has_feature(evtype):
                ev_names.append(ev_name)
        ev_names_str = ", ".join(ev_names)
        return "%s: name='%s', driver_version=0x%x, bus=0x%x, vendor=0x%04x, product=0x%04x, version=0x%x, caps=0x%02x, features='%s'" % \
            (self.filename, self.name, self.driver_version, self.idbus, self.idvendor, self.idproduct, self.idversion, self.caps, ev_names_str)

    def _fill(self):

        global EVsize
        try:
            raw = os.read(self._fd, EVsize * 32)
#            raw = os.read(self._fd, EVsize)
        except EOFError:
            self.close()
        else:
            if raw:
                for i in range(len(raw)/EVsize):
                    ev = Event()
                    ev.decode(raw[i*EVsize:(i+1)*EVsize])
                    self._eventq.append(ev)

    def open(self, filename):

        self.filename = filename
        self._fd = os.open(self.filename, os.O_RDONLY)

        # The following try/except wrappers are a hack
        # to handle the following error:
        #     IOError: [Errno 22] Invalid argument
        # The way the ioctl constants are defined is not very portable.
        # For example, on some systems the EVIOCGNAME is defined incorrectly.
        # I need to fix how ioctl constants are defined. The constant
        # 1090536710 is one that "just works" on PowerPC where using
        # EVIOCGNAME fails. It's probably a big-endian vs.
        # little-endian thing. PowerPC is big endian.

        # device name
        try:
            name = fcntl.ioctl(self._fd, EVIOCGNAME, chr(0) * 256)
        except (IOError):
            name = fcntl.ioctl(self._fd, 1090471174, chr(0) * 256)
        self.name = name.strip(chr(0)).strip()
        # driver version
        try:
            ver = fcntl.ioctl(self._fd, EVIOCGVERSION, '\x00\x00\x00\x00')
        except (IOError):
            ver = fcntl.ioctl(self._fd, 1074021633, '\x00\x00\x00\x00')
        self.driver_version = struct.unpack(INT, ver)[0]
        # device ID info
        try:
            devid = fcntl.ioctl(self._fd, EVIOCGID, '\x00\x00\x00\x00\x00\x00\x00\x00')
        except (IOError):
            devid = fcntl.ioctl(self._fd, 1074283778, '\x00\x00\x00\x00\x00\x00\x00\x00')
        self.idbus, self.idvendor, self.idproduct, self.idversion = struct.unpack(SHORT4, devid)
        # capabilities
        try:
            caps = fcntl.ioctl(self._fd, EVIOCGBIT(0), '\x00\x00\x00\x00')
        except (IOError):
            caps = fcntl.ioctl(self._fd, 1090471200, '\x00\x00\x00\x00')
        self.caps = struct.unpack(INT, caps)[0]

    def fileno(self):

        return self._fd

    def close(self):

        if self._fd is not None:
            os.close(self._fd)
            self._fd = None
            self.name = ""

    def read(self):

        if not self._eventq:
            self._fill()
        if len(self._eventq) < 1:
            print "read nothing"
            return None
        return self._eventq.pop()

    def readall(self):

        ev = self.read()
        while ev:
            yield ev
            ev = self.read()


def get_devices():

    devs = []
    for nn in range(0, 100):
        filename = "/dev/input/event%d" % (nn,)
        if os.path.exists(filename):
            devs.append(EventDevice(filename))
        else:
            break
    return devs

def list_devices():

    """List all devices with the EV_REL 'Relative Axes' feature."""

    devs = []
    for nn in range(0, 100):
        filename = "/dev/input/event%d" % nn
        if os.path.exists(filename):
            ed = EventDevice(filename)
            if ed.has_feature(EV_REL):
                devs.append(ed)
        else:
            break
    for dev in devs:
        print str(dev)

def mouse_motion (input_device='/dev/input/event8'):

    ed = EventDevice(input_device)
    while ed:
        ev = ed.read()
        if ev.evtype == EV_REL:
            yield ev.value


def entropy_bit(input_device='/dev/input/event8'):

    motion = mouse_motion(input_device)
    while motion:
        bit = motion.next() % 2
        yield bit


def entropy_bit_unbias_vonneumann(input_device='/dev/input/event8'):

    bits = entropy_bit(input_device)
    while bits:
        bit1 = bits.next()
        bit2 = bits.next()
        if bit1 == bit2:
            continue
        else:
            yield bit1


def entropy_bit_unbias_xor(input_device='/dev/input/event8'):

    motion = entropy_bit(input_device)
    while motion:
        bit1 = motion.next()
        bit2 = motion.next()
        yield bit1^bit2


def entropy_bit_unbias_vonneumann2(input_device='/dev/input/event8'):

    bits = entropy_bit_unbias_vonneumann(input_device)
    while bits:
        bit1 = bits.next()
        bit2 = bits.next()
        if bit1 == bit2:
            continue
        else:
            yield bit1


def entropy_bytes (input_device='/dev/input/event8'):

    bit_source = entropy_bit_unbias_vonneumann(input_device)
    #bit_source = entropy_bit_unbias_xor(input_device)
    while bit_source:
        byte = 0x00
        for nn in range(8):
            byte = byte<<1
            bit = bit_source.next()
            byte = byte|bit
        yield byte


def main (options, args):

    if options.list:
	list_devices()
	return 0

    # The following options require args[0] to be defined.

    input_device = args[0] #'/dev/input/event4'

    if options.raw:
        # Remember, this is BIASED, so it is expected to give
        # more of one value of bit than another.
        entropy_source = entropy_bit(input_device)
        for bit in entropy_source:
            sys.stdout.write('%d'%bit)
            sys.stdout.flush()

    if options.rawvn:
        entropy_source = entropy_bit_unbias_vonneumann(input_device)
        for bit in entropy_source:
            sys.stdout.write('%d'%bit)
            sys.stdout.flush()

    if options.rawvn2:
        entropy_source = entropy_bit_unbias_vonneumann2(input_device)
        for bit in entropy_source:
            sys.stdout.write('%d'%bit)
            sys.stdout.flush()

    if options.rawxor:
        entropy_source = entropy_bit_unbias_xor(input_device)
        for bit in entropy_source:
            sys.stdout.write('%d'%bit)
            sys.stdout.flush()

    if options.bytes:
        entropy_source = entropy_bytes(input_device)
        for byte in entropy_source:
            sys.stdout.write(chr(byte))
            sys.stdout.flush()

if __name__ == "__main__":
    try:
        start_time = time.time()
        parser = optparse.OptionParser(
                formatter=optparse.TitledHelpFormatter(),
                usage=globals()['__doc__'],
                version='1')
        parser.add_option('-v', '--verbose', action='store_true',
                default=False, help='verbose output')
        parser.add_option('--bytes', action='store_true',
                default=True, help='dump binary stream (default)')
        parser.add_option('--hex', action='store_true',
                default=False, help='dump ASCII hex stream')
        parser.add_option('--raw', action='store_true',
                default=False, help='dump raw bits with bias')
        parser.add_option('--rawvn', action='store_true',
                default=False, help='dump raw bits with von Neumann debiasing')
        parser.add_option('--rawvn2', action='store_true',
                default=False, help='dump raw bits with 2-pass von Neumann debiasing')
        parser.add_option('--rawxor', action='store_true',
                default=False, help='dump raw bits with xor debiasing')
        parser.add_option('--list', action='store_true',
                default=False, help='list input devices')
        (options, args) = parser.parse_args()
	if not options.list and len(args) < 1:
            msg = """Missing input device argument. The mouse device is
usually something like '/dev/input/event3' or '/dev/input/event4'."""
            parser.error(msg)
        if options.verbose: print(time.asctime())
        exit_code = main(options, args)
        if exit_code is None:
            exit_code = 0
        if options.verbose:
            print (time.asctime())
            print ('TOTAL TIME IN MINUTES: %f'%((time.time()-start_time)/60.0))
        sys.exit(exit_code)
    except KeyboardInterrupt as e: # The user pressed Ctrl-C.
        raise e
    except SystemExit as e: # The script called sys.exit() somewhere.
        raise e
    except Exception as e:
        print ('ERROR: Unexpected Exception')
        print (str(e))
        traceback.print_exc()
        os._exit(2)