Welome to the Internet, here's your private key

Kim-Ee Yeoh yeoh at cs.wisc.edu
Tue Feb 5 16:48:08 EST 2002


On Tue, 5 Feb 2002, Greg Rose wrote:

> This forced me to instrument my FIPS-140 code to measure it. It takes 1.42 
> ms to run a test on a Sun Ultra at 250MHz (I know, this is an ancient 
> machine). It's all integer arithmetic, on short integers at that, except 
> for the chi-square poker test, which (currently) does some floating point 
> but could easily be recoded to do scaled, 32-bit integer (16 x 16 -> 32 bit 
> multiplies, 16 of them, would be the bottleneck).

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.

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


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

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.


Kim-Ee


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



More information about the cryptography mailing list