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.

• Nzall: Is a gyroscope like those found in newer smartphones and laptops considered consumer hardware?
• Wrzlprmft: @NateKerkhofs: Yes.
• Nzall: Actually, could we get a definition of "consumer-grade hardware"? Is "anything you can buy at at your local computer store for less than 500 USD, or that you can get as part of a 1,000 USD machine" an acceptable definition?
• Wrzlprmft: @SebastianNegraszus: There is already an answer using that.
• Alexandre Teles: Let me insert a little trivia here, there is a real random number generator based on Quantum Mechanics running at the Australian National University. Take a look: qrng.anu.edu.au/index.php

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 ))

• user19214: What if I have the mic muted? Shouldn't this be perfect silence?
• Ell: @yeti: Well, sure. But we're allowed to assume that "the hardware is switched on and functional", which I think covers that.
• Olivier Dulac: unmuting everything is quite a big (and annoying) side-effect to a "pseudo random" binary generator, to me ^^
• Ismael Miguel: You could try to feed the speakers with some data using cat /dev/urandom > /dev/dsp, just in case the computer is in a sound-proof room/chamber/box/case/space.
• shortstheory: just what I wanted to do!

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.

• rr-: It always prints 1 for me: CYGWIN_NT-6.2-WOW64 work 1.7.28(0.271/5/3) 2014年02月09日 21:06 i686 Cygwin - ping has neither -q or -c here.
• rr-: Using Windows ping confirmed. I'm surprised.
• Dennis: @JamesSnell: That's the problem then. Windows ping doesn't have enough precision; it will always show a time of 1 ms...
• tophyr: Seems like this violates restriction #2: Pinging localhost depends entirely on the internal state of the computer.
• Wrzlprmft: Difficult to say. @Dennis: Do you know where the fluctuation comes from?

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.

• PTwr: "Please shake the device to generate new password."

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

• gnibbler: There is no "least significant bit" in a good hash. Yeah I know what you meant
• gnibbler: @11684, there's probably enough thermal noise etc. in the camera to prevent identical results
• Olivier Dulac: The light should fluctuate quite a bit (outside light going up/down, and of course any "blinkenlights" the computer probably emits)
• James_pic: This is loosely based on something a friend of mine did. He was interested in using radioactive decay to generate truly random numbers. He dismantled a webcam and a smoke alarm, put the isotope next to the CCD, and wrote some code to feed the locations of detected beta emissions into /dev/random. However, we found that even if we sealed off all the light from the outside, there was a measurable amount of background noise on the CCD, although the beta emissions were still detectable.
• James_pic: github.com/bitplane/schrodingers-rng

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))

• iFreilicht: A program that deletes and writes itself to the disk is something I could only imagine a perl or python programmer to do. Very cool idea!
• Peteris: This looks something that wouldn't touch any hardware and be deterministic when run within a VM, which is a very common scenario.
• MSalters: You'd want a flush to disk to make it depend on the disk instead of the cache (which is machine state, rule #2)

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.

• Wrzlprmft: This answer has been awarded a special bounty for a particularly short solution (just in case, anybody wonders). It was tied with Franki’s answer by my criteria and won by lot.

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.

• Wrzlprmft: Hmm, I would not count the absence of wi-fi devices so unnatural that you can neglect it.
• Ian D. Scott: @Wrzlprmft It depends where you are. It is unnatural to not have wifi networks in a crowded urban area. On a universal scale, not being in a near total vacuum is not a fair assumption, nor if limited to Earth is it fair to assume the computer is not submerged in water.
• Wrzlprmft: @IanD.Scott: Well, the next wifi-free area for me is actually in the cellar (don’t ask me why I know this). And I am not living in the middle of nowhere. Anyway, the number of computers in wifi-free suroundings certainly exceeds the number of (working) computers in water or a vacuum by several orders of magnitude. (It all comes down to your definition of natural in the end, I guess.)

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 0ドルx30,%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 0ドルx80
 # okay, we're done here. Let's exit
 mov %ebx,%eax # do an exit system call with status 0
 xor %ebx,%ebx
 int 0ドルx80
.Lfailure:
 mov 1,ドル%eax # do an exit system call with status 1
 mov %eax,%ebx
 int 0ドルx80
 .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 0ドルx15,%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 0ドルx15,%eax
 80480ab: 73 2f jae 80480dc <_start+0x44>
 80480ad: b8 01 00 00 00 mov 0ドルx1,%eax
 80480b2: 0f a2 cpuid 
 80480b4: 0f ba e1 1e bt 0ドルx1e,%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 0ドルx1,%eax
 80480c3: 04 30 add 0ドルx30,%al
 80480c5: 50 push %eax
 80480c6: b8 04 00 00 00 mov 0ドルx4,%eax
 80480cb: bb 01 00 00 00 mov 0ドルx1,%ebx
 80480d0: 89 e1 mov %esp,%ecx
 80480d2: 89 da mov %ebx,%edx
 80480d4: cd 80 int 0ドルx80
 80480d6: 89 d8 mov %ebx,%eax
 80480d8: 31 db xor %ebx,%ebx
 80480da: cd 80 int 0ドルx80
 80480dc: b8 01 00 00 00 mov 0ドルx1,%eax
 80480e1: 89 c3 mov %eax,%ebx
 80480e3: cd 80 int 0ドルx80

• Wrzlprmft: "You may use any [...] hardware [...] – unless it is intended for random-number generation." – The goal is to improvise a hardware random-number generator, not to use one.
• FUZxxl: @Wrzlprmft rdrand is not a random number generator. It's a peripheral made for the NSA to mess with people's cryptography.
• FUZxxl: Actually, I didn't notice that sentence before writing this program. My bad.

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]

• Display Name: with averaging, the deviation can be very small...

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;

• Frank: I just found a bug in FF, "Stop sharing" doesn't turn of the webcam!

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.

• Wrzlprmft: This answer was tied for the bounty for a particularly short answer by my criteria and lost by lot.

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 :-)

• Emil: What happens if the record is not silent and there are no non-zero samples?
• user20424: Good question. Some zeros tend to pop up anyway, because the values oscillate around zero (sound vibrations) and there's a limited number of decimals. But now that you mention it, it should of course be "<0" rather than ~=0, so that I count the number of negative samples instead. :-] This too is random.

Answer 16

Bash

(Thanks, Dennis.)

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

• Wrzlprmft: If I am not fully mistaken, this only relies only on the system time and the current software state of the computer and moreover requires a user to be logged in.
• Dennis: @Wrzlprmft: w shows a list of logged in users, which can be empty. The system load is based on the CPU queue length.
• Soham Chowdhury: Well, I could replace w with top.

Answer 17

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 18

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 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.

• clismique: Is there really any difference between your and Soham's program?