/dev/random and linux security issues (kinda long)

[aluminumsulfate at earthlink.net]

   Date: Sat, 14 May 2005 22:58:29 -0400
   From: mike ledoux <mwl+gnhlug at alumni.unh.edu>

   On Sat, May 14, 2005 at 10:39:44PM -0400, mike ledoux wrote:
   > On Sat, May 14, 2005 at 07:50:14PM -0400, aluminumsulfate at earthlink.net wrote:
   > > I just discovered something VERY DISTURBING about /dev/{u,}random in
   > > Linux....  Despite what the man page for urandom says, the data from
   > > /dev/random is REALLY not very random at all.  Many googleable pages
   > > on entropy gathering will tell you what the man page says: that
   > > /dev/random will block until the kernel has enough entropy to return
   > > data.  THIS IS FALSE!!!  FALSE FALSE!
   > 
   > This statement does not match my experience.  More to the point, it
   > is demonstrably untrue, simply by requesting 10k of random bytes
   > from each device:
   > 
   > [1011] 22:17 mwl at server:~>cat /proc/sys/kernel/random/entropy_avail; time dd if=/dev/random of=random.txt bs=1k count=10; cat /proc/sys/kernel/random/entropy_avail ; time dd if=/dev/urandom of=urandom.txt bs=1k count=10

   Of course, if you then look at the output files, you'll realize that
   dd will happily accept a few bytes from /dev/random in place of a 1k
   block, and leave you with a 346 byte random.txt.  Moving the k to
   the appropriate place in the dd command yeilds results more in line
   with expectations:

<snip>

Yes, I too observe that it takes /dev/random much (MUCH) longer to
return data than /dev/urandom.  But that doesn't mean that the data
which /dev/random returns is random... it just means it takes longer
to come up with it.  :) I asked about this on #crypto before posting
this finding.  The folks there seem to agree that /dev/random is not a
source of very random numbers.

Just take a 64-byte sample from /dev/random, at look at it in base 95:

dave at bat$ dd if=/dev/urandom bs=1 count=64 | ./string2dec.pl | ./dec2base95.pl 
64+0 records in
64+0 records out
64 bytes transferred in 0.001558 seconds (41076 bytes/sec)
Bm ?n`zp>4R>f4fC\>>u*HCkHRp*%%%Ha>M\/WW f4a94kaz* Wk4p/*Hf/*Mzz%%C>C *z%MRa4pZ

^^ That data looks anything BUT random.  I don't have the tools to do
a formal frequency analysis of it... but the result seems clear (with
a little inspection).  The output has 79 characters, 6 of which are
">" (7.6%), 6 of which are "%", 6 of which are "*", 5 of which are "z"
(6.3%), and none of "ADEFGIJKLNOPQRSTUVXYbcdeghijlmoqrstuvwxy"... not
to mention the punctuation characters it's missing.  The probability
of seeing 6 ">" in a random 79-digit base-95 number is 79C6 * 1/95^6 *
(94/95)^73, or .0175%.  Ditto for 6 "%" or 6 "*".  I can't be *that*
lucky....

Interestingly, my available entropy seems to *increase* as /dev/random
is read, and then max out at 4096.

dave at bat$ cat /proc/sys/kernel/random/entropy_avail 
4096

Dave