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

Sun May 15 18:43:01 EDT 2005

For those of you who've been waiting to see what patterns I can find
in the number pi.... uh, oh... wrong movie.  I have good news: the
universe ISN'T falling apart!  I recoded my Perl scripts in LISP (the
language I should have coded it in, anyway... but I was trying to be a
Perl geek and use Perl's BigInt...), and the output from /dev/pennies
*is* random afterall!

Output from Perl: (cannot be correct in a sane universe)
7xW#mknuHpMRM*Mp\9R CRM/99HpMz%f>>Hf\Rf/faf9WRpWHH%a\a W4Wu a>zzuppRWa94f\9f4O

Output from LISP: (represents the universe I like to live in)
7xW#mknhEfY'C/87QMQ/:AaDfVZS-{XKQ_CL*VH]K+D)"m|%_v?mmuujC\hX0y6tCtYM Z(.qPn at TO

Notice that the two results are identical, up to the eighth byte.  *I*
don't see anything wrong with my Perl scripts... so I figure there's
very likely some obscure (and very strange) bug in Perl's BigInt.  I
say "strange" because the (incorrect) output it produces is always the
same AND the process is reversible...  meaning that feeding data
through

echo $blah | ./dec2base95 | ./base95to10.pl
blah

always gives me back the original data.

But, more to the question I've been asking: "Is the /dev/random device
a source of high-quality random numbers?", I applied the LISP-coded
analyzer to the output of /dev/random...

dave at bat$ dd if=/dev/random bs=1 count=64 of=base95.ana; GCL_ANSI=t gcl -batch -load base95ana.lisp
64+0 records in
64+0 records out
64 bytes transferred in 0.005469 seconds (11702 bytes/sec)
(98 252 42 31 159 180 197 210 221 176 165 254 84 83 238 243 89 133 1
  13 131 34 123 128 15 149 124 179 133 160 97 162 73 236 75 252 204 190
  242 59 49 66 95 81 74 228 87 141 55 6 99 53 178 148 115 178 182 33 6
  148 39 201 159 42)
5184266039017642205320923282221963255525057715521590619402061685201875242677999906964709707296811729680786740704812817513446133258363618766453033411387178
(26 86 74 5 11 35 64 16 22 56 60 32 41 58 73 94 35 32 89 11 86 60 67 22
 74 28 72 58 85 53 21 31 14 35 22 74 73 93 85 19 43 38 8 76 75 58 4 5
 87 78 66 89 48 74 19 8 6 88 72 53 79 11 56 59 39 22 75 64 75 74 31 74
 13 35 55 69 27 13)
":vj%+C`06X\\@IZi~C at y+v\\c6j<hZuU5?.C6ji}u3KF(lkZ$%wnbyPj3(&xhUo+X[G6k`kj?j-CWe;-"
dave at bat$ dd if=/dev/random bs=1 count=64 of=base95.ana; GCL_ANSI=t gcl -batch -load base95ana.lisp 
64+0 records in
64+0 records out
64 bytes transferred in 0.007267 seconds (8807 bytes/sec)
(164 127 212 87 2 36 250 13 99 122 125 241 188 50 86 168 103 134 35
  106 95 44 192 250 91 54 44 3 106 46 5 60 70 124 248 16 199 155 241
  247 212 25 76 88 46 94 0 142 242 81 19 88 78 162 135 32 213 54 227
  255 7 213 62 35)
8615529188225248535683463564085339063892036996086582469016713955655227163825143780054806758162872538151902293395629239250709778833664026164465213015146019
(44 69 1 13 16 14 93 5 46 3 50 86 4 16 29 32 29 16 61 17 52 92 3 3 62
 77 81 13 6 18 40 65 13 11 35 27 8 5 40 29 41 6 25 30 9 32 49 54 57 26
 19 64 19 57 48 92 53 34 3 90 1 36 80 81 18 13 70 30 37 40 39 84 8 40
 69 90 31 74)
"Le!-0.}%N#Rv$0=@=0]1T|##^mq-&2Ha-+C;(%H=I&9>)@QVY:3`3YP|UB#z!Dpq2-f>EHGt(Hez?j"
dave at bat$ dd if=/dev/random bs=1 count=64 of=base95.ana; GCL_ANSI=t gcl -batch -load base95ana.lisp 
64+0 records in
64+0 records out
64 bytes transferred in 0.007337 seconds (8723 bytes/sec)
(91 51 18 97 158 231 252 131 52 131 121 61 107 141 10 189 196 208 158
  93 52 155 20 237 142 219 101 147 0 201 82 89 247 245 141 43 170 91
  195 135 183 67 39 95 151 10 20 244 131 218 68 86 229 50 64 162 210
  105 195 239 192 82 20 226)
4776505347424135397985009156966054293689649870957743259302702068781028019596707452247298333940002140346627702878003775955608996630853181523936277704086754
(24 75 64 55 57 83 82 91 9 19 68 69 22 39 58 21 40 47 61 82 93 42 92 94
 6 36 39 42 4 8 90 82 38 46 21 57 50 72 7 93 70 15 92 11 4 69 80 66 25
 20 47 73 2 64 23 22 15 41 93 1 64 49 10 19 45 69 41 83 43 5 50 79 23
 24 80 59 25 29)
"8k`WYsr{)3de6GZ5HO]r}J|~&DGJ$(zrFN5YRh'}f/|+$epb94Oi\"`76/I}!`Q*3MeIsK%Ro78p[9="

The extra backslashes are okay... they're just used to quote special
characters.  Note that the output *looks* random now (in fact, alot
like the output of rand95.pl, as was expected), meaning that the
output of /dev/random isn't *obviously* flawed.  So the answer to my
question, then, is: "Maybe." :) I'd still love to see how /dev/random
stands up to the DIEHARD tests....

   Date: Sun, 15 May 2005 14:10:34 -0400
   From: mike ledoux <mwl+gnhlug at alumni.unh.edu>

<snip>

   It may seem that way at first thought, but it is not the case.  It
   is entirely possible to randomly generate the same value repeatedly
   in sequence.  Statistically, it is, in fact, equally likely that you
   will generate 79 '6's as 79 characters with no repeats.

I don't believe so. The probability of getting 79 '6's is 1/95^79.
The probability of getting ANY string of 79 of the same digit would be
1/95^78.  IIRC, the probability of getting 79 different characters,
with no repeated digits, would be 95P79 / 95^79.

dave at bat$ bc -q
scale=50
95 * 94 * 93 * 92 * 91 * 90 * 89 * 88 * 87 * 86 * 85 * 84 * 83 * 82 * 81 * 80 * 79 * 78 * 77 * 76 * 75 * 74 * 73 * 72 * 71 * 70 * 69 * 68 * 67 * 66 * 65 * 64 * 63 * 62 * 61 * 60 * 59 * 58 * 57 * 56 * 55 * 54 * 53 * 52 * 51 * 50 * 49 * 48 * 47 * 46 * 45 * 44 * 43 * 42 * 41 * 40 * 39 * 38 * 37 * 36 * 35 * 34 * 33 * 32 * 31 * 30 * 29 * 28 * 27 * 26 * 25 * 24 * 23 * 22 * 21 * 20 * 19 * 18 * 17 / 95^79
.0000000000000000000002839978194482798799021130532484016900974590995\
667675189103103165919953744348550
scale=200
1/95^79
.0000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000057522159525614376669710905909232712000334637
1/95^78
.0000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000005464605154933365783622536061377107640031790595

So, getting a string with no repeated digits is *many zeros* more likely
than getting 79 of the same digit.

   Like I said, the human brain is very good at finding patterns where
   none exist.

It's also very good at finding patterns where they do. ;)

   Well, 64 bytes should not exhaust your entropy pool anyway.  Try
   reading 4k blocks and see what you get.  If your entropy_avail stays
   full at 4096 on that test, something strange may be happening.

Sending the random data to /dev/null a few times, however, does have
that effect: (yes, I know! I'm throwing away perfectly good entropy!)

cat /proc/sys/kernel/random/entropy_avail; dd if=/dev/random bs=1 count=64 of=/dev/null; cat /proc/sys/kernel/random/entropy_avail
4096
64+0 records in
64+0 records out
64 bytes transferred in 0.002209 seconds (28973 bytes/sec)
3072

   -- 
   mwl+gnhlug at alumni.unh.edu          OpenPGP KeyID 0x57C3430B
   Holder of Past Knowledge           CS, O-
   Put your wasted CPU cycles to use: http://www.distributed.net/
   "The game is called, Super Monkey Ball. Apparently, there are these monkeys,
    and they have balls, big giant balls, which you use to move about."  Largo

   _______________________________________________
   gnhlug-discuss mailing list
   gnhlug-discuss at mail.gnhlug.org
   http://mail.gnhlug.org/mailman/listinfo/gnhlug-discuss

If anyone finds this is due to mistake in my Perl code (which can be
found at the end of my first message), I'd love know what it is.  I
think the bug is in BigInt.  But I'm not a big enough Perl fan to go
submit this as a bug, so feel free to do that, too.  The LISP code to
my analyzer is available should anyone want it. "Here, here!" to the
coolest programming language in existence. ;)

Now, the only question I have is: Which device do I trust more for
crypto, /dev/random or /dev/pennies...?

Dave