Welome to the Internet, here's your private key

[Kim-Ee Yeoh]

On Wed, 6 Feb 2002, Greg Rose wrote:

> At 03:48 PM 2/5/2002 -0600, Kim-Ee Yeoh wrote:
>
> >Could you clarify what you mean by "counter output"?  Are we talking about
> >a sequence of consecutive 8-, 16-, or 32-bit numbers?  If so, FIPS will
> >detect and flunk such sequences.
> 
> While priming the RC4 table, I accidentally filled the data buffer instead 
> (D'oh!) with consecutive byte values 0x00, 0x01, ... 0xFF, 0x00, ...
> 
> This very much passes the FIPS 140 tests for randomness, despite being 
> nothing like it:
>	<statistics snipped>

For 16-bit or 32-bit sequences of consecutive numbers starting with 0,
FIPS easily flunks them because there are too many gaps (consecutive runs
of zeroes). 

And if the runs test in FIPS were slightly extended, your sequence of
consecutive 8-bit numbers would have been easily caught too.  Here's the
full spectrum of runs for your sequence:

	Run-length	# of gaps	# of blocks
	==========	=========	===========
	1		2497		2529
	2		1252    	1255
	3		 628    	 621
	4		 317    	 307
	5		 159    	 152
	6		  80    	  75
	7		  70    	   0
	8		   0    	  74
	9-14		   0    	   0
	15		  10    	   0
	16 and up	   0    	   0

That there are 70 gaps of length exactly 7 but no blocks at all of the
same length is extremely anomalous behavior for the output of a putative
RNG.  Extending the runs test from 6 to 8 categories, i.e. counting blocks
and gaps for run-lengths of exactly 1 to 7 and for run-lengths of 8 and
greater, would easily have caught this.

I will even go further as to quantify what I mean by "extremely anomalous
behavior."  The expected number of blocks (or gaps) of length exactly p in
a uniformly random n-bit sequence is e(n,p) = (n-p+3)/2^(p+2) with a
variance of v(n,p) = (3*p^2-2*n*p-8*p+n-3)/2^(2*p+4) + e(n,p), a result
that can be shown without too much difficulty.  As n tends toward
infinity, the distribution in the limit is Gaussian (see Knuth V2 3E p69).
The probability that a uniformly random 20000-bit sequence has no blocks
of length 7 is no more than 2.1 * 10^(-10), several orders of magnitude
lower than the one-in-a-million threshold at which the FIPS tests are
calibrated.

> Up to LFSR length 8, there are too few runs of length 6 or greater, so they 
> must fail. LFSR Length 9 fails the low end of the chi-squared test... too 
> evenly distributed. (Note that the counter above only passes this because 
> it cuts off in the middle of a byte count, and so skews away from the 
> one-heavy end of the spectrum). Hmmm... a table is required. (I'm using the 
> first polynomial specified in Schneier of each length, impulse sequence:
> $ lfsr -n 20000 16 5 3 2 | binbin | fips140)

As you have noted, simple LFSRs are easily detected by FIPS.  LFSRs of
longer period can be detected by using both a larger sample and analyzing
the full, rather than the truncated, runs spectrum.  Alternatively, if you
simply want to eliminate any possibility of an LFSR, just apply
Berlekamp-Massey. 

> Poly Length     Description of failure
> -----------     ------------------
> 9               Poker test too regular
> 10              Poker test too regular
> 11              Poker test too regular
> 12              Passes test! (12, 6, 4, 1, 0)
> 13              Passes test! (13, 4, 3, 1, 0)
> 14              Passes test! (14, 5, 3, 1, 0)
> 15              multiple runs test failures (byte alignment too good?),
>                  but passes poker test

You want to recheck your last result.  The primitive binary polynomial
x^15+x+1 with a starting seed of 1 produces a sequence that starts with a
length-14 gap followed by a length-15 block.  The FIPS runs spectrum is:

	Run-length	# of gaps	# of blocks
	==========	=========	===========
	 1		2536    	2514
 	 2		1284    	1250
	 3		 633    	 650
	 4		 310    	 322
	 5		 153    	 157
	 6 and up	 131		 154

FIPS passes the sequence.



Kim-Ee


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com