Thursday, 27 February 2014

If I say that I do what I want, it doesn't mean that everything I do is somehow unconventional

An ant starts to crawl along a taut rubber rope 1 km long at a speed of 1 cm per second (relative to the rubber it is crawling on). At the same time, the rope starts to stretch by 1 km per second (both in front of and behind the ant, so that after 1 second it is 2 km long, after 2 seconds it is 3 km long, etc).


When will the ant reach the end of the rope?



...the answer in the end.

----

Intel Ivy Bridge CPUs (rdrand instruction) and Raspberry Pi have a hardware random number generator which allows the production of seemingly very secure non-deterministic random numbers from thermal etc. sources for cryptographic purposes.



I also noticed that my MacBook Air uses Ivy Bridge i5 which comes with the rdrand instrunction. However the gcc on MacOS didn't seem to support this instruction so I wrote an assembly program (using nasm) to test if I get random numbers out of it. Seemed to work.

I tested the hwrng on the rpi and found that FIPS 140-2 gives similar results to /dev/urandom on linux, however /dev/hwrng on rpi should be intrincically non-deterministic, or at least similarly non-deterministic as thermal noise. The performance seems to be around 107 kB/s, rdrand appeared to give around 240 MB/s on a single core and single thread. I didn't bother tweaking. The official figure is supposedly at least 500 MB/s.

It's another question whether one can trust these hardware implementations or not as we have no sure way of knowing what they actually do and hardware manufacturer may be collaborating with NSA for example and get pseudorandom numbers anyway which might have a pattern identifiable by someone who knows how it was done.


; nasm -f macho64 rdr.asm
; nasm -f elf64 rdr.asm
bits 64
global rdr
section .text
rdr:
        rdrand rax
;        jnc rdr ; if CF=0, random data not available, try again, however, does not occur on Ivy Bridge so can be ignored at the moment
        ret

 ; gcc rdr.c rdr.o
#include <stdio.h>

 int rdr();
int main() {
        int x;
        for(x=0; x<256*256*256*2; x++)
                printf("%c", rdr());
}

 #!/bin/bash
clear
dd if=/dev/urandom of=./urandom.bin count=65536
./a.out > hwrandom.bin
echo
echo --rdrand--rdrand--rdrand--rdrand--
echo
cat hwrandom.bin | rngtest
echo
echo --urandom--urandom--urandom--urandom--
echo
cat urandom.bin | rngtest

 rngtest: starting FIPS tests...
rngtest: entropy source exhausted!
rngtest: bits received from input: 268435456
rngtest: FIPS 140-2 successes: 13413
rngtest: FIPS 140-2 failures: 8
rngtest: FIPS 140-2(2001-10-10) Monobit: 1
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 5
rngtest: FIPS 140-2(2001-10-10) Long run: 2
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0


rdrand: FIPS 140-2 failures: 14, 10, 14, 11, 9, 3, 7, 18, 13, 10
urandom: FIPS 140-2 failures: 11, 14, 9, 9, 7, 10, 10, 9, 13, 11

One should notice that it's supposed to fail occasionally on a perfect random number generator so nothing unusual here.

I ran the tests on one of my servers instead.

$ cat /proc/cpuinfo | grep -i 'model name' | head -n 1
model name      : Intel(R) Core(TM) i5-3570K CPU @ 3.40GHz

$ cat /proc/cpuinfo | grep -i rdrand | head -n 1
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmp
erf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm pcid sse4_1 sse4_2 popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm ida arat epb xsaveopt pln pts dtherm tpr_shadow vnmi flexpriority ept vpid fsgsbase smep erms

It gives "Illegal instruction (core dumped)" if you try to run it on something other than Ivy Bridge.

Similar tests on the rpi...

$ sudo cat /dev/hwrng | rngtest -c 1024
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: bits received from input: 20480032
rngtest: FIPS 140-2 successes: 1023
rngtest: FIPS 140-2 failures: 1
rngtest: FIPS 140-2(2001-10-10) Monobit: 1
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=70.080; avg=958.421; max=1627604.167)Kibits/s
rngtest: FIPS tests speed: (min=841.647; avg=3216.511; max=6401.590)Kibits/s
rngtest: Program run time: 27469963 microseconds

$ sudo cat /dev/urandom | rngtest -c 1024
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: bits received from input: 20480032
rngtest: FIPS 140-2 successes: 1023
rngtest: FIPS 140-2 failures: 1
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 1
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=1.510; avg=29.660; max=1733.953)Mibits/s
rngtest: FIPS tests speed: (min=843.719; avg=4117.551; max=6403.689)Kibits/s
rngtest: Program run time: 5620869 microseconds

I didn't run the stuff on /dev/random because it's a very low throughput entropy source.

Easiest way to fill the entropy pool (hardware noise):

$ cat /proc/sys/kernel/random/entropy_avail
150
$ ls -R /
...
$ cat /proc/sys/kernel/random/entropy_avail
2175


-- -- -- --

GPU accelerated fft on rpi


sudo ./hello_fft.bin  17 8
rel_rms_err = 7e-05, usecs = 17168, k = 0

... this is about 60MS/s, for the xcorr calculation discussed before it would be 2x20 MS/s (2 forwards, 1 backwards).

----

Eating one banana gives you higher dose of radiation than living next to a nuclear power plant for a year. Sleeping next to another human for 100 days equals one dental x-ray.

----

…the answer to the ant problem being about 8.8e43421 years.

(A huge, yet finite number much larger than any quantity in this universe.)

http://en.wikipedia.org/wiki/Ant_on_a_rubber_rope
Posted by at No comments:
Subscribe to: Posts (Atom)