Improvise a Hardware Random-Number Generator

Question

Your task is to improvise a hardware random-number generator with whatever hardware you have lieing around.

Challenge

Write a program with the following properties:

1. It prints either 0 or 1 (and nothing else).
2. The output depends on a physical process and not just the internal state of the computer.
3. There is no relation between outputs of subsequent runs (one minute apart).
4. The output is not predictable with any realistic effort.
5. The probability of the output being 0 is between 0.2 and 0.8.
6. It runs in less than a minute with a reasonably high probability.

You must explain why your program has these properties, if it is not obvious.

Clarifications and Restrictions

The following may seem like an awful lot of restrictions for a popularity contest, but ultimatively it’s all to ensure that the program remains within the spirit of the question, somewhat works and to avoid solutions which are popular due to being a total overkill but are ultimatively rather boring.

• The system time does not count as a physical process.
• You may use any consumer-grade hardware you like from 8-inch floopy-disk drives to a USB rocket launcher to headphones – unless it is intended for random-number generation. A piece of hardware is consumer-grade, if it is mass-produced and costs less than 1000 $/€/£, so you cannot use radio telescopes, the CERN, MRIs or your home-built particle detector.
• You can only make the most basic assumptions on the state and alignment of the hardware such as being switched on (if it has a power switch) and being properly installed and functional. For example you can assume a CD drive to be generally capable of reading a disk and not to be jammed, but you cannot assume it to be open or closed or to contain a disk. In another example you cannot assume two pieces of hardware to be aligned to allow for a special interaction, but you can assume them to be in the same room.
• You may leave the hardware in any state you like, unless you break it.
• You can and must assume the hardware to be in a natural environment, but nothing more. For example you can assume that the hardware is not positioned in a in tank of liquid helium nor in an extremely sound- and lightproof room nor in space. However, you cannot assume any sound- and lightsources to be present except those that are only avoidable with radical efforts.
• Your program must run on a standard desktop computer with a non-esoteric operating system of your choice. You may employ any software that is not specifically designed for random-number generation.
• You cannot assume Internet access.
• You can neither assume humans to be present nor absent, but you can assume that nobody intentionally interfers with your program, e.g., by manually stopping a fan or running a program that does nothing but switching off the microphone as often as possible.
• You can only make the most basic assumptions about the software settings. For example, you can assume drivers to be installed and activated but you must be prepared for the sound to be muted.
• You may leave the software settings in any state you like.

Bonus

A special bounty was awarded to a particularly short solution. This was rather by numbers of instructions and similar than by characters. The winners were (tied according to my criteria):

• This answer by Franki.
• This answer by Tejas Kale.

I could only award one answer and Tejas Kale’s answer won by lot.

Answer 1

Shell

Reads a single sample from the microphone stream and prints its least-significant bit, which should be dominated by noise.

EDIT: Changed to unmute the microphone ... and everything else too!

# Warning - unmutes EVERYTHING!
for DEV in `amixer | grep Simple | sed -e "s/.*'\(.*\)'.*/\\1/" -e "s/ /~/g"`
do
    amixer -q -- sset "`echo $DEV | sed 's/~/ /g'`" unmute 100% 2>/dev/null
done

echo $(( `od -N1 -d < /dev/dsp | head -n1 | sed 's/.* //'` & 1 ))

Answer 2

Bash

echo $[`ping -qc1 127.1|sed 's/[^1-9]/+/g'`0&1]

Gathers entropy from the response time of a single ping to localhost.

Note that the response time appears exactly thrice in the output of ping -qc1:

PING 127.1 (127.0.0.1) 56(84) bytes of data.

--- 127.1 ping statistics ---
1 packets transmitted, 1 received, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 0.044/0.044/0.044/0.000 ms

All other numbers and constant and – more importantly – independent from the response time.

sed 's/[^1-9]/+/g' converts every zero and non-digit into plus signs, and echo $[...0&1] prints the parity of the resulting sum.

Answer 3

JavaScript + HTML5 DeviceMotion

var hash = function(x) {
    var h = 0
    for (var i = 0; i < x.length; i++) {
        h += x.charCodeAt(i)
        h ^= h << 5
        h ^= h >> 3
        h ^= h << 13
        h &= 0xffff
    }
    return h
}
var listener = function(e) {
    var accelerationString = JSON.stringify(e.acceleration)
    var hashed = hash(accelerationString)
    alert(hashed % 2)
    window.removeEventListener("devicemotion", listener, true)
}
window.addEventListener("devicemotion", listener, true);

JSFiddle here.

Uses the HTML5 DeviceMotion API on supported devices (mostly mobile devices). It turns the resulting acceleration object into JSON, hashes it, and takes the remainder modulo 2.

Most of the code is the hash function (damn you JavaScript, and your total lack of a standard library). It could probably be shorter, but I'm a sucker for a good hash function.

Answer 4

Python + Webcam

Using code shamelessly stolen from here, takes a shapshot using your webcam, hashes the data, and prints the least significant bit.

#!/usr/bin/python
import pygame.camera, hashlib

pygame.camera.init()
cam = pygame.camera.Camera(pygame.camera.list_cameras()[0])
cam.start()
raw = cam.get_raw()
cam.stop()
pygame.camera.quit()

h = hashlib.sha256()
h.update(raw)
print ord(h.digest()[-1]) % 2

Answer 5

Perl

Checks your Harddrive's response time, by timing three operations:

• Reading its own source
• Deleting itself
• Writing itself again

Finally, the time taken is packed as a float, and the 11th most significant bit is used (second most significant bit of the mantissa).

use Time::HiRes qw(time);

$t1 = time;
open SELF, "<$0";
read SELF, $_, $^H;
close SELF;

unlink $0;

open SELF, ">$0";
print SELF $_;
close SELF;

print 1&unpack(xB3, pack(f, time-$t1))

Answer 6

Bash

echo $[`sensors|sed 's/[^1-9]/+/g'`0&1]

sensors prints the current system temperatures along with the fan speed.

acpitz-virtual-0
Adapter: Virtual device
temp1:        +52.0°C  (crit = +98.0°C)

thinkpad-isa-0000
Adapter: ISA adapter
fan1:        3510 RPM

coretemp-isa-0000
Adapter: ISA adapter
Physical id 0:  +54.0°C  (high = +86.0°C, crit = +100.0°C)
Core 0:         +51.0°C  (high = +86.0°C, crit = +100.0°C)
Core 1:         +46.0°C  (high = +86.0°C, crit = +100.0°C)

sed 's/[^1-9]/+/g' converts every zero and non-digit into plus signs, and echo $[...0&1] prints the parity of the resulting sum.

Regex and parity calculation borrowed from dennis's answer.

Answer 7

Bash

(echo -en "ibase=16;";(find /proc/[0-9]*/s* -type f -maxdepth 2 ; find /sys /proc/[^0-9]* -type f) 2>&1 | xargs -n1 sha256sum  2>&1 | sha256sum | tr abcdef ABCDEF | sed 's/  -/%2/' )| bc

Uses everything, just in case...

Depends on

• sensor readings of most hardware sensors (about all somehow expose their values somewhere in /sys or /proc)
• number, memory layout and runtimes of all processes on the system (which may be considered "state of the system" but usually themselves depend on the timings of the hardware)
• depending on the system, various values in /proc/<pid>/s* (e.g. sched/schedstat) depend on the speed of the hardware necessary to bring those processes alive.
• things I might not have thought of that are available in those files too.

Runtime on my system is ~10s, but may vary a lot. Especially don't run this as root, or at least modify it to exclude /proc/kcore (unless you are willing to spend a lot of time to include the entropy contained in there, which would probably really include everything)

Answer 8

Shell + Wi-Fi

sudo airmon-ng start wlan0 > /dev/null && sudo dumpcap -a duration:30 -i mon0 -w out.cap > /dev/null && sha512sum out.cap | grep -c "^[0-7]" && sudo airmon-ng stop mon0 > /dev/null

Puts the wi-fi card into monitor mode, dumps 30 seconds worth of packets received (including unreadable encrypted data from neighbouring networks), takes the sha512 hash of the packet data, and returns 1 if the first letter of the hash is 0-7. Assumes that your wi-fi card is wlan0, and that you do not currently have a mon0 device.

If there are no nearby wi-fi devices, then the output will be predictable, as it will be the same every time.

Answer 9

Modern 8086 compatible processors manufactured by Intel contain an easily accessible peripheral that generates proper randomness. Driving that peripheral is done using the rdrand instruction which either generates a random bit pattern or sets the carry flag if the peripheral is unavailable or out of entropy.

The following short program for 80386 Linux checks if the peripheral is available by means of the cpuid instruction and tries to generate a random number. If either the peripheral or a random number is not available, the program will terminate with a status of 1. If a random number could be generated, either a 1 or a 0 is printed out and the program terminates with exit status 0.

Save as rand.s and assemble with

as --32 -o rand.o rand.s
ld -melf_i386 -o rand rand.o

Here is the entire assembly:

        .globl _start
        .type _start,@function
_start:
        # check if the cpuid instruction is available by trying to
        # toggle the id flag in the eflags register
        pushfl
        mov (%esp),%eax
        btc $21,%eax    # toggle id bit
        push %eax
        popfl           # check if id bit was saved
        pushfl
        pop %eax        # load new flags
        pop %ecx        # load original flags
        xor %ecx,%eax   # difference is in %eax
        bt $21,%eax     # check if bit was flipped
        jnc .Lfailure

        # if we reach this part, we have a cpuid instruction
        # next, check if rdrand exists
        mov $1,%eax     # load cpuid leaf 1
        cpuid
        bt $30,%ecx     # is rdrnd available?
        jnc .Lfailure

        # let's try to get some random data
        rdrand %ax      # don't waste randomness; one bit would suffice
        jnc .Lfailure   # no randomness available
        and $1,%eax     # isolate one bit of randomness
        add $0x30,%al   # 0x30 = '0'
        push %eax
        mov $4,%eax     # prepare a write system call
        mov $1,%ebx
        mov %esp,%ecx   # where we placed the data before
        mov %ebx,%edx   # one byte
        int $0x80

        # okay, we're done here. Let's exit
        mov %ebx,%eax   # do an exit system call with status 0
        xor %ebx,%ebx
        int $0x80

.Lfailure:
        mov $1,%eax     # do an exit system call with status 1
        mov %eax,%ebx
        int $0x80

        .size _start,.-_start

And a dump of the resulting 77 bytes of machine code:

08048098 <_start>:
 8048098:   9c                      pushf  
 8048099:   8b 04 24                mov    (%esp),%eax
 804809c:   0f ba f8 15             btc    $0x15,%eax
 80480a0:   50                      push   %eax
 80480a1:   9d                      popf   
 80480a2:   9c                      pushf  
 80480a3:   58                      pop    %eax
 80480a4:   59                      pop    %ecx
 80480a5:   31 c8                   xor    %ecx,%eax
 80480a7:   0f ba e0 15             bt     $0x15,%eax
 80480ab:   73 2f                   jae    80480dc <_start+0x44>
 80480ad:   b8 01 00 00 00          mov    $0x1,%eax
 80480b2:   0f a2                   cpuid  
 80480b4:   0f ba e1 1e             bt     $0x1e,%ecx
 80480b8:   73 22                   jae    80480dc <_start+0x44>
 80480ba:   66 0f c7 f0             rdrand %ax
 80480be:   73 1c                   jae    80480dc <_start+0x44>
 80480c0:   83 e0 01                and    $0x1,%eax
 80480c3:   04 30                   add    $0x30,%al
 80480c5:   50                      push   %eax
 80480c6:   b8 04 00 00 00          mov    $0x4,%eax
 80480cb:   bb 01 00 00 00          mov    $0x1,%ebx
 80480d0:   89 e1                   mov    %esp,%ecx
 80480d2:   89 da                   mov    %ebx,%edx
 80480d4:   cd 80                   int    $0x80
 80480d6:   89 d8                   mov    %ebx,%eax
 80480d8:   31 db                   xor    %ebx,%ebx
 80480da:   cd 80                   int    $0x80
 80480dc:   b8 01 00 00 00          mov    $0x1,%eax
 80480e1:   89 c3                   mov    %eax,%ebx
 80480e3:   cd 80                   int    $0x80

Answer 10

bash

Aiming for the most unnecessarily expensive random number gathering method. Time how long it takes to spawn emacs a million times, then use Dennis' trick to turn the time taken into a single Boolean (takes about 7 seconds on my machine).

$[`(time (seq 1000000 | xargs -P1000 emacs  >/dev/null 2>&1)) |& sed 's/[^1-9]/+/g'`0&1]

Answer 11

Arduino Mega1280

edit: updated version that is robust against having anything plugged into the pins. The idea relies on the fact that the ATMega1280 uses a separate internal oscillator for the watchdog oscillator. I simply setup a watchdog interrupt which sets a flag, have a counter based on the system clock (on the Arduino this is a 16MHz external crystal), and allow clock jitter/variance do the work.

#include <avr/interrupt.h>

int time;
volatile bool wdt_ran;

// watchdog interrupt handler
ISR(WDT_vect, ISR_BLOCK)
{
  wdt_ran = true;
}

void setup()  
{
  // setup watchdog interrupt
  cli();
  MCUSR &= ~(1 << WDRF);
  WDTCSR |= (1<<WDCE) | (1<<WDE);
  WDTCSR = (1<<WDIE) | (1<<WDP2) | (1<<WDP1) | (1<<WDP0);
  sei();
  // Open serial communications and wait for port to open:
  Serial.begin(57600);
}

void loop()
{
  if(wdt_ran)
  {
    Serial.println(abs(time%2));
    wdt_ran = false;
  }
  ++time;
}

Answer 12

Javascript

http://jsfiddle.net/prankol57/9a6s0gmv/

Takes video input.

You can see the screenshot that it used to calculate the random number.

var m = (navigator.getUserMedia || navigator.webkitGetUserMedia || navigator.mozGetUserMedia || navigator.msGetUserMedia);

var constraints = {
  video: {
    mandatory: {
      maxWidth: 350,
      maxHeight: 350
    }
  },
  audio: false
};

var video = document.querySelector("video"), canvas = document.createElement("canvas");
document.body.appendChild(canvas);
canvas.width = 350;
canvas.height = 350;

function start() {
    m.call(navigator, constraints, function (stream) {
        video.src = window.URL.createObjectURL(stream);
    }, function() {
        alert("An error occured. Did you deny permission?");
    });
}

if (m) {
    start();
} else {
    alert('getUserMedia() is not supported in your browser');
}

function getRandomData() {
    var ctx = canvas.getContext("2d");
    ctx.drawImage(video, 0, 0);
    var data = ctx.getImageData(0, 0, 350, 350).data;
    var total = 0;
    for (var i = 0; i < data.length; ++i) {
        total += data[i];
        total %= 2;
    }
    alert("The random number is " + total);
}

document.querySelector("button").onclick = getRandomData;

Answer 13

Shell on Linux

Measure read speed of a hard drive + access time of a frequently updated directory on this disc which layout is unpredictable.

# Set this to the device node of whatever drive you want to measure
DRIVE_DEVICE=sda
# This must be a path that is
# a) on device "/dev/$DRIVE_PATH"
# b) frequently updated to add additional access time randomization due to
#    less-predictable disk layout due to less-predictable time, amount and
#    ordering uf updates, like logfile directories, maybe cache directories.
FIND_PATH=/var/log
# Better than using 'sync' - sync only the disk that we actually read from
# also sync both internal drive and system buffers
hdparm -f -F "/dev/$DRIVE_DEVICE"
# Note: bash's built-in time command doesn't support formats :/
# Note: the result is only going to be as good as the system's time command,
#       which isn't necessarily equally good on other U*ICes
t=$(command time -f '%e' -- find "$FIND_PATH" -printf '' 2>&1)
echo $((${t#*.}&1))

requires:

1) read and execute access to every directory under "$FIND_PATH"
2) sending (flush) control commands to a hard drive via a device node.
   Requires root access per default, but can be delegated to a less privileged user
   either by using sudo on this script or by applying
       chgrp 'some_system_group' "$DRIVE_DEVICE" &&
       chmod g+rx "$DRIVE_DEVICE"
   if this is acceptable on your system.

This approach has the advantage of not modifying any data on the system and not requiring perl over primo's one.

Answer 14

Shell

Tested on Linux, but maybe your U*IX does have /proc/stat as well?

This starts only a single additional process, reads only a single additional file (not even on disc) and is 37 characters short. It's also pretty fast.

t=1`sum /proc/stat`;echo $[${t% *}&1]

One may think that this is determined by all kernel and userland process states, but that is not the case, since /proc/stat also includes IO-wait time, time to sevice hardware interrupts, time spent in idle task and some other which all depend on external hardware input.

Answer 15

Matlab

The microphone solution:

recObj=audiorecorder;recordblocking(recObj,10);rem(sum(getaudiodata(recObj)<0),2)

Records 10 seconds of sound, finds the number of negative samples in the recording and outputs 0 if this number is even and 1 if it's odd. Thus 0 with 50% probability. The approach means that even small amounts of noice, unavoidable in a silent recording, will be enough to generate a random output. The following slightly longer code speeds up the number generator by using a shorter recording, compensated with a higher bitrate, which gives more noise.

recObj=audiorecorder(8000,16,1);recordblocking(recObj,0.1);rem(sum(getaudiodata(recObj)<0),2)

In a test under quiet conditions, I find that in 100 runs of the latter code, the code outputs zero 51 times. 100 runs under noisy conditions produced zero 40 times.

Edit: Thanks to Emil for pointing out a flaw in the original code :-)

Answer 16

SmileBASIC

XON MOTION 'enable motion sensor
ACCEL OUT ,,Z 'get Z acceleration (up/down)
PRINT Z<-1 'if Z is less than -1, output 1, otherwise 0.

Uses the 3DS's motion sensor. The Z axis of the accelerometer is usually around -1 (because of gravity), and due to random noise, it can sometimes be above or below that.

Here's one that uses the microphone:

XON MIC 'enable microphone
DIM REC%[0] 'make array
MICSTART 0,3,1 'start recording. 0=8180Hz, 3=8 bit unsigned, 1=1 second
WAIT 1 'delay (1 frame is enough since we only check the first sample)
MICSAVE MIC 'save recording
PRINT MIC[0]>0 'if the first sample isn't negative, output 1

Answer 17

Bash

(Thanks, Dennis.)

echo $[`w|sed 's/[^1-9]/+/g'`0&1]

Answer 18

Takes the least significant bit of the computer's accelerometer (needs the hdaps Linux module):

#!/usr/bin/env python
import re
m = re.search('([-\d]+),([-\d]+)',
              open('/sys/devices/platform/hdaps/position', 'r').read())
print((int(m.group(1)) ^ int(m.group(2))) & 1)

This basically measures the noise of the sensor.

Answer 19

Bash

I took Soham’s own suggestion (using top):

echo $[`top -bn1|sed 's/[^1-9]/+/g'`0&1]

Edit: It works the same way Soham's does. It turns all non numeric characters in the output of top into '+' and then evaulates the parity of the resulting string.

the 'b' flag to top runs it in batch mode so that it reports all processes, not just the first screenful and 'n1' says to just run 1 iteration of top.