Path: cactus.org!milano!cs.utexas.edu!usc!wupost!uunet!mcsun!sun4nl!alchemy!
+     accucx!nevries
From: nevries@accucx.cc.ruu.nl (Nico E de Vries)
Newsgroups: sci.crypt

Subject: IBM-PC random generator, survey #1
Message-ID: <2821@accucx.cc.ruu.nl>
Date: 29 Jun 92 18:39:18 GMT
Organization: Academic Computer Centre Utrecht
Lines: 92

Hope it is of some use. Comment, critique, applause, all welcome!


Nico E. de Vries
_ _
O O  USENET nevries@cc.ruu.nl  FIDO 2:281/708.1  COMPUSERVE "soon" (tm)
 o   This text reflects MY opinions, not that of my employer BITECH.      
\_/  This text is supplied 'AS IS', no waranties of any kind apply.      
     Don't waste your time on complaining about my hopeless typostyle.

"Unfortunately, the current generation of mail programs do not have checkers
 to see if the sender knows what he is talking about" (A.S. Tanenbaum)

*------*

Survey #1, "Nico's random generator"
====================================

As many readers of sci.crypt probably noticed I posted a random
generator for the IBM-PC a while ago. I asked for testing comment
and discussion and I got them! I would like to thank everyone
who has contributed. This does NOT mean I am finished BTW. I need
much more statistics and thoughts than we currently have.

The basic principle.
--------------------
The idea behind the algo is the use of phase noise in crystals (notice
I have refered to this as jitter which was a huge mistake of mine). To
measure the phase shift of a crystal a second crystal is used. I use
for this purpose the microprocessor clock and the real time clock.
The microprocessor raises a counter in a loop and an (real time
clock controlled) interrupt handler samples the counter. The last
bit of these "samples" is used. On fast computers this is all what
is needed on slower computers the microprocessor controlled
loop seems to become too slow. To correct that problem the basic process
is repeated 8 times and the results are exclusive orred. This solution
has been chosen to make the algo machine independent.

Practical experiments.
----------------------
Many tests have been performed (I HOPE TO GET EVEN MORE RESULTS ???). Noone
of them found any problems (notice that this proves nothing). Some test
performed are:
   - basic statistic tests (freq etc)
   - graphical tests
   - patern analyzation using higher order data compressors
   - some of Knuths tests (I hope to get all of them)

Theory.
-------
The most major consern seems to be if my algo is capable of actually
measuring phase noise. The possibility if this can be done with IBM-PC
software is debated. No hard evidence on either side of this has been
found yet.

Removing the repeat counter (8) still leaves us with a "working" random
generator (if CTR is fast enough, working defined as noone found problems
with practical tests yet). If the phase noise is NOT measured one should
be capable of explaining its working. Two major arguments have risen:

- the cycle size (number of different states) is very large
- other hardware events (e.g. DMA refresh) enhance the cycle size

Notice that in both these cases it is possible (in theory) to predict
the output of the generator given the EXACT specifications of the
machine on which it runs. This means the generator can be "safely" (in
the context of cryptographics) used to generate a SMALL amount of
data (the position in the cycle at start of the algo etc).

If the phase noise IS measured than this argumentation is less
interesting.

Improvements.
-------------
Some possible improvements.

A reversing the scheme, timer loops, uP samles
B using more or other crystals (video retrace, COM ports)
C postprocessing the output with MD5

C is debatable. One could claim it makes the basic generator useless
but in an open environment ("Cheater" has all the algo's and info)
it does improve the safeness without having large disadvantages. A
simple seed based generator postprocessed by MD5 might be easier to
crack if a cheater knows the exact procedure used.

"Conclusion".
-------------
I don't have any for now but I'll try one.
The generator is, accorfing to many, "usefull". For heavy duty environments
advanced (and expensive) hardware is probably a better choice. For "poor
mans" random generation it might turn out to be usefull.