Welome to the Internet, here's your private key

Greg Rose ggr at qualcomm.com
Tue Feb 5 18:06:46 EST 2002


At 03:48 PM 2/5/2002 -0600, Kim-Ee Yeoh wrote:
>I took a brief look at your code, and one optimization you could do is to
>make a single pass for both the monobit and poker tests.  If c_0, c_1,
>..., c_15 are the frequency counts of nibbles, then the monobit count is
>just the sum over all i's of c_i * w(i), where w(i) is the Hamming weight
>of i.

Yep, that's a small and useful optimisation.

>Also the chi-square for the poker test could easily be done in pure
>integer arithmetic by clearing out the denominator of 5000.  (Of course,
>it helps when your embedded system, such as the one I work with, has a
>machine word size of 32 bits.  Your mileage on specific smartcards may
>vary.)

I recognise this too.

My goal when I wrote the code was to cleanly implement the FIPS as it 
described the tests... which I think I did. Anyone who *truly* cares about 
optimising it for a smartcard for example, won't use C code to do it. As I 
said, the only nasty things that would remain at that point are the 16 
multiplies (16x16->32 bit integers), calculating the squares of the poker 
values... these are pretty much unavoidable. Given that, I don't understand 
why the FIPS specified the tests using floating point... *they* should have 
made this optimisation (as they did for the bounds on the runs test, which 
they initially got wrong anyway...)

> > The scariest thing, though... at first I put in an unkeyed RC4 generator
> > for the self-test data, but accidentally ran the FIPS test on a straight
> > counter output... and it passed (even version 1)! I'd always assumed that
> > something in the regularity of a counter would trigger it. Running through
> > the buffer, XORing consecutive bytes, makes it fail quite handily, but
> > might also have the undesirable effect of hiding a bias in the data, if
> > there was one. I'm thinking of suggesting to NIST that a stronger test
> > would be to run the test on the raw data, and then on the data after 
> XORing
> > consecutive bytes... if it's really random stuff it should pass both, and
> > in the meantime this would catch all sorts of failures. Any comments?
>
>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:
9932 ones
Poker test: 317 0x0s
Poker test: 317 0x1s
Poker test: 317 0x2s
Poker test: 317 0x3s
Poker test: 316 0x4s
Poker test: 316 0x5s
Poker test: 316 0x6s
Poker test: 316 0x7s
Poker test: 316 0x8s
Poker test: 316 0x9s
Poker test: 316 0xAs
Poker test: 316 0xBs
Poker test: 304 0xCs
Poker test: 300 0xDs
Poker test: 300 0xEs
Poker test: 300 0xFs
Poker test ChiSquared parameter = 2.304
2497 runs of 1 0s
2529 runs of 1 1s
1252 runs of 2 0s
1255 runs of 2 1s
628 runs of 3 0s
621 runs of 3 1s
317 runs of 4 0s
307 runs of 4 1s
159 runs of 5 0s
152 runs of 5 1s
160 runs of 6 0s
149 runs of 6 1s

I, like you, thought it would flunk, but it doesn't.

>I'm almost as certain that a
>maximal-period LFSR would be similarly detected.  A runs test, especially,
>isn't fooled so easily.

An interesting question. One of the utilities I have lying around happens 
to do LFSRs... so I can answer this.

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)

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
16              Passes test! (16, 5, 3, 2, 0)
17              Passes test! (17, 3, 0)

At this point I am detecting a pattern... So, I'm afraid it isn't true that 
it will pick up even these simple linear sequences. (An LFSR of length 12 
only generates 4095 bits, repeated about 5 times!) I find this less 
surprising, actually. LFSR output "looks" random in some more fundamental 
sense.

>As it stands, the FIPS-140 RNG testsuite is a good compromise between
>speed and validation efficacy.  FIPS-140 is a standard for crypto-module
>validation, and so long as your tests for the RNG component of your
>crypto-module are comparable or exceed those specified in the standard,
>you're doing fine.  You are quite at liberty to perform the additional
>tests you've suggested.

I was surprised that these simple software bad-generators managed to pass 
the test, although the point of the test is more to check out hardware 
failure-modes, like biases or stuck bits. Still. Interesting.

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



More information about the cryptography mailing list