Path: cactus.org!milano!cs.utexas.edu!uunet!mcsun!uknet!cam-cl!cam-cl!rja14
From: rja14@cl.cam.ac.uk (Ross Anderson)
Newsgroups: sci.crypt

Subject: Re: IBM-PC random generator, source included
Message-ID: <1992Jun24.164407.28468@cl.cam.ac.uk>
Date: 24 Jun 92 16:44:07 GMT
References: <2673@accucx.cc.ruu.nl> <1992Jun23.080147.15804@cactus.org>
+           <2677@accucx.cc.ruu.nl> <1992Jun23.200511.27492@cactus.org>
+           <2797@accucx.cc.ruu.nl>
Sender: news@cl.cam.ac.uk (The news facility)
Reply-To: rja14@cl.cam.ac.uk (Ross Anderson)
Organization: U of Cambridge Computer Lab, UK
Lines: 30

The current flame war:

>> The total state for Nico's scheme seems to be contained in: 1) the
>> refresh counter-timer, 2) the interrupt counter-timer, 3) the
>> software counter lsb, and 4) the period uncertainty when used in a
>> particular program.  This will be 4.2 + 12 + 1 + 2(?) = 19.2 bits,
>> and this is not enough to prevent analysis.  
>
>I don't exactly see where your numbers come from but if they are
>correct changing the repeat counter into 24 should make the random
>generator better?
>
>> increase the state-space by up to 7 bits by using the byte-parity
>> of each sample instead of just using the lsb, but this will not
>
>I don't see the advantage of this. The jitter can only be measured
>when the last bit value changes (the time between two changes is
>undeterministic). Thats why the repeat is there. 

should be amenable to birthday testing. 

If Nico's generator does indeed approximate to a virtual state machine with 
less than 32 bits of state, then this could be detected by drawing at most a
few hundred thousand samples and counting the number of doubles (and triples 
if any).

I have a preprint on such testing if anybody's interested but the basic
principles should be obvious enough from basic probability theory.

Ross