Welome to the Internet, here's your private key

[Greg Rose]

At 04:24 PM 2/4/2002 -0800, Bill Frantz wrote:
>At 2:09 PM -0800 2/4/02, lynn.wheeler at firstdata.com wrote:
> >1) A typical message would have a 20-byte nonce random number, which
> >computed to a 20-byte SHA1 and then encrypted with RSA resulting in 20-byte
> >signature (basic message plus 40-byte infrastructure overhead, signature
> >plus nonce).

I think an RSA signature can be no smaller than the key modulus, so an RSA 
sig with a 1024-bit key is going to be 128 bytes plus some overhead, no 
matter what. I think you (Lynn) meant DSA here. Or maybe you did mean RSA, 
given that you then go on to DSA... I don't know.

>On the other hand, building a good source of random numbers into the card
>doesn't strike me as being that difficult.  (Although running a FIPS-140
>test every time a signature is generated (card is powered up), might be a
>performance problem.)

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). Anyway, on a 0.5 MHz 
smarcard, it's probably fair to assume this would take 0.5 seconds or so 
(my C code is meant for clarity, not speed). This is probably less than the 
time required for an RSA or DSA signature (taking into account the 
precomputation) without hardware acceleration.

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?

Anyway, if anyone wants it, the new fips140.c (with self-test and timing 
loop support, but no other changes) is on my web page.

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