Random Numbers

From Federal Burro of Information
Revision as of 13:56, 15 May 2017 by David (talk | contribs) (→‎Gotchas, caveats, traps)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

So I posted to facebook hoping that my crypto friends would chime in.

David: I was reading http://arstechnica.com/security/2013/12/we-cannot-trust-intel-and-vias-chip-based-crypto-freebsd-developers-say/ and I thought, why not just connect a scintillation screen to a web cam, make a bitmap and go? It's harder than that right?

XXX XXX umm... because math? not easy to explain.

a webcam pointing at a naturally random effect could work, but you'd have to be *very* careful to make sure you know how much randomness is in your source, as well as how to get it out of your image without picking up any residual effects from the source, the environment, the camera, etc.

knowing "how much" randomness is in something (often referred to as entropy) is important - with a source like that, there's no good way to know. and knowing the "quality" of the randomness (distance from uniform, other entropy metrics) is also really important.

doing something like that over and over and saying "take the sum of each color value across the image mod 2, then take the best out of three for R/G/B to get one bit of randomness" might work, but you'd have to do it a lot and analyze the output to even know that. stronger assumptions can be made but they'll be even harder to confirm. even if the output "looks random" (1s 50% of the time, statistical tests within logarithmic space complexity pass) it might be possible for a maliciously constructed generator to not be giving you random bits.

this probably hasn't explained it any better, sorry. but yes, you can use sources like that (if you trust the phenomenon and the camera, which is a major problem on its own) if you know about the limitations and how to measure the output...

YYY YYY I've seen a real system using a camera and a lava lamp before. Any chaotic system would work. Its more complex than you need really. Comparing the drift between two independent clock signals is a far simpler circuit with easy to count entropy. The only trick is being certain the two clocks are indeed independent across the operating range (temperature/voltage/frequency). Unexpected parasitic coupling of clocks is a common failure. Lack of safeguards when the operating ranges are maliciously exceeded is another. The main issue I've seen though is lack of verifiability. The designs are always proprietary trade secrets (even when you have an NDA with the vendor!). Using a single entropy source is thus a bad strategy for any system.

XXX was a senior av researcher at messagelabs and now works at UofT Citizen labs researching people to attack NGOs

YYY Was (until 3 days ago) an engineering manager at Rim in the hardware crypto group.

Scripts

echo $(hexdump -n3 -e '/1 "%02X"' /dev/random)

Gotchas, caveats, traps

UUIDs, and GUIDs are _not_ random: https://en.wikipedia.org/wiki/Universally_unique_identifier

reference: http://stackoverflow.com/questions/1709600/what-kind-of-data-can-you-extract-from-a-uuid

#!/usr/bin/env perl

my $uuid="AAAAAAAA-BBBB-CCCC-DDDD-FFFFFFFFFFFF";
$uuid=~tr/-//d;
my $time_low=hex substr($uuid,2* 0,2*4);
my $time_mid=hex substr($uuid,2* 4,2*2);
my $version =hex substr($uuid,2* 6,1);
my $time_hi =hex substr($uuid,2* 6+1,2*2-1);

my $time=($time_hi*(2**16)+$time_mid)*(2**32)+$time_low;
my $epoc=int($time /10000000) - 12219292800;
my $nano=$time-int($time/10000000)*10000000;

my $clk_hi  =hex substr($uuid,2* 8,2*1);
my $clk_lo  =hex substr($uuid,2* 9,2*1);
my $node    =substr($uuid,2*10,2*6);

$node=~/^(..)(..)(..)(..)(..)(..)$/ || die;
$node="$1:$2:$3:$4:$5:$6";

print "time: ",scalar localtime $epoc," +",$nano/10000,"ms\n";
print "clock id: ",$clk_hi*256+$clk_lo,"\n";
print "Mac: $node\n";

my $byte=hex $1;
if(hex($1)&1){
    print "broadcast/multicast bit set.\n";
};