Welome to the Internet, here's your private key

[Bill Frantz]

At 2:09 PM -0800 2/4/02, lynn.wheeler at firstdata.com wrote:
>One could claim that one of the reasons for using RSA digital signatures
>with smart cards rather than DSA or EC/DSA is the DSA & EC/DSA requirement
>for quality random number generation as part of the signature process.
>
>A lot of the RSA digital signatures have the infrastructure that creates
>the message to be signed to also generate and include a large random number
>(nonce) in the message. This was acceptable to a large class of smartcards
>that didn't have quality random number generation (either for the purposes
>of ken-gen and/or signatures). Effective because of the short-comings of
>the random number generation ... they had external source doing the key-gen
>and injecting the key ... along with no requirement for (on-card) random
>number during the signing process (typically a requirement that the
>external source include a random nonce in the body of the message).
>
>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).
>
>2) It is possible to compute a 20-byte SHA1 against the basic message, and
>then do a DSA signature resulting in 40-byte signature (basic message plus
>40-byte infrastructure overhead).
>
>The difference between #1 and #2 is that a smartcard has eliminated any
>dependency in number #1 on the infrastructure providing the message with a
>random number.

The quality of random numbers available to a smart card is a very important
point.  Unless you can trust the external source of random numbers, DSA
signatures (and elliptic curve DSA) don't strike me as very secure.  In
Applied Cryptography II, Schneier says, "If Eve ever recovers a K that
Alice used to sign a message, perhaps by exploiting some properties of the
random-number generator that generated K, she can recover Alice's private
key, X.  If Eve ever gets two messages signed using the same K, even if she
doesn't know what it is, she can recover X."  I can easily imagine a POS
terminal hacked to record both the random number, and the signature, as
part of a card cloning scam.

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

It is probably worth examining the protocols for bad random number attacks
on the nonces.

Cheers - Bill


-------------------------------------------------------------------------
Bill Frantz           | The principal effect of| Periwinkle -- Consulting
(408)356-8506         | DMCA/SDMI is to prevent| 16345 Englewood Ave.
frantz at pwpconsult.com | fair use.              | Los Gatos, CA 95032, USA



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