From: doug@netcom.com (Doug Merritt)
Date: Tue, 11 Jan 94 09:37:08 PST
To: cypherpunks@toad.com
Subject: Weak Random Number Generators
Message-ID: <199401111734.JAA04369@mail.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


jerry@terminus.dell.com a while ago said he'd made a hardware random
number generator, and offered to send out data generated by it, inviting
people to look for weaknesses.

I followed up on that and found problems with one of the two sets of
data he sent (files a.bin and b.bin, one produced with his hardware and
one with a software RNG, but which is which was not identified). He
apparently is too busy to acknowledge my response, so I thought I'd
post the results I emailed him here, for those of you interested in
weaknesses of RNG's.

The weakness is shown via ascii graphics of the results of the analysis,
which makes it accessible and intuitive.

-------------- included message ------------------

As I suspected, it only took a few minutes of programming to find
periodicity in the phase space. The set you called "a.bin" is the
one that shows a great deal of obvious structure. The intrinsic
resonance is related to powers of two (I haven't figured it out
more closely than that), which is what one might expect from software
methods, but less likely from hardware methods (unless there's a
power-of-two bias introduced by an ADC).

On the other hand, I may be seeing structure in your psuedo-random
number generator...they're notoriously bad unless you went out of
your way to find a really really good one.

The b.bin file appeared ergodic, almost completely filling the 2d
phase space I picked as an easy-to-implement test. I may try another
few tests shortly.

For your amusement, I produced two psuedo-RNG files, one using the
ancient and decrepit rand() function, well known to be a very poor
source of randomness (c.bin), and one using the more carefully
constructed BSD Unix random() function (d.bin). The latter also
has its flaws, but they are far better hidden than those of rand().
Note that c.bin is even more grossly flawed (structured) than your a.bin.

Meanwhile, if a.bin happens to be from your software RNG rather than
from your hardware RNG, then you need a new one!

I have one of the better ones lying around somewhere, let me know if
you need it.

Below is what I saw from my crude-ascii graphics output from the four
test sets.

If you think this would be of interest to cypherpunks, feel free to
post this there...or tell me to.
        Doug
(Note that I'm using a 35 by 80 window to view these)

2811> ran < a.bin
.       .    .... .   .      .... .   .     .....   .        ...
                               .               .             . .
             ...             ....            . .              .


                                             .
                             .                 .
                              .
                               .



              . .            . .. .          ....              .
. .          ....       .   .......  .       ....            ...
...          ....       ..   .....    .     .....           ....
.           ..... .         ..... .         ..... .         ....
.            .... .   .      ....            .... .          ...
                                               .
                .             ...            . ..            .

                                             .

               .             ..

                .              .              .
                                                             .


              ..               ..            ...
. .         ..... .     .   ..... .         .....     .     ....
. .         .......         ......          .....            ...
.      .    ..... .         ..... .         .....           ....

2812> ran < b.bin
........................................................... ....
. ..............................................................
..................................... ..........................
................................................................
...................................... .........................
..................... ..........................................
................................................................
........................................ .......................
................................................................
................................................................
.................... ................. .........................
................................................................
.......................................... .....................
................................................................
.................................... ........................ ..
............................. ..................................
............................................. ..................
................................................................
................................................................
................................ ...............................
................................................................
.........  .....................................................
............................ ...................................
.......................... .....................................
................................................................
................................................................
........... ....................................................
................... ............................................
.......................... .....................................
................................................................
................................................................
.............................................................. .

2813> ran < c.bin
                         .                               .
      .                               .
                   .                               .
.                               .
             .                               .
                          .                               .
       .                               .
                    .                               .
 .                               .
              .                               .
                           .                               .
        .                               .
                     .                               .
  .                               .
               .                               .
                            .                               .
         .                               .
                      .                               .
   .                               .
                .                               .
                             .                               .
          .                               .
                       .                               .
    .                               .
                 .                               .
                              .                               .
           .                               .
                        .                               .
     .                               .
                  .                               .
                               .                               .
            .                               .

2814> ran < d.bin
................................................................
................................................................
... ............................................... ....... ....
........................................................... ....
................................................................
........................................................ .......
................................................................
................................................................
................................................. ..............
...................................... .........................
................................................................
............ ...................................................
................................................................
................................................................
................................................................
................................................................
................................................................
................................................................
................................................................
............... ................................................
................................................................
................................................................
................................................................
................................................................
................................................................
................................................................
.......................... ................ ....................
................................................... ............
................................................................
................................................................
................................................................
................................................................

-------------- end included message -------------