Welome to the Internet, here's your private key

[Greg Rose]

>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.

Yes, I agree, but it isn't my test, it's just my code for the FIPS test.

>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.

B-M is not something I'd normally recommend to run in power-up tests...

> > 15              multiple runs test failures (byte alignment too good?),
> >                  but passes poker test
>
>You want to recheck your last result.[...]
>FIPS passes the sequence.

Correct, thank you. I've delayed releasing a bunch of my utilities for 
stuff like this because I hadn't yet had time to clean them all up and make 
them consistent... and it turned around and bit me. The "LFSR" program 
outputs ascii 0 or 1... I then used "binbin" to turn it into packed bytes, 
and this program was putting bits into bytes lsb-first. But the FIPS test 
(which originally did lsb-first too, but I was then convinced msb-first was 
"more conventional") didn't agree. It's interesting (but not worth 
pursuing) that simply reversing the bits in the bytes makes it fail the 
test. Anyway, now that I've changed this convention, my results agree with 
yours.

We've probably worn out everyone's interest with this, now. I'm happy to go 
offline with it though.

regards,
Greg.

Greg Rose                                       INTERNET: ggr at qualcomm.com
Qualcomm Australia          VOICE:  +61-2-9817 4188   FAX: +61-2-9817 5199
Level 3, 230 Victoria Road,                http://people.qualcomm.com/ggr/
Gladesville NSW 2111    232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C


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