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.